Adaptive Huffman Coding

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.