Databases Reference
In-Depth Information
1
2
3
51
51
51
NYT
0
51
NYT
0
1
a
NYT
0
2
a
1
49
2
a
49
50
49
50
50
(a)
(aa)
YN0
1
r
47
48
(aar)
4
4
51
51
2
a
2
a
2
2
50
50
49
49
1
r
1
1
r
1
48
48
47
NYT
47
1
d
1
0
1
d
46
45
45
46
YN0
1
v
(aard)
43
44
(aardv)
4
5
51
51
2
3
2
a
a
2
49
50
2
1
r
2
r
1
48
47
1
1
d
1
d
1
45
46
NYT
NYT
0
1
v
0
1
v
43
44
(aardv)
(aardv)
F I GU R E 3 . 13
Adaptive Huffman tree after [a a r d v] is processed.
3.4.2 Encoding Procedure
The flowchart for the encoding procedure is shown in Figure
3.14
. Initially, the tree at both the
encoder and decoder consists of a single node, the NYT node. Therefore, the codeword for
the very first symbol that appears is a previously agreed-upon fixed code. After the very first
symbol, whenever we have to encode a symbol that is being encountered for the first time, we
send the code for the NYT node, followed by the previously agreed-upon fixed code for the
symbol. The code for the NYT node is obtained by traversing the Huffman tree from the root
to the NYT node. This alerts the receiver to the fact that the symbol whose code follows does
not as yet have a node in the Huffman tree. If a symbol to be encoded has a corresponding
node in the tree, then the code for the symbol is generated by traversing the tree from the root
to the external node corresponding to the symbol.
To see how the coding operation functions, we use the same example that was used to
demonstrate the update procedure.
