Adaptive Huffman coding: Difference between revisions

Revision as of 08:50, 13 October 2004

Revision as of 14:25, 13 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, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data. <br>

The benefit of one-pass procedure is that the sorce can be encoded realtime, though it becomes more sensitive to transmission errors, since single loss ruins the whole tree.

==The algorithmAlgoritms==

There exists a number of implementaions of this method, the most notable are '''FGK''' (Faller-Gallager-Knuth)and '''Vitter''' algorithm.

===Vitter 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 right to left.

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>

Line 13 ⟶ 20:

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.

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

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

When we transmit an NYT symbol we have to transmit code for NYT node then it's generic code.

For every symbol which already in the tree we only have to transmit code for it's '''externalleaf node'''.

For every symbol transmitted on both sides we must execute '''update procedure''':

1. If current symbol is NYT, add two child nodes to NYT node, one will be a new NYT node the other is externalleaf node for our symbol, increase weight for new externalleaf node and old NYT, '''goto step 4''' <br>

'''else'''<br>

go to symbols externalleaf node.

3. If this node does not have the highest number in a block swap it with which has the highest number

Line 33 ⟶ 40:

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

====Example====

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

Line 48 ⟶ 55:

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

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

Increase weights for 253 and 254 and root.

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

Go to it's externalleaf node 253, we have a block of wights of 1 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"''' is now 01.

== External links ==

[http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html University of California Dan Hirschberg site]

[http://www.cs.cf.ac.uk/Dave/Multimedia/node212.html Cardiff University Dr. David Marshall site]

[[Category:Lossless compression algorithms]]