Adaptive Huffman coding: Difference between revisions

Revision as of 01:57, 22 November 2019

Revision as of 10:26, 18 December 2019

Line 33:

[[File:Internal four.png|thumb|Slide_And_Increment(internal node) sliding step 4. Now the 'P' points to the former parent ( as in the case of internal node according to algorithm)]]

==== Algorithm '''algorithm''' for adding a symbol ===='''is'''

leaf_to_increment = NULL

p = pointer to the leaf node containing the next symbol

IF'''if''' (p is NYT) THEN'''then'''

Extend p by adding two children

Extend p by adding two children
Left child becomes new NYT and right child is the new symbol leaf node

''p'' = parent of new symbol leaf node

leaf_to_increment = Right Child of p

ELSE'''else'''

Swap p with leader of its block

IF'''if''' (new p is sibling to NYT) THEN'''then'''

leaf_to_increment = p

''p'' = parent of p

WHILE'''while''' (p != NULL) '''do'''

Slide_And_Increment(p)

IF (leaf_to_increment != NULL)

Slide_And_Increment(leaf_to_increment)

IF'''if''' (leaf_to_increment != NULL) '''then'''

Slide_And_Increment(leaf_to_increment)

==== Function '''function''' Slide_And_Increment(p) ===='''is'''

previous_p = parent of ''p''

IF (p is an internal node) THEN

'''if''' (p is an internal node) '''then'''
Slide p in the tree higher than the leaf nodes of weight wt + 1

increase weight of ''p'' by 1

''p'' = previous_p

ELSE'''else'''

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

increase weight of ''p'' by 1

''p'' = new parent of ''p''.

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