Adaptive Huffman coding: Difference between revisions

Revision as of 12:17, 16 March 2016

Revision as of 12:42, 16 March 2016

Line 39:

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

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

Note: swapping nodes means swapping weights and corresponding symbols, but not the numbers.

====Example: encoding "abb" gives 01100001 001100010 11====

[[File:Adaptive Huffman Vitter.jpg]]

Line 63:

For the second "b" transmit 11.

It should be noted that for the convenience of explanation this step is notdoesn't exactly followingfollow Vitter’sVitter'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. NowAt last increase node 255 and 256’s weight.

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