Databases Reference
In-Depth Information
START
First
appearance
for symbol?
NYT gives birth
to new NYT and
external node
Ye s
No
Increment weight
of external node
and old NYT node
Go to symbol
external node
Go to old
NYT node
Node
number max
in block?
Switch node with
highest numbered
node in block
No
Ye s
Increment
node weight
Is this
the root
node?
No
Go to
parent node
Ye s
STOP
F I GU R E 3 . 12
Update procedure for the adaptive Huffman coding algorithm.
tree at the transmitter is updated after each symbol is encoded, and the tree at the receiver is
updated after each symbol is decoded. The procedure operates as follows.
After a symbol has been encoded or decoded, the external node corresponding to the symbol
is examined to see if it has the largest node number in its block. If the external node does not
have the largest node number, it is exchanged with the node that has the largest node number
in the block, as long as the node with the higher number is not the parent of the node being
updated. The weight of the external node is then incremented. If we did not exchange the
nodes before the weight of the node was incremented, it is very likely that the ordering required
by the sibling property would be destroyed. Once we have incremented the weight of the node,
