Adaptive Huffman coding

It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data.

There are a number of implementations of this method, the most notable are FGK (Faller-Gallager-Knuth) and Vitter algorithm.

Having no initial knowledge of occurrence frequencies, it permits dynamically adjusting the Huffman's tree as data are being transmitted.

In a FGK Huffman tree, a special external node, called 0-node, is used to identify a newly coming character.

For a past-coming character, just output the path of the data in the current Huffman's tree.

Most importantly, we have to adjust the FGK Huffman tree if necessary, and finally update the frequency of related nodes.

As the frequency of a datum is increased, the sibling property of the Huffman's tree may be broken.

For the convenience of explanation this step doesn't exactly follow Vitter's algorithm,[2] but the effects are equivalent.

Slide_And_Increment(leaf node) sliding starts. P is a leaf node.
Slide_And_Increment(leaf node) sliding step 2. As P is leaf node, it slides in front of next block nodes of equal weight.
Slide_And_Increment(leaf node) sliding step 3. Here we increase the current weight by 1.
Slide_And_Increment(leaf node) sliding step 4. Method comes to an end. P is the new parent.
Slide_And_Increment(internal node) sliding starts. P is an internal node.
Slide_And_Increment(internal node) sliding step 2. Node P slides in front of next block of leaves nodes, with weight wt+1.
Slide_And_Increment(internal node) sliding step 3. Now we increase the weight to 9. Thus the invariant is maintained as the current node is an internal node and should occur in front of leaf nodes of equal weight as we have increased the weight.
Slide_And_Increment(internal node) sliding step 4. Now the 'P' points to the former parent ( as in the case of internal node according to algorithm)