Databases Reference
In-Depth Information
T A B L E 3 . 4
The reduced two-letter
alphabet.
Letter
Probability
Codeword
a
3
0.6
α
3
a
2
0.4
c
(
a
2
)
T A B L E 3 . 5
Huffman code for the original
five-letter alphabet.
Letter
Probability
Codeword
a
2
0.4
1
a
1
0.2
01
a
3
0.2
000
a
4
0.1
0010
a
5
0.1
0011
a
3
)
=
α
2
. Therefore,
But
c
(
α
2
=
α
3
∗
0
which means that
c
(
a
3
)
=
α
3
∗
00
c
(
a
4
)
=
α
3
∗
010
011
Again we define a new alphabet, this time with only two letters
a
3
c
(
a
5
)
=
α
3
∗
and
a
2
.Here
a
3
is
composed of the letters
a
3
and
a
1
and has probability
P
a
3
)
=
a
3
)
+
(
P
(
P
(
a
1
)
=
0
.
6. We
now have Table
3.4
.
As we have only two letters, the codeword assignment is straightforward:
c
a
3
)
=
(
0
c
(
a
2
)
=
1
which means that
α
3
=
0, which in turn means that
c
(
a
1
)
=
01
c
(
a
3
)
=
000
c
(
a
4
)
=
0010
c
(
a
5
)
=
0011
The Huffman code is given by Table
3.5
. The procedure can be summarized as shown in
Figure
3.1
.
The average length for this code is
l
=
.
4
×
1
+
.
2
×
2
+
.
2
×
3
+
.
1
×
4
+
.
1
×
4
=
2
.
2 bits/symbol
