Estimating the size of Huffman code preambles

Abstract

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(sub 1), n(sub 2)....,n(sub m)), where n(sub 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(sub i) into a fixed-length binary word of length log(sub 2)l, where l is an a priori upper bound on the codeword length. This method produces a maximum preamble length of mlog(sub 2)l bits. The object is to show that, in most cases, no substantially shorter header of any kind is possible.