Next: Arithmetic Coding
Up: Lossless Compression Algorithms (Entropy
Previous: Huffman Coding of Images
The basic Huffman algorithm has been extended, for the following reasons:
(a) The previous algorithms require the statistical knowledge which is
often not available (e.g., live audio, video).
(b) Even when it is available, it could be a
heavy overhead especially when many tables had to be sent when
a non-order0 model is used, i.e. taking
into account the impact of the previous symbol to the probability of the
current symbol (e.g., "qu" often come together, ...).
The solution is to use adaptive algorithms. As an example, the
Adaptive Huffman Coding is examined below.
The idea is however applicable to other adaptive compression algorithms.
ENCODER DECODER
------- -------
Initialize_model(); Initialize_model();
while ((c = getc (input)) != eof) while ((c = decode (input)) != eof)
{ {
encode (c, output); putc (c, output);
update_model (c); update_model (c);
} }
}
- The key is to have both encoder and decoder to use exactly the
same initialization and update_model routines.
- update_model does two things: (a) increment the count,
(b) update the Huffman tree (Fig 7.2).
- During the updates, the Huffman tree will be maintained its
sibling property, i.e. the nodes (internal and leaf) are
arranged in order of increasing weights (see figure).
- When swapping is necessary, the farthest node with weight
W is swapped with the node whose weight has just been increased to W+1.
Note: If the node with weight W has a subtree beneath it,
then the subtree will go with it.
- The Huffman tree could look very different after node
swapping (Fig 7.2), e.g., in the third tree, node A is again
swapped and becomes the #5 node. It is now encoded using only 2 bits.
Note: Code for a particular symbol changes during the
adaptive coding process.
Next: Arithmetic Coding
Up: Lossless Compression Algorithms (Entropy
Previous: Huffman Coding of Images
Dave Marshall
10/4/2001