Thread: Trying to figure out DEFLATE

The part I'm having trouble with is decoding the Huffman codes when they're specified in the header. This is done by the code lengths, and I get most of the process. The part I don't get, is the application of DEFLATE's two extra rules to make decoding using just the lengths possible. To quote the RFC:

* 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 part I don't get is the second rule. Again, quoting the RFC:

We could recode the example above to follow this rule as
follows, assuming that the order of the alphabet is ABCD:

Symbol Code
------ ----
A 10
B 0
C 110
D 111

I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are
lexicographically consecutive.

Shouldn't B be before A, seeing that it's shorter than A? How is 0 preceding 10? It's shown again in another example in the RFC:

Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111

Shouldn't the length 2 be at the top, making 00 the code for A, and so on? I don't get it.

EDIT: Sorry, formatting didn't work as expected.

Originally Posted by MK27

Umm -- alphabetical and lexicographical are same thing:

lexicographical order

So the difference is that the lexicographical/alphabetical order used in the table is not the same as the lexicographical/alphabetical order "mentioned in the RFC".

Ie, the table is ordered with the left hand column, but discussed in terms of ordering with the right hand column. RFCs can be very obtuse. Not that I know anything much about Huffman encoding.

Visually version of above remark

alphabetical/lexicographical of column 1

Code:

Symbol Code
------    ----
A         10
B         0
C         110
D         111

alphabetical/lexicographical of column 2

Code:

Symbol Code
------    ----
B         0
A         10
C         110
D         111

There are not the same in the RFC because they were likely talking about sorting by different columns.

Tim S.