File CanonicalHuffman.h

↰ Parent directory (ADS/compression)

The canonical code of Huffman (section 12.1.1 of the notes): the lengths L( :math:` sigma ` ) of the codes of Huffman [see File Huffman.h, whose huffman() gives them], and a new code with the same lengths, hence as short, chosen so that neither the encoder nor the decoder needs the tree.

Definition (ADS/compression/CanonicalHuffman.h)

Detailed Description

With num[ l ] the number of the symbols of length l and max the longest length, the first code of length l is :math:` fc[ max ] = 0 ` and :math:` fc[ l ] = lceil ( fc[ l + 1 ] + num[ l + 1 ] ) / 2 rceil , the parent of the first unused node of the level below, and the symbols of length l, in their order, get the consecutive codes :math: fc[ l ] , fc[ l ] + 1 , ldots ` on l bits: the tree is skewed to the left, the longest codes being all zeros at the start. The notes divide without rounding up, which is the same on the complete codes that the algorithm of Huffman gives (the sum is even there); rounding up also keeps the decoder right on a code that is not complete, e.g., one cut by the limit on the lengths. The decoder reads one bit at a time, v being the value of the l bits read, and stops at the first l with :math:` v ge fc[ l ] , since the codes of length l are the values from fc[ l ] on and every prefix of a longer code is smaller: the symbol is symb[ l ][ v - fc[ l ] ]. Hence the preamble is the lengths alone, at most :math: max^2 ` bits for fc and :math:` ( |\Sigma| + max ) log_2( |\Sigma| + 1 ) ` for symb, instead of the pointers of the tree, and the decoding of a code of l bits makes l steps on two arrays that fit in the cache, instead of l steps along the pointers of the tree, each a possible miss. The decoders of the practice go further, as the literature explains: a table indexed by the next k bits gives the length of most codes in one access (Moffat and Turpin), and the canonical code is that of the Huffword of Witten, Moffat and Bell, whose symbols are the words of a text.

The average length of the code of Huffman is within one bit of the entropy, :math:` H_0 le L_H < H_0 + 1 ` (Theorem 12.2) [see File Entropy.h], and its codes can be long: a frequency that grows as the numbers of Fibonacci gives a code of 33 bits after about :math:` 10^7 ` symbols (section 12.1.2). limitedLengths() bounds them to a given L by the iterative scaling of the notes: the frequencies are halved until the code of Huffman has no length above L, which in the limit gives a code of fixed length :math:` lceil log_2 |\Sigma| rceil ; the package-merge of Larmore and Hirschberg finds the optimal code of lengths at most L in :math: O( |\Sigma| L ) ` time, at the price of a less simple algorithm. The construction takes :math:` O( |\Sigma| log |\Sigma| ) ` time, the encoding of a symbol O( 1 ) and its decoding O( L( sigma ) ).

The contracts [see File Contract.h]: the lengths are positive, at most 63, and satisfy the inequality of Kraft, :math:` sum_sigma 2^{-L( sigma )} le 1 ; the frequencies of limitedLengths() are positive and :math: 2^L ge |\Sigma| `; a symbol encoded has a code, and the bits decoded are codes; decode( encode( x ) ) == x, an audit. The operations are defined in CanonicalHuffman.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 12

    1. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the IRE 40(9), 1098-1101, 1952, doi:10.1109/JRPROC.1952.273898

    1. Schwartz, B. Kallick, Generating a canonical prefix encoding, Communications of the ACM 7(3), 166-169, 1964, doi:10.1145/363958.363991

  1. Moffat, A. Turpin, On the implementation of minimum redundancy prefix codes, IEEE Transactions on Communications 45(10), 1200-1207, 1997, doi:10.1109/26.634683

    1. Larmore, D. S. Hirschberg, A fast algorithm for optimal length-limited Huffman codes, Journal of the ACM 37(3), 464-473, 1990, doi:10.1145/79147.79150

    1. Witten, A. Moffat, T. C. Bell, Managing Gigabytes, 2nd ed., Morgan Kaufmann, 1999

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions