Databases Reference
In-Depth Information
Huffman Coding
3.1 Overview
In this chapter we describe a very popular coding algorithm called the Huffman
coding algorithm. We first present a procedure for building Huffman codes
when the probability model for the source is known, and then we introduce a
procedure for building codes when the source statistics are unknown. We also
describe a few techniques for code design that are in some sense similar to the
Huffman coding approach. Finally, we give some examples of using the Huffman code for
image compression, audio compression, and text compression.
3.2 The Huffman Coding Algorithm
This technique was developed by David Huffman as part of a class assignment; the class was
the first ever in the area of information theory and was taught by Robert Fano at MIT [
16
]. The
codes generated using this technique or procedure are called
Huffman codes
. These codes are
prefix codes and are optimum for a given model (set of probabilities).
The Huffman procedure is based on two observations regarding optimum prefix codes.
1.
In an optimum code, symbols that occur more frequently (have a higher probability of
occurrence) will have shorter codewords than symbols that occur less frequently.
2.
In an optimum code, the two symbols that occur least frequently will have the same
length.
