Editing Adaptive Huffman coding (section)

===Vitter algorithm===
Some important terminologies & constraints :-
* '''Implicit Numbering''' : It simply means that nodes are numbered in increasing order by level and from left to right. i.e. nodes at bottom level will have low implicit number as compared to upper level nodes and nodes on same level are numbered in increasing order from left to right. In other terms, when we have built the Huffman tree, when merging two nodes into a parent node, we have set the one with the lower value as the left child, and the one with the higher value as the right child.
* '''Invariant''' : For each weight w, all leaves of weight w precede all internal nodes having weight w. In other terms, when we have built the Huffman tree, if several nodes had the same value, we prioritized merging the leaves over the internal nodes.
* '''Blocks''' : Nodes of same weight and same type (i.e. either leaf node or internal node) form a Block.
* '''Leader''' : Highest numbered node in a block.

Blocks are interlinked by increasing order of their weights.

A leaf block always precedes internal block of same weight, thus maintaining the invariant.

'''NYT (Not Yet Transferred)''' is a special node used to represent symbols which are ''<nowiki>'not yet transferred'</nowiki>''.

[[File:Leaf step one.png|thumb|Slide_And_Increment(leaf node) sliding starts. P is a leaf node.]]
[[File:Leaf step two.png|thumb|Slide_And_Increment(leaf node) sliding step 2. As P is leaf node, it slides in front of next block nodes of equal weight.]]
[[File:Leaf step three.png|thumb|Slide_And_Increment(leaf node) sliding step 3. Here we increase the current weight by 1.]]
[[File:Leaf step four.png|thumb|Slide_And_Increment(leaf node) sliding step 4. Method comes to an end. P is the new parent.]]
[[File:Internal one.png|thumb|Slide_And_Increment(internal node) sliding starts. P is an internal node.]]
[[File:Internal two.png|thumb|Slide_And_Increment(internal node) sliding step 2. Node P slides in front of next block of leaves nodes, with weight wt+1.]]
[[File:Internal three.png|thumb|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.]]
[[File:Internal four.png|thumb|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)]]

 '''algorithm''' for adding a symbol '''is'''
     leaf_to_increment := NULL
     p := pointer to the leaf node containing the next symbol
 
     '''if''' (p is NYT) '''then'''
         Extend p by adding two children
         Left child becomes new NYT and right child is the new symbol leaf node
         ''p'' := parent of new symbol leaf node
         leaf_to_increment := Right Child of p
     '''else'''
         Swap p with leader of its block
         '''if''' (new p is sibling to NYT) '''then'''
             leaf_to_increment := p
             ''p'' := parent of p
 
     '''while''' (p ≠ NULL) '''do'''
         Slide_And_Increment(p)
 
     '''if''' (leaf_to_increment != NULL) '''then'''
         Slide_And_Increment(leaf_to_increment)

 '''function''' Slide_And_Increment(p) '''is'''
     previous_p := parent of ''p''
 
     '''if''' (p is an internal node) '''then'''
         Slide p in the tree higher than the leaf nodes of weight wt + 1
         increase weight of ''p'' by 1
         ''p'' := previous_p
     '''else'''
         Slide p in the tree higher than the internal nodes of weight wt
         increase weight of ''p'' by 1
         ''p'' := new parent of ''p''.

Encoder and decoder start with only the root node, which has the maximum number. In the beginning it is our initial NYT node.

When we transmit an NYT symbol, we have to transmit code for the NYT node, then for its generic code.

For every symbol that is already in the tree, we only have to transmit code for its leaf node.

====Example====

[[File:Adaptive Huffman Vitter.jpg|800px]]

Encoding "abb" gives 01100001 001100010 11.

Step 1:

Start with an empty tree.

For "a" transmit its binary code.

Step 2:

NYT spawns two child nodes: 254 and 255, both with weight 0. Increase weight for root and 255. Code for "a", associated with node 255, is 1.

For "b" transmit 0 (for NYT node) then its binary code.

Step 3:

NYT spawns two child nodes: 252 for NYT and 253 for leaf node, both with weight 0. Increase weights for 253, 254, and root. To maintain Vitter's invariant that all leaves of weight w precede (in the implicit numbering) all internal nodes of weight w, the branch starting with node 254 should be swapped (in terms of symbols and weights, but not number ordering) with node 255. Code for "b" is 11.

For the second "b" transmit 11.

For the convenience of explanation this step doesn't exactly follow Vitter's algorithm,<ref name=":0">{{cite web|url=http://www.cs.duke.edu/csed/curious/compression/adaptivehuff.html#tree |title=Adaptive Huffman Coding |publisher=Cs.duke.edu |access-date=2012-02-26}}</ref> but the effects are equivalent.

Step 4:

Go to leaf node 253. Notice we have two blocks with weight 1. Node 253 and 254 is one block (consisting of leaves), node 255 is another block (consisting of internal nodes). For node 253, the biggest number in its block is 254, so swap the weights and symbols of nodes 253 and 254. Now node 254 and the branch starting from node 255 satisfy the SlideAndIncrement condition<ref name=":0"/> and hence must be swapped. At last increase node 255 and 256's weight.

Future code for "b" is 1, and for "a" is now 01, which reflects their frequency.