Adaptive Huffman coding: Difference between revisions

Revision as of 18:12, 13 October 2004

Revision as of 16:06, 14 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 just a single loss ruins the whole code.

Line 7:

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

===VitterFGK algorithm===

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

Line 13:

Weights must suffice '''sibling property''', that is what nodes can be listed in order of nonincreasing weight with each node adjacent to its sibling. Thus if A is parent node of B and node C is child of B, then <math>W(A)>\ge W(B)>\ge W(C)</math>.<br />

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

Line 62:

Go to it's leaf 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, and for '''"a"''' is now 01, which reflects their frequency.

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

== External links ==