Canonical Huffman code
From Wikipedia, the free encyclopedia
|This article does not cite any references or sources.|
Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009)
|This article may need to be wikified to meet Wikipedia's quality standards. Please help by adding relevant internal links, or by improving the article's layout. (December 2009)|
A canonical Huffman code is a particular type of Huffman code which has the property that it can be very compactly described.
Data compressors generally work in one of two ways. Either the decompressor can infer what codebook the compressor has used from previous context, or the compressor must tell the decompressor what the codebook is. Since a canonical Huffman codebook can be stored especially efficiently, most compressors start by generating a "normal" Huffman codebook, and then convert it to canonical Huffman before using it.
The normal Huffman coding algorithm assigns a variable length code to every symbol in the alphabet. More frequently used symbols will be assigned a shorter code. For example, suppose we have the following non-canonical codebook:
A = 11B = 0C = 101D = 100
Here the letter A has been assigned 2 bits, B has 1 bit, and C and D both have 3 bits. To make the code a canonical Huffman code, the codes are renumbered. The bit lengths stay the same with the code book being sorted first by codeword length and secondly by alphabetical value:
B = 0A = 11C = 101D = 100
Each of the existing codes are replaced with a new one of the same length, using the following algorithm:
- The first symbol in the list gets assigned a codeword which is the same length as the symbol's original codeword but all zeros. This will often be a single zero ('0').
- Each subsequent symbol is assigned the next binary number in sequence, ensuring that following codes are always higher in value.
- When you reach a longer codeword, then after incrementing, append zeros until the length of the new codeword is equal to the length of the old codeword. This can be thought of as a left shift.
By following these three rules, the canonical version of the code book produced will be:
B = 0A = 10C = 110D = 111
Encoding the Codebook
The whole advantage of a canonical Huffman tree is that one can encode the description (the codebook) in fewer bits than a fully-described tree.
Let us take our original Huffman codebook:
A = 11B = 0C = 101D = 100
There are several ways we could encode this Huffman tree. For example, we could write each symbol followed by the number of bits and code:
('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)
Since we are listing the symbols in sequential alphabetical order, we can omit the symbols themselves, listing just the number of bits and code:
(2,11), (1,0), (3,101), (3,100)
With our canonical version we have the knowledge that the symbols are in sequential alphabetical order and that a later code will always be higher in value than an earlier one. The only parts left to transmit are the bit-lengths (number of bits) for each symbol. Note that our canonical Huffman tree always has higher values for longer bit lengths and that any symbols of the same bit length (C and D) have higher code values for higher symbols:
A = 10 (code value: 2 decimal, bits: 2)B = 0 (code value: 0 decimal, bits: 1)C = 110 (code value: 6 decimal, bits: 3)D = 111 (code value: 7 decimal, bits: 3)
Since two-thirds of the constraints are known, only the number of bits for each symbol need be transmitted:
2, 1, 3, 3
With knowledge of the canonical Huffman algorithm, it is then possible to recreate the entire table (symbol and code values) from just the bit-lengths. Unused symbols are normally transmitted as having zero bit length.
Given a list of symbols sorted by bit-length, the following pseudo code will print a canonical Huffman code book:
code = 0while more symbols: print symbol, code code = (code + 1) << ((next bit length) - (current bit length))