Adaptive Huffman coding: Difference between revisions

Revision as of 00:58, 11 October 2004

Revision as of 05:56, 11 October 2004

Line 1:

'''Adaptive Huffman coding''' is an [[adaptive coding]] technique based on [[Huffman coding]], building the code as the symbols are being transmitted, that allows one-pass encoding ofand theadaptation messageto bychanging creatingconditions the codebook, as thein data. is being transmitted.

==The algorithm==

Line 25 ⟶ 26:

4. Increase weight for current node

45. If this is not the root node go to parent node, '''goto step 3'''<br>else end<br>

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

==Example==

[[Image:adaptive_huffman.png|Developing adapive Huffman tree]]

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 1-s and the biggest number in the block is 255, so swap the nodes, increase weght.

Future code for 'b' is 1.

Future code for 'a' is now 01.