Databases Reference
In-Depth Information
START
Read in symbol
Is this
the first
appearance
of the
symbol?
Yes
No
Send code for NYT
node followed by
index in the NYT list
Code is the
p
ath from
the root node to the
corresponding node
Call update
procedure
No
Is this the
last symbol?
Yes
STOP
F I GU R E 3 . 14
Flowchart of the encoding procedure.
Examp l e 3 . 4 . 2 : Encoding Procedure
In Example 3.4.1we used an alphabet consisting of 26 letters. In order to obtain our prearranged
code, we have to find
m
and
e
such that 2
e
2
e
. It is easy to see that
+
r
=
26, where 0
r
<
the values of
e
10 satisfy this requirement.
The first symbol encoded is the letter
a
.As
a
is the first letter of the alphabet,
k
=
4 and
r
=
=
1.
As 1 is less than 20,
a
is encoded as the 5-bit binary representation of
k
1, or 0, which is
00000. The Huffman tree is then updated as shown in the figure. The NYT node gives birth
to an external node corresponding to the element
a
and a new NYT node. As
a
has occurred
once, the external node corresponding to
a
has a weight of one. The weight of the NYT node
is zero. The internal node also has a weight of one, as its weight is the sum of the weights
−
