Databases Reference
In-Depth Information
packages from the previous step are merged with the list of items that consists of the individual
letters. This list is then sorted in order of increasing cost. After
l
max
−
1 iterations the lowest
cost 2
m
2 items are selected. The length of the codeword for each letter is equal to the
number of items containing that letter. As there are 2
m
−
−
2 items, each of which decrements
the Kraft-McMillan sum by 0.5, we end up with a set of lengths
{
l
i
}
such that
m
=
l
i
1
i
=
1
Example3.2.2:
Let us design a length-limited Huffman code for a source that puts out letters from an alphabet
A
={
a
1
,
a
2
,
a
3
,
a
4
,
a
5
,
a
6
}
with
P
(
a
1
)
=
0
.
05
,
P
(
a
2
)
=
0
.
1,
P
(
a
3
)
=
0
.
15,
P
(
a
4
)
=
3. The entropy for this source is 2.409 bits/symbol. Using the
standard Huffman procedure we can generate the code shown in Table
3.10
with an average
length
l
P
(
a
5
)
=
0
.
2, and
P
(
a
6
)
=
0
.
45. The longest codewords are four bits long. Let us design a code with the
added constraint that
l
max
=
=
2
.
3.
We begin with the list of letters. The costs are listed next to the letters:
L
0
=
[
a
1
(
0
.
05
),
a
2
(
0
.
1
),
a
3
(
0
.
15
),
a
4
(
0
.
2
),
a
5
(
0
.
2
),
a
6
(
0
.
3
)
]
We then proceed with the first packaging step. The packages are denoted by
a
jkl
(
where the
subscripts indicate the letters in the package and the quantity in the argument is the total cost
of the item. In the first packaging step we form packages by grouping the letters two-by-two
to form
p
)
]
We then merge these packages with our original list to get the merged list:
Package
1
:
[
a
12
(.
15
),
a
34
(.
35
),
a
56
(.
5
)
Merge
1
:
[
a
1
(
0
.
05
),
a
2
(
0
.
1
),
a
3
(
0
.
15
),
a
12
(
0
.
15
),
a
4
(
0
.
2
),
a
5
(
0
.
2
),
a
6
(
0
.
3
),
a
34
(
0
.
35
),
a
56
(
0
.
5
)
]
To get a code limited to three bits we need to go through one more iteration. In the next
packaging step we take the items in the previous merged list and group them two-by-two:
Package
2
:
[
a
12
(
0
.
15
),
a
312
(
0
.
3
),
a
45
(
0
.
4
),
a
634
(
0
.
65
)
]
T A B L E 3 . 10
Huffman code.
Letter
Probability
Codeword
a
1
0
.
05
0100
a
2
0
.
1
0101
a
3
0
.
15
011
a
4
0
.
2
10
a
5
0
.
2
11
a
6
0
.
3
00
