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 = (n1, n2....,nm), where ni 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 ni into a fixed-length binary word of length log2l, where l is an a priori upper bound on the codeword length. This method produces a maximum preamble length of mlog2l bits. The object is to show that, in most cases, no substantially shorter header of any kind is possible.