Adaptive Huffman coding: Difference between revisions

Revision as of 13:15, 16 March 2016

Revision as of 18:17, 16 March 2016

Line 12:

===Vitter algorithm===

Some important terminologies & constraints :-

Code is represented as a tree structure in which every node has a corresponding weight and a unique number.

* '''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.

* '''Invariant''' : For each weight w, all leaves of weight w precedes all internal nodes having weight w.

Numbers go down, and from right to left.

* '''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.

Weights must satisfy the sibling property, which states that nodes must be listed in the order of decreasing weight with each node adjacent to its sibling. Thus if A is the parent node of B and C is a child of B, then <math>W(A) > W(B) > W(C)</math>.

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

The weight is merely the count of symbols transmitted which codes are associated with children of that node.

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

A set of nodes with same weights make a '''block'''.

=== '''Algorithm :-''' ===

To get the code for every node, in case of binary tree we could just traverse all the path from the root to the node, writing down (for example) "1" if we go to the right and "0" if we go to the left.

[[File:Leaf step one.png|thumb|'''Slide Method''' (leaf node): Slide_And_Increment(P) starts.

1. P is a leaf node.

]]

''leaf_to_increment'' = NULL

''P'' = pointer to symbol node

We need some general and straightforward method to transmit symbols that are "not yet transmitted" (NYT). We could use, for example, transmission of binary numbers for every symbol in alphabet.

'''''Step 1 :-'''''

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

If (P is NYT) THEN

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

''BEGIN'' 

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

[[File:Leaf step two.png|thumb|'''Slide Method''' (leaf node): Slide_And_Increment(P)

2. As P is leaf node, it slides in front of next block nodes of equal weight.

]]

extend P by adding two children.

Left child becomes new NYT and right child is the new symbol node.

For every symbol transmitted both the transmitter and receiver execute the update procedure:

      ''P'' = parent of new symbol node

# If current symbol is NYT, add two child nodes to NYT node. One will be a new NYT node, the other is a leaf node for our symbol. Increase weight for the new leaf node and the old NYT and go to step 4. If current symbol is not NYT, go to symbol's leaf node.

# If this node does not have the highest number in a block, swap it with the node having the highest number, except if that node is its parent<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 |date= |accessdate=2012-02-26}}</ref>

# Increase weight for current node

# If this is not the root node go to parent node then go to step 2. If this is the root, end.

      ''leaf_to_increment'' = Right Child of P.

Note: swapping nodes means swapping weights and corresponding symbols, but not the numbers. Notice that although the above description is excellent in capturing the principle of adaptive Huffman coding, it doesn't maintain Vitter's invariant that all leaves of weight w precede (in the implicit numbering) all internal nodes of weight w. See the example below for a more accurate explanation for Vittter'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 |date= |accessdate=2012-02-26}}</ref>.

''END''

Go to Step 3.

[[File:Leaf step three.png|thumb|'''Slide Method''' (leaf node) : Slide_And_Increment(P)

3. Here we increase the current weight by 1.

]]

'''''Step 2 :-'''''

Swap P with leader of its block.

If (new P is sibling to NYT) THEN

''BEGIN''

        ''leaf_to_increment'' = P

        ''P'' = parent of p.

[[File:Leaf step four.png|thumb|'''Slide Method''' (leaf node) : Slide_And_Increment(P)

4. Method comes to an end.

P is the new parent.

]]

''END''

'''''Step 3 :-'''''

[[File:Internal one.png|thumb|'''Slide Method''' (internal node) :- Slide_And_Increment(P)

1. P is a internal node.

]]

while (P is not Root)

[[File:Internal two.png|thumb|'''Slide Method''' (internal node): Slide_And_Increment(P).

2. Node P slides in front of next block of nodes, with weight wt+1.

]]

        ''Slide_And_Increment( P )''

'''Step 4 :-'''

If ( leaf_to_increment != NULL )

       ''Slide_And_Increment( P )''

'''PROCEDURE  ''Slide_And_Increment( P node ) :'''''

''BEGIN''

''previous_p'' = parent of p

''wt'' = weight of p

if ( p is Internal node )

[[File:Internal three.png|thumb|'''Slide Method''' (internal node) : Slide_And_Increment(P)

3. Now we increase the weight by 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 P in the tree higher than the leaf nodes of weight ''wt + 1.''

else

Slide P in the tree higher than the nodes of weight ''wt''.

''wt'' += 1

if ( p is internal node )

p = ''previous_p''

else

p = new parent of p.

''END''

[[File:Internal four.png|thumb|'''Slide Method''' (internal node) : Slide_And_Increment(P)

4. Now the 'P' points to the former parent ( as in the case of internal node according to algorithm)

]]

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====

Line 65 ⟶ 153:

For the second "b" transmit 11.

It should be noted that 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 |date=|publisher=Cs.duke.edu |date= |accessdate=2012-02-26}}</ref>, but the effects are equivalent.

Step 4: