Citation
Abstract
In this article, 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,,N2,...,Nm), Where nj is the length of the Huffman codeword associated with the ith source symbol. A simple method of doing this encoding is to individually encode each nj into a fixed-length binary word of length logal, where | is an a priori upper bound on the codeword length. This method produces a maximum preamble length of mlog| bits. The object of this article is to show that, in most cases, no substantially shorter header of any kind is possible.
Details
- Volume
- 42-114
- Published
- August 15, 1993
- Pages
- 90–95
- File Size
- 229.1 KB