Adaptive Huffman coding: Difference between revisions

Revision as of 22:52, 10 October 2004

Revision as of 00:58, 11 October 2004

Line 1:

'''Adaptive Huffman coding''' is an [[adaptive coding]] technique based on [[Huffman coding]], that allows one-pass encoding of the message by creating the codebook, as the data is being transmitted.

== The algorithm ==

== 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 left to right so if A is parent node of B and node C is child of B, then A<B<C.<br>

Line 9 ⟶ 7:

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

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 straightforwad metod to transmit symbols which are '''not yet transmitted''' (NYT), we could use tranmission of binary numbers for every symbol in alphabet.<br>

We need some general and straightforwadstraightforward metodmethod to transmit symbols which are '''not yet transmitted''' (NYT), we could use tranmission of binary numbers for every symbol in alphabet.<br>

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 '''external node'''.

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

Line 32 ⟶ 27:

4. 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, batbut not the numbers.