0

I'm doing some research on Huffman coding, there are some variants and I can't find their use case in real applications.

Huffman (classic): ? (pass tree with 0 for node and 1 for leaf)

Efficient way of storing Huffman tree

Canonical Variant

  • JPEG
  • PNG

Fixed Variant

  • Deflate
  • HPACK http/2

Adaptative Variant: ?

Do you know of any other use cases?

Thank you.

flobib
  • 1
  • 1

1 Answers1

0

I'm not sure what you're trying to discriminate there between "canonical" and "fixed". All implementations I know of use canonical Huffman codes, since that avoids having to transmit information about a Huffman code that is irrelevant. Both Deflate and JPEG use both fixed and dynamic Huffman codes, where fixed codes are defined a priori, and dynamic codes depend on the data being compressed.

PNG uses Deflate as does many, many other applications. Some examples are gzip, zip, HTTP (with the gzip or zlib "deflate" encodings), PDF, FITS, CDF, HDF. I have no idea how many more.

You just used Deflate to read this web page. There! You did it again. You do this every day, many many times.

Brotli is another compression format that uses Huffman codes.

I'm sure there are a thousand others, many of which are proprietary.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158
  • Hmm, You said `I'm not sure what you're trying to discriminate there between "canonical" and "fixed"`, but it's two different implementations. You say it yourself here`Both Deflate and JPEG use both fixed and dynamic Huffman codes, where fixed codes are defined a priori, and dynamic codes depend on the data being compressed.` – flobib Mar 31 '22 at 07:47
  • and my question isn't where to use Huffman, it is where to use the specific variants – flobib Mar 31 '22 at 07:53
  • An example, you said `Brotli is another compression format that uses Huffman codes.`, ok good to know, but which variant is used ? – flobib Mar 31 '22 at 07:54
  • My question is more oriented on the Adaptative variant and the classic form – flobib Mar 31 '22 at 07:55
  • But thanks for your answer, I didn't know that PDF, FITS, CDF, and HDF formats use the Huffman coding. I will check it out. – flobib Mar 31 '22 at 08:00
  • I don't know of any production code that uses adaptive Huffman coding. Your "canonical" and "fixed" categories don't make any sense. PNG uses Deflate, so whatever you want to call it, they both use exactly the same thing. Yet you have them in different categories. Fixed and Dynamic (different from adaptive) Huffman coding _both_ use Canonical codes. JPEG, like Deflate, also can use Fixed or Dynamic codes. HPACK uses only fixed Huffman codes. – Mark Adler Mar 31 '22 at 13:54
  • I don't understand, the canonical variant is a method to build the huffman tree and pass it into the encoded file. In the case of the fixed variant, the tree is already built and the tree is not encoded in the file (for decompression, the algorithm needs the encoding table). So for me it is completely different. – flobib Apr 01 '22 at 14:57
  • The fixed variant is based on the frequency of a language, for HPACK, it is the English language – flobib Apr 01 '22 at 15:00
  • Even for the fixed variant, e.g. in deflate, canonical codes are used. they are built in the same way as the dynamic codes. However each only once. – Mark Adler Apr 01 '22 at 16:40
  • The distinction I think you're trying to make is dynamic vs. fixed (sometimes called static). Whether the dynamic codes are transmitted or the fixed codes are built using a canonical description of code lengths is irrelevant. They don't have to be built or transmitted that way. Though it is usually the practical approach. – Mark Adler Apr 01 '22 at 16:48