Adaptive Huffman coding: Difference between revisions

Revision as of 21:17, 19 July 2016

Revision as of 02:31, 13 August 2016

Line 24:

'''NYT(Not Yet Transferred)''' is special node and used to represents symbols which are ''<nowiki/>'not yet transferred'''.

[[File:Leaf step one.png|thumb|Slide_And_Increment(leaf node) sliding starts. P is a leaf node.]]

==== Algorithm :- ====

[[File:Leaf step onetwo.png|thumb|'''Slide Method''' Slide_And_Increment(leaf node): Slide_And_Increment(sliding step 2. As P) startsis leaf node, it slides in front of next block nodes of equal weight.]]

[[File:Leaf step three.png|thumb|Slide_And_Increment(leaf node) sliding step 3. Here we increase the current weight by 1.]]

1. P is a leaf node.

[[File:Leaf step four.png|thumb|Slide_And_Increment(leaf node) sliding step 4. Method comes to an end. P is the new parent.]]

]]

[[File:Internal one.png|thumb|Slide_And_Increment(internal node) sliding starts. P is an internal node.]]

''leaf_to_increment'' = NULL

[[File:Internal two.png|thumb|Slide_And_Increment(internal node) sliding step 2. Node P slides in front of next block of nodes, with weight wt+1.]]

[[File:Internal three.png|thumb|Slide_And_Increment(internal node) sliding step 3. Now we increase the weight by 9. Thus the '''''invariant is maintained''''' as the current node is an internal node and should occur in front of leaf nodes of equal weight as we have increased the weight. ]]

[[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)]]

''P'' ==== pointerAlgorithm tofor adding a symbol node====

leaf_to_increment = NULL

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

IF (P is NYT) THEN

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

Swap P with leader of its block

IF (new P is sibling to NYT) THEN

leaf_to_increment = P

P = parent of p

WHILE (P != NULL)

Slide_And_Increment(P)

IF (leaf_to_increment != NULL)

Slide_And_Increment(leaf_to_increment)

==== PROCEDURE Slide_And_Increment(P) ====

'''''Step 1 :-'''''

previous_p = parent of p

wt = weight of p

If (P is NYT) THEN

IF (p is an internal node)

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

''BEGIN''

wt += 1

[[File:Leaf step two.png|thumb|'''Slide Method''' (leaf node): Slide_And_Increment(P)

p = previous_p

2. As P is leaf node, it slides in front of next block nodes of equal weight.

ELSE

]]

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

extend P by adding two children.

wt += 1

Left child becomes new NYT and right child is the p = new symbolparent of nodep.

''P'' = parent of new symbol node

''leaf_to_increment'' = Right Child of P.

''END''

Go to Step 3.

[[File:Leaf step three.png|thumb|'''Slide Method''' (leaf node) : Slide_And_Increment(P)

3. Here we increase the current weight by 1.

]]

'''''Step 2 :-'''''

Swap P with leader of its block.

If (new P is sibling to NYT) THEN

''BEGIN''

''leaf_to_increment'' = P

P = parent of p.[[File:Leaf step four.png|thumb|'''Slide Method''' (leaf node) : Slide_And_Increment(P)

4. Method comes to an end.

P is the new parent.

]]

''END''

'''''Step 3 :-'''''

[[File:Internal one.png|thumb|'''Slide Method''' (internal node) :- Slide_And_Increment(P)

1. P is an internal node.

]]

while (P != NULL)

[[File:Internal two.png|thumb|'''Slide Method''' (internal node): Slide_And_Increment(P).

2. Node P slides in front of next block of nodes, with weight wt+1.

]]

''Slide_And_Increment( P )''

'''Step 4 :-'''

If ( leaf_to_increment != NULL )

''Slide_And_Increment( leaf_to_increment )''

'''PROCEDURE ''Slide_And_Increment( P node ) :'''''

''BEGIN''

''previous_p'' = parent of p

''wt'' = weight of p

if ( p is Internal node )

[[File:Internal three.png|thumb|'''Slide Method''' (internal node) : Slide_And_Increment(P)

3. Now we increase the weight by 9. Thus the '''''invariant is maintained''''' as the current node is an internal node and should occur in front of leaf nodes of equal weight as we have increased the weight.

]]

Slide P in the tree higher than the leaf nodes of weight ''wt + 1.''

else

Slide P in the tree higher than the nodes of weight ''wt''.

''wt'' += 1

if ( p is internal node )

p = ''previous_p''

else

p = new parent of p.

''END''

[[File:Internal four.png|thumb|'''Slide Method''' (internal node) : Slide_And_Increment(P)

4. Now the 'P' points to the former parent ( as in the case of internal node according to algorithm)

]]

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

Line 129 ⟶ 71:

====Example====

[[File:Adaptive Huffman Vitter.jpg|800px]]

Encoding "abb" gives 01100001 001100010 11.