Databases Reference
In-Depth Information
T A B L E 3 . 27
The codebook after one
iteration.
Sequence
Probability
B
0.30
C
0.10
AA
0.36
AB
0.18
AC
0.06
T A B L E 3 . 28
A 3-bit Tunstall code.
Sequence
Code
B
000
C
001
AB
010
AC
011
AAA
100
AAB
101
AAC
110
3.8 Applications of Huffman Coding
In this section, we describe some applications of Huffman coding. As we progress through the
topic, we will describe more applications, since Huffman coding is often used in conjunction
with other coding techniques.
3.8.1 Lossless Image Compression
A simple application of Huffman coding to image compression would be to generate a Huffman
code for the set of values that any pixel may take. For monochrome images, this set usually
consists of integers from0 to 255. Examples of such images are contained in the accompanying
data sets. The four that we will use in the examples in this topic are shown in Figure
3.16
.
We will make use of one of the programs from the accompanying software (see Preface)
to generate a Huffman code for each image and then encode the image using the Huffman
code. The results for the four images in Figure
3.16
are shown in Table
3.29
. The Huffman
code is stored along with the compressed image as the code will be required by the decoder to
reconstruct the image.
The original (uncompressed) image representation uses 8 bits/pixel. The image consists
of 256 rows of 256 pixels, so the uncompressed representation uses 65,536 bytes. The com-
pression ratio is simply the ratio of the number of bytes in the uncompressed representation
to the number of bytes in the compressed representation. The number of bytes in the com-
pressed representation includes the number of bytes needed to store the Huffman code. Notice
that the compression ratio is different for different images. This can cause some problems in
