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.

- During the updates, the Huffman tree will be maintained its