gzip lies

[astralchan]

Topics of Discussion

In the interest of contributers, this discussion is for discussing everything relating to parsing / extracting the gzip format. Anything relating to the parsing of the gzip format and / or handling deflate data streams can be discussed here. Including strategies to handle Huffman tables / compression along with LZ 77 compression both used in the deflate algorithm.

[CheetahPixie]

And of course to outline quirks, weirdness and other stuff we encounter along the way. .tar has already proven complicated enough for its own lies discussion later, actually.

[astralchan]

I've been trying to read through RFC 1951 as to how the deflate compression method uses Huffman coding to compress the data blocks. Here's an example on page 7:

         / \
        0   1
       /      \
     / \        B
    0   1
  /       \
A        / \
        0   1
       /      \
      D        C

This produces the following Huffman codes for each symbol following the path each branch to the symbol of the binary tree:

A 00
B 1
C 011
D 010

Specifically within a deflate data block, the Huffman algorithm follows two rules:

• All codes of a given bit length have lexicographically
  consecutive values, in the same order as the symbols
  they represent;
• Shorter codes lexicographically precede longer codes.

The RFC then goes on to say that, applying these rules, they can recode that example to the following Huffman codes:

A 10
B 0
C 110
D 111

I guess I'm failing to see how the first example breaks the two rules? The alphabetical order in the example is, I assume, ABCD for symbols A, B, C, and D. In the first example, C and D have Huffman code lengths of 3 and are presented in order. The shorter code for B is after the longer code for A. Any thoughts?

[astralchan]

I came across two videos while looking for info on Huffman encoding and these two videos helped greatly:
https://www.youtube.com/watch?v=JsTptu56GM8
https://www.youtube.com/watch?v=iiGZ947Tcck
I know that the implementation of Huffman coding in deflate is a little special, but understanding the basic Huffman coding process feels nice and that it will help.