Databases Reference
In-Depth Information
Condition 4:
Suppose we change an intermediate node into a leaf node by combining
all of the leaves descending from it into a composite word of a reduced alphabet. Then, if
the original tree was optimal for the original alphabet, the reduced tree would be optimal
for the reduced alphabet.
If this condition were not satisfied, we could find a code with a smaller average code length
for the reduced alphabet and then simply expand the composite word again to get a new code
tree that would have a shorter average length than our original “optimum” tree. This would
contradict our statement about the optimality of the original tree.
In order to satisfy conditions 1, 2, and 3, the two least probable letters would have to be
assigned codewords of maximum length
l
m
. Furthermore, the leaves corresponding to these
letters arise from the same intermediate node. This is the same as saying that the codewords for
these letters are identical except for the last bit. Consider the common prefix as the codeword
for the composite letter of a reduced alphabet. Since the code for the reduced alphabet needs
to be optimum for the code of the original alphabet to be optimum, we follow the same
procedure again. To satisfy the necessary conditions, the procedure needs to be iterated until
we have a reduced alphabet of size one. But this is exactly the Huffman procedure. Therefore,
the necessary conditions above, which are all satisfied by the Huffman procedure, are also
sufficient conditions.
3.2.5 Length of Huffman Codes
We have said that the Huffman coding procedure generates an optimum code, but we have not
said what the average length of an optimum code is. The length of any code will depend on a
number of things, including the size of the alphabet and the probabilities of individual letters.
In this section, we will show that the optimal c
od
e for a source
S
, and hence the Huffman code
for the source
, has an average code length
l
bounded below by the entropy and bounded
above by the entropy plus 1 bit. In other words,
S
1
(1)
In order for us to do this, we will need to use the Kraft-McMillan inequality introduced
in Chapter 2. Recall that the first part of this result, due to McMillan, states that if we have a
uniquely decodable code
H
(S)
l
<
H
(S)
+
K
i
C
with
K
codewords of length
{
l
i
}
1
, then the following inequality
=
holds:
K
2
−
l
i
(2)
1
i
=
1
Example3.2.3:
Examining the code generated in Example
3.2.1
(Table
3.5
), the lengths of the codewords are
{
1
,
2
,
3
,
4
,
4
}
. Substituting these values into the left-hand side of Equation (
2
), we get
2
−
1
2
−
2
2
−
3
2
−
4
2
−
4
+
+
+
+
=
1
which satisfies the Kraft-McMillan inequality.
