29-06-2012, 04:37 PM
Adaptive Huffman Coding
Adaptive Huffman Coding.ppt (Size: 281.5 KB / Downloads: 195)
Why Adaptive Huffman Coding
Huffman coding suffers from the fact that the uncompresser need have some knowledge of the probabilities of the symbols in the compressed files
this can need more bit to encode the file
if this information is unavailable compressing the file requires two passes
first pass: find the frequency of each symbol and construct the huffman tree
second pass: compress the file
Some history
Adaptive Huffman coding was first conceived independently by Faller (1973) and Gallager (1978)
Knuth contributed improvements to the original algorithm (1985) and the resulting algorithm is referred to as algorithm FGK
A more recent version of adaptive Huffman coding is described by Vitter (1987) and called algorithm V
An important question
Better exploiting locality, adaptive Huffman coding is sometimes able to do better than static Huffman coding, i.e., for some messages, it can have a greater compression
... but we’ve assessed optimality of static Huffman coding, in the sense of minimal redundancy
Algorithm FGK - V
The first phase starts at the leaf of the t+1-th symbol
We swap this node and all its subtree, but not its numbering, with the highest numbered node of the same weight
New current node is the parent of this latter node
The process is repeated until we reach the root
Algorithm FGK - summary
The algorithm starts with only one leaf node, the 0-node. As the symbols arrive, new leaves are created and each time the tree is recomputed
Each symbol is coded with its codeword in the current tree, and then the tree is updated
Unseen symbols are coded with 0-node codeword and some other bits are needed to specify the symbol