Adaptive Huffman coding: Difference between revisions

Revision as of 02:31, 13 August 2016

Revision as of 02:33, 13 August 2016

Line 35:

==== Algorithm for adding a symbol ====

leaf_to_increment = NULL

Pp = pointer to the leaf node containing to the next symbol

IF (Pp is NYT) THEN

Extend P by adding two children

Left child becomes new NYT and right child is the new symbol leaf node

Pp = parent of new symbol leaf node

leaf_to_increment = Right Child of Pp

ELSE

Swap Pp with leader of its block

IF (new Pp is sibling to NYT) THEN

leaf_to_increment = Pp

Pp = parent of p

WHILE (Pp != NULL)

Slide_And_Increment(Pp)

IF (leaf_to_increment != NULL)

Slide_And_Increment(leaf_to_increment)

==== PROCEDURE Function Slide_And_Increment(Pp) ====

previous_p = parent of p

wt = weight of p

IF (p is an internal node)

Slide Pp in the tree higher than the leaf nodes of weight wt + 1

wt += 1

p = previous_p

ELSE

Slide Pp in the tree higher than the internal nodes of weight wt

wt += 1

p = new parent of p.