Adaptive Huffman Coding – Update procedure
Example 3.4.1 Encoding message [a a r d v a r k], alphabet size – 26
Following codes are generated based on message to be encoded & alphabet size
a 00000
d 00011
k 01010
r 10001
v 1011
Total nodes possible: 2n-1 = 51
Root (Highest) node number = 51
Initially tree will have only one node NYT numbered 51 and weight
zero
a
Read Symbol : a
First Appearance of the Symbol? Yes
Send Code for NYT Node : NYT node is root, we don’t have code for root node
Send Index in the NYT List : Code for a 00000
Call update procedure
Update Procedure
First Appearance of the Symbol? Yes
NYT gives birth to new NYT and External node for ‘a’
Increment weight of external and Old NYT node. W(a/50) = 1, W(oldNYT/51)
=1 Goto old NYT node. No = 51
Root node? Yes
Stop
Is this the last symbol to read? No, continue...
Output till now 00000
aa
First Appearance of the Symbol? No
Code is the path from the root node to the corresponding node (a/50) :
1 Call update procedure
Update Procedure
First Appearance of the Symbol? No
Goto External node of the symbol. No = 50
Node number max in block? Yes (Block {50})
Increment node weight. W(a/50) = 2
Root node? No
Goto Parent node. No = 51
Node number max in block? Yes (Block {51})
Increment node weight. W(51) = 2
Root node? Yes Stop
Is this the last symbol to read? No, continue...
Output till now 00000 1
aar
Read Symbol : r
First Appearance of the Symbol? Yes
Send Code for NYT Node : NYT node is 49, Code 0
Send Index in the NYT List : Code for r 10001
Call update procedure
Update Procedure
First Appearance of the Symbol? Yes
NYT gives birth to new NYT and External node for ‘r’
Increment weight of external and Old NYT node. W(r/48) = 1, W(oldNYT/49) =1
Goto old NYT node. No = 49
Root node? No
Goto Parent node. No = 51
Node number max in block? Yes (Block {51,50})
Increment node weight. W(51) = 3
Root node? Yes Stop
Is this the last symbol to read? No, continue...
Output till now 00000 1 0 10001
aard
Read Symbol : d
First Appearance of the Symbol? Yes
Send Code for NYT Node : NYT node is 47, Code 00
Send Index in the NYT List : Code for d 00011
Call update procedure
Update Procedure
First Appearance of the Symbol? Yes
NYT gives birth to new NYT and External node for ‘d’
Increment weight of external and Old NYT node. W(d/46) = 1, W(oldNYT/47)
=1 Goto old NYT node. No = 47
Root node? No
Goto Parent node. No = 49
Node number max in block? Yes (Block {49, 48, 47, 46})
Increment node weight. W(49) = 2
Root node? No
Goto Parent node. No = 51
Node number max in block? Yes (Block {51})
Increment node weight. W(51) = 4
Root node? Yes Stop
Is this the last symbol to read? No, continue...
Output till now 00000 1 0 10001 00 00011
aardv
Read Symbol : v
First Appearance of the Symbol? Yes
Send Code for NYT Node : NYT node is 45, Code 000
Send Index in the NYT List : Code for v 1011
Call update procedure
Update Procedure
First Appearance of the Symbol? Yes
NYT gives birth to new NYT and External node for ‘v’
Increment weight of external and Old NYT node. W(v/44) = 1, W(oldNYT/45) =1
Goto old NYT node. No = 45
Root node? No
Goto Parent node. No = 47
Node number max in block? No (Block {48, 47, 46, 45, 44})
Switch node with highest numbered node in block. Switch with 48, ‘r’ will be 47, No
=48
Increment node weight. W(48) = 2
Root node? No
Goto Parent node. No = 49
Node number max in block? No (Block {50, 49, 48})
Switch node with highest numbered node in block. Switch with 50, ‘a’ will be 49, No
=50
Increment node weight. W(50) = 3
Root node? No
Goto Parent node. No = 51
Node number max in block? Yes (Block {51})
Increment node weight. W(51) = 5
Root node? Yes Stop
Is this the last symbol to read? No, continue...
Output till now 00000 1 0 10001 00 00011 000 1011
aardva
First Appearance of the Symbol? No
Code is the path from the root node to the corresponding node (a/49) : 0
Call update procedure
Update Procedure
First Appearance of the Symbol? No
Goto External node of the symbol. No = 49
Node number max in block? Yes (Block {49,48})
Increment node weight. W(a/49) = 3
Root node? No
Goto Parent node. No = 51
Node number max in block? Yes (Block {51})
Increment node weight. W(51) = 6
Root node? Yes Stop
Is this the last symbol to read? No, continue...
Output till now 00000 1 0 10001 00 00011 000 1011 0
Can you complete the rest of the message? i.e. r and k