《Data Compression》第五章

5

Statistical Methods

Statistical data compression methods employ variable-length codes, with the shorter

codes assigned to symbols or groups of symbols that appear more often in the data

(have a higher probability of occurrence). Designers and implementors of variable-

length codes have to deal with the two problems of (1) assigning codes that can be

decoded unambiguously and (2) assigning codes with the minimum average size. The

first problem is discussed in detail in Chapters 2 through 4, while the second problem

is solved in different ways by the methods described here.

calculate how redundancy is reduced, or even eliminated, by the various methods.

5.1 Shannon-Fano Coding

Shannon-Fano coding, named after Claude Shannon and Robert Fano, was the first

algorithm to construct a set of the best variable-length codes.

We start with a set of n symbols with known probabilities (or frequencies) of oc-

currence. The symbols are first arranged in descending order of their probabilities. The

set of symbols is then divided into two subsets that have the same (or almost the same)

probabilities. All symbols in one subset get assigned codes that start with a 0, while

the codes of the symbols in the other subset start with a 1. Each subset is then recur-

sively divided into two subsubsets of roughly equal probabilities, and the second bit of

seven-symbol alphabet. Notice that the symbols themselves are not shown, only their

probabilities.

Robert M. Fano was Ford Professor of Engineering, in

the Department of Electrical Engineering and Computer Sci-

ence at the Massachusetts Institute of Technology until his

retirement. In 1963 he organized MIT’s Project MAC (now

the Computer Science and Artificial Intelligence Laboratory)

and was its Director until September 1968. He also served as

Associate Head of the Department of Electrical Engineering

and Computer Science from 1971 to 1974.

received the Bachelor of Science degree in 1941 and the Doctor of Science degree in 1947,

both in Electrical Engineering from MIT. He has been a member of the MIT staff since

1941 and a member of its faculty since 1947.

During World War II, Professor Fano was on the staff of the MIT Radiation Lab-

oratory, working on microwave components and filters. He was also group leader of the

Radar Techniques Group of Lincoln Laboratory from 1950 to 1953. He has worked and

published at various times in the fields of network theory, microwaves, electromagnetism,

information theory, computers and engineering education. He is author of the book enti-

tled Transmission of Information, and co-author of Electromagnetic Fields, Energy and

Forces and Electromagnetic Energy Transmission and Radiation. He is also co-author

and three symbols (with total probability 0.25 and codes that start with 00). Step three

divides the last three symbols into 1 (with probability 0.1 and code 001) and 2 (with

total probability 0.15 and codes that start with 000).

The average size of this code is 0.25 ×2+0.20 ×2+0.15 ×3+0.15 ×3+0.10 ×3+

0.10 × 4+0.05 × 4=2.7 bits/symbol. This is a good result because the entropy (the

smallest number of bits needed, on average, to represent each symbol) is

0.25 log

0.25 + 0.20 log

0.20 + 0.15 log

2. 0.20 1 0 :10

3. 0.15 0 1 1 :011

4. 0.15 0 1 0 :010

5. 0.10 0 0 1 :001

6. 0.10 0 0 0 1 :0001

7. 0.05 0 0 0 0 :0000

and fourth symbols. Calculate the average size of the code and show that it is greater

than 2.67 bits/symbol.

with the minimum average size (zero redundancy). Its average size is 0.25 × 2+0.25 ×

to its entropy. This means that it is the theoretical minimum average size.

5.2 Huffman Coding

Being originally from Ohio, it is no wonder that Huffman went to Ohio State University

for his BS (in electrical engineering). What is unusual was his age

(18) when he earned it in 1944. After serving in the United States

Navy, he went back to Ohio State for an MS degree (1949) and then

to MIT, for a PhD (1953, electrical engineering).

That same year, Huffman joined the faculty at MIT. In 1967,

he made his only career move when he went to the University of

California, Santa Cruz as the founding faculty member of the Com-

and coding, signal designs for radar and communications, and design procedures for

asynchronous logical circuits. Of special interest is the well-known Huffman algorithm

for constructing a set of optimal prefix codes for data with known frequencies of occur-

rence. At a certain point he became interested in the mathematical properties of “zero

curvature” surfaces, and developed this interest into techniques for folding paper into

unusual sculptured shapes (the so-called computational origami).

Huffman coding is a popular method for data compression. It serves as the basis

for several popular programs run on various platforms. Some programs use just the

Huffman method, while others use it as one step in a multistep compression process.

The Huffman method [Huffman 52] is somewhat similar to the Shannon-Fano method.

compression.

Since its development in 1952 by D. Huffman, this method has been the subject of

intensive research in data compression. The long discussion in [Gilbert and Moore 59]

proves that the Huffman code is a minimum-length code in the sense that no other

encoding has a shorter average length. An algebraic approach to constructing the Huff-

man code is introduced in [Karp 61]. In [Gallager 74], Robert Gallager shows that the

redundancy of Huffman coding is at most p

is the probability of the

most-common symbol in the alphabet. The redundancy is the difference between the