Databases Reference
In-Depth Information
we have adapted the Huffman tree at that level. We then turn our attention to the next level by
examining the parent node of the node whose weight was incremented to see if it has the largest
number in its block. If it does not, it is exchanged with the node with the largest number in the
block. Again, an exception to this is when the node with the higher node number is the parent
of the node under consideration. Once an exchange has taken place (or it has been determined
that there is no need for an exchange), the weight of the parent node is incremented. We then
proceed to a new parent node and the process is repeated. This process continues until the root
of the tree is reached.
If the symbol to be encoded or decoded has occurred for the first time, a new external node
with a weight of zero is assigned to the symbol and a new NYT node is appended to the tree.
Both the new external node and the new NYT node are offsprings of the old NYT node. We
increment the weight of the new external node by one. As the old NYT node is the parent of
the new external node, we increment its weight by one and then go on to update all the other
nodes until we reach the root of the tree.
Examp l e 3 . 4 . 1 : Update Procedure
Assume we are encoding the message [a a r d v a r k], where our alphabet consists of the 26
lowercase letters of the English alphabet.
The updating process is shown in Figure
3.13
. We begin with only the NYT node. The
total number of nodes in this tree will be 2
51, so we start numbering backwards
from 51 with the number of the root node being 51. The first letter to be transmitted is
a
.
As
a
does not yet exist in the tree, we send a binary code 00000 for
a
and then add
a
to the
tree. The NYT node gives birth to a new NYT node and a terminal node corresponding to
a
.
The weight of the terminal node will be higher than the NYT node, so we assign the number
49 to the NYT node and 50 to the terminal node corresponding to the letter
a
. The second
letter to be transmitted is also
a
. This time the transmitted code is 1. The node corresponding
to
a
has the highest number (if we do not consider its parent), so we do not need to swap
nodes. The next letter to be transmitted is
r
. This letter does not have a corresponding node
on the tree, so we send the codeword for the NYT node, which is 0 followed by the index
of
r
, which is 10001. The NYT node gives birth to a new NYT node and an external node
corresponding to
r
. Again, no update is required. The next letter to be transmitted is
d
, which
is also being sent for the first time. We again send the code for the NYT node, which is now
00 followed by the index for
d
, which is 00011. The NYT node again gives birth to two new
nodes. However, an update is still not required. This changes with the transmission of the
next letter,
×
26
−
1
=
, which has also not yet been encountered. Nodes 43 and 44 are added to the
tree, with 44 as the terminal node corresponding to
v
v
. We examine the grandparent node of
v
(node 47) to see if it has the largest number in its block. As it does not, we swap it with
node 48, which has the largest number in its block. We then increment node 48 and move to
its parent, which is node 49. In the block containing node 49, the largest number belongs to
node 50. Therefore, we swap nodes 49 and 50 and then increment node 50. We then move to
the parent node of node 50, which is node 51. As this is the root node, all we do is increment
node 51.
