Databases Reference
In-Depth Information
4.
A somewhat different approach to describing Huffman codes can be found in
Data
Compression—Methods and Theory
, by J.A. Storer [37].
5.
A more theoretical but very readable account of variable-length coding can be found in
Elements of Information Theory
, by T.M. Cover and J.A. Thomas [38].
6.
Although the topic
Coding and Information Theory
, by R.W. Hamming [5], is mostly
about channel coding, Huffman codes are described in some detail in Chapter 4.
3.10 Projects and Problems
1.
The probabilities in Tables
3.32
and
3.33
were obtained using the program
countalpha
from the accompanying software. Use this program to compare probabilities for different
types of text, C programs, messages on Internet forums, and so on. Comment on any
differences you might see and describe how you would tailor your compression strategy
for each type of text.
2.
Use the programs
huff_enc
and
huff_dec
to do the following (in each case use the
codebook generated by the image being compressed):
(a)
Code the Sena, Sensin, and Omaha images.
(b)
Write a program to take the difference between adjoining pixels, and then use
huffman
to code the difference images.
(c)
Repeat (a) and (b) using
adap_huff
.
Report the resulting file sizes for each of these experiments and comment on the differ-
ences.
3.
Using the programs
huff_enc
and
huff_dec
, code the Bookshelf1 and Sena images
using the codebook generated by the Sensin image. Compare the results with the case
where the codebook was generated by the image being compressed.
4.
A source emits letters from an alphabet
A
={
a
1
,
a
2
,
a
3
,
a
4
,
a
5
}
with probabilities
P
(
a
1
)
=
0
.
15,
P
(
a
2
)
=
0
.
04,
P
(
a
3
)
=
0
.
26,
P
(
a
4
)
=
0
.
05, and
P
(
a
5
)
=
0
.
50.
(a)
Calculate the entropy of this source.
(b)
Find a Huffman code for this source. Item(c)Find the average length of the code in
(b) and its redundancy.
A
={
a
1
,
a
2
,
a
3
,
a
4
}
(
a
1
)
=
.
(
a
2
)
=
.
5.
For an alphabet
with probabilities
P
0
1,
P
0
3,
(
a
3
)
=
.
(
a
4
)
=
.
P
0
25, and
P
0
35, find a Huffman code using the following:
(a)
The first procedure outlined in this chapter
(b)
The minimum variance procedure
Comment on the difference in the Huffman codes.
6.
In many communication applications, it is desirable that the number of 1s and 0s trans-
mitted over the channel be about the same. However, if we look at Huffman codes,
