Estimating the Size of Huffman Code Preambles
Data compression via block-adaptive Huffman coding is considered. The compressor consecutively processes blocks of N data symbols, estimates source statistics by computing the relative frequencies of each source symbol in the block, and then synthesizes a Huffman code based on these estimates. In order to let the decompressor know which Huffman code is being used, the compressor must begin the transmission of each compressed block with a short preamble or header file. This file is an encoding of the list n = (n 1 , n 2 ....,n m ), where n i is the length of the Hufffman codeword associated with the ith source symbol. A simple method of doing this encoding is to individually encode each n i into a fixed-length binary word of length log 2 l, where l is an a priori upper bound on the codeword length. This method produces a maximum preamble length of mlog 2 l bits. The object is to show that, in most cases, no substantially shorter header of any kind is possible.