Adaptive Huffman coding: Difference between revisions

Revision as of 05:56, 11 October 2004

Revision as of 21:50, 11 October 2004

Line 4:

==The algorithm==

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

Numbers go down, and from leftright to rightleft. so

Weights suffice '''sibling property''', if A is parent node of B and node C is child of B, then W(A)<W(B)<W(C).<br>

The weight is merely the count of symbols transmited which codes are associated with children of that node.<br>

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

Line 36 ⟶ 39:

Start with empty tree.

For '''"a"''' transmit it's binary code.

NYT spawns two child nodes 254 and 255.

Weight for root is now 1.

Now code for '''"a"''', associated with node 255 is 1.

For '''"b"''' transmit 0 for NYT node, then it's binary code.

NYT spawns two child nodes 252 for NYT and 253 for external node.

Increase weights for 253 and 254 and root.

For second '''"b"''' transmit 01.

Go to it's external node 253, we have a block of wights of 1-s and the biggest number in the block is 255, so swap the nodes, increase weght, go to root, increase weigth for root.

Future code for 'b' is 1.

Future code for 'a''"b"''' is now 011.

Future code for 'b''"a"''' is 1now 01.