Adaptive Huffman coding: Difference between revisions

Revision as of 06:32, 17 March 2016

Revision as of 06:33, 17 March 2016

Line 13:

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

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

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

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

Line 25 ⟶ 24:

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

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

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

1. P is a leaf node.

Line 37 ⟶ 36:

If (P is NYT) THEN

''BEGIN'' 

[[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.

      ''P''  = parent of new symbol node

      ''leaf_to_increment''  = Right Child of P.

''END''

Line 63 ⟶ 62:

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

Line 81 ⟶ 80:

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

]]

        ''Slide_And_Increment( P )''

'''Step 4 :-'''

Line 87 ⟶ 86:

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 )

Line 101 ⟶ 100:

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

Line 133 ⟶ 132:

[[File:Adaptive Huffman Vitter.jpg]]

Encoding "abb" gives 01100001 001100010 11.

Step 1:

Line 153 ⟶ 152:

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 |publisher=Cs.duke.edu |date= |accessdate=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">{{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> and hence must be swop. 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.