Canonical Huffman code

A canonical Huffman code is a particular type of Huffman code with properties that let it be described very compactly. Instead of storing the structure of the code tree explicitly, the codewords are ordered so that it is enough to store only the length of each codeword, which cuts the overhead of the codebook. Most compressors therefore first build an ordinary Huffman codebook and then convert it to canonical form before using it. The conversion sorts the symbols by codeword length from shortest to longest and, within one length, by alphabetical or numerical value. The first symbol gets a codeword of all zeros of its original length, each following symbol gets the next binary number in sequence, and when the length grows the new codeword is padded with zeros, which amounts to a left shift. Because codes of the same length are assigned sequentially, the decoder can be much simpler and faster than one that must walk a tree stored in memory, and the encoded data no longer has to carry the tree nodes and their references.