Huffman coding is a widely used method of entropy coding used for data compression. It assumes that we have complete knowledge of a signal's statistics. However, there are versions of Huffman coding that are used with streaming media and cannot possibly know everything about the signal's statistics. How do these adaptive Huffman encoders work?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Have you read the Wikipedia article, including the example implementation? en.wikipedia.org/wiki/Adaptive_Huffman_coding#Vitter_algorithm Do you have a more specific question? $\endgroup$– endolithCommented Aug 23, 2011 at 18:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The Wikipedia article has a pretty good description of the adaptive Huffman coding process using one of the notable implementations, the Vitter algorithm. As you noted, a standard Huffman coder has access to the probability mass function of its input sequence, which it uses to construct efficient encodings for the most probable symbol values. In the prototypical example of file-based data compression, for example, this probability distribution can be calculated by histogramming the input sequence, counting the number of occurrences of each symbol value (symbols could be 1-byte sequences, for example). This histogram is used to generate a Huffman tree, like this one (taken from the Wikipedia article):
The tree is arranged by decreasing weight, or probability of occurrence in the input sequence; leaf nodes at the top represent the most probable symbols, which therefore receive the shortest representations in the compressed data stream. The tree is then saved along with the compressed data and is subsequently used by the decompressor later to regenerate the (uncompressed) input sequence again. As one of the early entropy code implementations, standard Huffman coding is fairly straightforward.
The adaptive Huffman coder's structure is quite similar; it uses a similar tree-based representation of the input sequence's statistics to select efficient encodings for each input symbol value. The main difference is that, as a streaming implementation of the algorithm, no a priori knowledge of the input's probability mass function is available; the sequence's statistics must be estimated on the fly. If one is to use the same Huffman encoding scheme, this means that the tree used to generate each symbol's encoding in the compressed stream must be built and maintained dynamically as the input stream is processed.
The Vitter algorithm is one way of accomplishing this; as each input symbol is processed, the tree is updated, maintaining its characteristic of decreasing probability of symbol occurrence as you move down the tree. The algorithm defines a set of rules for how the tree is updated over time, and how the resulting compressed data is encoded in the output stream. As the input sequence is consumed, the tree's structure should represent a more and more accurate description of the input's probability distribution. In contrast to the standard Huffman coding approach, the decompressor does not have a static tree to use for decoding; it must perform the same tree-maintenance functions continuously during the decompression process.
In summary: The adaptive Huffman coder operates very similarly to the standard algorithm; however, instead of a static measurement of the entire input sequence's statistics (the Huffman tree), a dynamic, cumulative (i.e. from the first symbol to the current symbol) estimate of the sequence's probability distribution is used to encode (and decode) each symbol. In contrast to the standard Huffman coding approach, the adaptive Huffman algorithm requires this statistical analysis at both the encoder and decoder.
