© Copyright 1998 The Perl Journal. Reprinted with permission.
You are probably familiar with Unix
utilities, or the DOS
pkzip utility. These programs all make files smaller; we say that such files are compressed. Compressed files take less disk space and less network bandwidth. The
downside of compressed files is that it they are full of unreadable
gibberish; you usually have to run another program to uncompress them before you can use them again. In this article we'll see how file
compression works, and I'll show a simple module that includes functions
for compressing and uncompressing files.
The idea behind data compression is very simple. In a typical file, say a
text file, every character takes up the same amount of space: 8 bits. The
e is represented by the 8 bits 01100101; the letter Z is represented by the 8
bits 010101010. But in a text file,
e occurs much more frequently than
Z---maybe about 75 times as frequently. If you could give the common symbols
short codes and the uncommon symbols long codes, you'd have a net gain.
This isn't a new idea. It was exploited by Samuel Morse in the Morse Code, a very early digital data transmission protocol. Morse Code was designed to send text files over telegraph wires. A telegraph is very simple; it has a switch at one end, and when you close the switch, an electric current travels through a wire to the other end, where there is a relay that makes a click. By tapping the switch at one end, you make the relay at the other end click. Letters and digits are encoded as sequences of short and long clicks. A short click is called a dot, and a long click is called a dash.
The two most common letters in English text are
T; in Morse code these are represented by a single dot and a single dash,
respectively. The codes for
M, all common letters, are
--. In contrast, the codes for the uncommon letters
In computer file compression, we do a similar thing. We analyze the contents of the data, and figure out which symbols are frequent and which are infrequent. Then we assign short codes to the frequent symbols and long codes to the infrequent symbols. We write out the coded version of the file, and that usually makes it smaller.
There's a problem with Morse Code: You need a third symbol, typically a
long pause, to separate the dots and dashes that make up one letter from
the dats and dashes that make up the next. Otherwise, if you get
*-, you don't know whether it's the single letter
A or the two letters
ET---or it might be the first bit of the letter
L. In a long message, all the dots and dashes run together and you get a big
mess that can't be turned back into text. In Morse code, it can be hard to
tell `Eugenia' from `Sofia': Without the interletter pauses, they're both:
Those interletter spaces take up a lot of transmission time, and it would be nice if you didn't need them. It turns out that if you arrange the code properly, you don't. The ambiguity problem with Morse Code occurs because some codes are prefixes of others: There are some letters where the code for the first part of one letter is just the same as the code for the other letter, but with something extra tacked on. When you see the shorter code, you don't know if it's complete or if it should be combined with the following symbols. It turns out that if no code is a prefix of any other, then the code is unambiguous.
Suppose for simplicity that we only needed to send the letters A, C, E, and S over the telegraph. Instead of Morse code, we could use the following code table:
A - C ** E *-* S *--
Suppose we receive the message
was the message? Well, the first symbol is
-, so the
first letter in the message must be
A, because that's the
only letter with a code that starts with a
-. Then the
next two symbols are
**, so the second letter must be a
C, because all the other codes that start with
* have a
- after the
*. Similar reasoning shows that the third
letter is also
C. After that, the code is
*-*; it must be an
E. We continue through
the message, reading off one letter at a time, and eventually we get
the whole thing this way.
It's so simple that a computer can decode it, if the computer is equipped with a decision tree like this one:
Start at Start, and look at the symbols in the message one by one. At each stage, follow the appropriate labelled branch to the next node. If there's a letter at that node, output the letter and go back to the start node. If there's no letter at the node, look at the next symbol in the input and continue down the tree towards the leaves.
Obviously, it's important to choose the right code. If Morse had made
* code for
E, he wouldn't be famous.
Choosing the right code can be tricky. Consider the example of the
previous section, where we only had to code messages that contain
The code I showed is good when we expect our messages to contain more
S were very common, we clearly could have done better;
less clearly, if all four letters were about equally common, then we
could still have done better, by assigning each letter a code of the
Suppose, for example, our message happened to contain 200 of each of the four letters. Then the first code would use 1800 symbols, and the second code would use only 1600.
In 1952, David Huffman discovered a method for producing the
optimal unambigous code. For a given set of symbols, if you
know the probability with which each symbol appears in the input, you
can use Huffman's method to construct an unambiguous code that encodes
the typical message with fewer
-'s than any other code.
The method is very simple and ingenious. For concreteness, let's suppose that the (rather silly) message is
_ instead of space so that it'll be easier to see.)
Start with the table of relative probabilities; you can get this by counting the number of occurrences of every symbol in the message. This is called histogramming. (A histogram is a bar chart; histos is Greek for a beam or a mast.) Here's the histogram for the symbols in our sample message:
Now take the two least common entries in the table, that's
R. They'll get the longest codes,
because they're least common. We'll simplify this by pretending that
R are the same, and lumping them
together into one category, which we'll call
we'll assign codes to all the other letters and to
HR. When we're done, we still have to distinguish between
HR has some
code. We don't know what it is yet, so let's symbolize it with
<HR>. We don't really need to use
<HR> in our message, because the is no such thing
as the letter
HR, so we'll split it in two, and let the
<HR>* and the code for
<HR>-. As a result of this, the
R will be longer than the
codes for the other letters, but if that has to appen, it's better for
it to happen for
R, because they are
the least common letters in the message.
So we will lump
R together and pretend temporarily that they are only
one letter. Our table then looks like this:
S 11 R = <HR>- T 10 H = <HR>* HR 8 E 7 _ 6 I 5
Now we repeat the process. The two least common symbols are
_. We'll lump them together into a new
I_, we'll assign finish assigning the
I_. When we're done,
will get the code
_ will get
S 11 R = <HR>- I_ 11 H = <HR>* T 10 _ = <I_>- HR 8 I = <I_>* E 7
Then we lump together
HRE 15 R = <HR>- S 11 H = <HR>* I_ 11 _ = <I_>- T 10 I = <I_>* HR = <HRE>- E = <HRE>*
Then we lump together
I_T 21 R = <HR>- HRE 15 H = <HR>* S 11 _ = <I_>- I = <I_>* HR = <HRE>- E = <HRE>* I_ = <I_T>- T = <I_T>*
Then we lump together
SHRE 25 R = <HR>- I_T 21 H = <HR>* I = <I_>- _ = <I_>* HR = <HRE>- E = <HRE>* I_ = <I_T>- T = <I_T>* S = <SHRE>- HRE = <SHRE>*
Now we only have two `symbols' left. There's only one way to assign a
code to two symbols; one of them gets
* and the other
-. It doesn't matter which gets which, so let's say
Now the codes fall out of the table we've built up in the right-hand column:
SHRE = * S = *- HRE = ** HR = **- R = **-- H = **-* E = *** I_T = - I_ = -- _ = --- I = --* T = -*
We throw away the codes for the fictitious compound symbols, and we're left with the real code:
S = *- T = -* E = *** _ = --- I = --* H = **-* R = **--
As promised, the code is unambiguous, because no code is a prefix of any other code. Our original message encodes like this:
-***-****----***-*--***--*--*--*****--*--- *---**--******--*-----*******-***-*--- **--****---**--*----***-*--**---- *--***--****-*-
For a total of 128
-'s, an average of 2.72 symbols per character,
and a 9.3% improvement over the 141 symbols we would have had to use if we
had given every letter a three-symbol code.
For this article, I implemented a demonstration module that compresses
files. You can retrieve it from the perl Journal web site at http://www.tpj.com/ or from my Perl
Paraphernalia web site at http://www.plover.com/~mjd/perl/Huffman/.
compresses an input and saves it to the file
/tmp/htest.out; then it opens this file, reads in the compressed data, decompresses it,
and prints the result to standard output.
Most of the real work is in the
Huffman module that
htest uses. Here are the important functions that
my $hist = Huffman::histogram(\@symbols);
This generates the histogram of the input text. The histogram is the tally
of the number of occurrences of each symbol. The argument to
histogram is an array of symbols, passed by reference for efficiency, because it is
likely to be very large. It might have been simpler to pass the input as a
single string, but this way we can assign codes per-word instead of
per-character if we want to, just by splitting the input into an array in a
my $codes = Huffman::tabulate($hist);
tabulate function generates the code table from thie histogram using Huffman's
method. (This has the side effect of destroying the histogram.) The code
table is just a hash that maps symbols to codes; the codes themselves are
This writes the code table to the file.
Huffman::encode(*FILE, $codes, \@symbols);
This encodes the input text and writes the result to the file.
my $codes = Huffman::load_code_table(*FILE); my $coded_data = <FILE>; my $text = Huffman::decode($codes, $coded_data);
This is the decompression process. The return value from
load_code_table is a code table in a rather interesing form. It's a decision tree, just
like the ones we saw earlier in the article. Each node of the tree is
either a single string (which is the symbol that the decoder should output)
or it's an array with two elements; the 0th element is the part of the tree
on the branch labeled 0, and the 1st element is the part of the tree on the
branch labeled 1. For example, taking
* as equivalent to 0 and
equivalent to 1, the decision tree from earlier in the
article would be represented like
[[C, [E, S ] ], A ]
We can compress the file, but unless we include the code table in the
compressed file, we won't be able to uncompress it again. Files that
can't be uncompressed are not very useful. (Sometimes you don't need
to be able to decompress the file; in these cases the Perl
unlink function implements a much simpler and more
efficient form of compression.) But sometimes the code table is
bigger than the savings that we got from compressing the file,
especially if the original file is small. On a sample file of
comp.lang.perl.misc articles, the compressor reduced the file
size by 32%, from 42733 bytes to 29114. But when I ran it on its own
source code, the file size increased from 987 bytes to 1321. The
compressed data was only 631 bytes long, but the code table and other
overhead took up 690 bytes.
Huffman coding is optimal in the sense of compressing a given set of symbols into the smallest space possible. But if you readjust your idea of a `symbol', you can get must better compression.
Suppose you're compressing English text. If you histogram the characters, and use Huffman's method, you'll get the optimal way to encode the characters. Because each character has its own code, your code would also serve to code arbitrary random gibberish. It should be clear that this expressiveness has a price. For English text, we don't need so much expressiveness; it's clearly more efficient to assign a code to each word instead of to each character. In doing so, we lost the ability to encode random gibberish, but our compressed data becomes much smaller. Suppose there are about 2**17 words in English; if we assign each one a different 17-bit code, we can then encode our original seven-word message:
THE THIRSTIEST SISTERS TEETH RESIST THIS STRESS
into 7*17 = 119 bits, alreasy an improvement on the 128 we used before. And if we use Huffman's method to assign long codes to rare words and short codes to common words, we can do even better.
Using this method, I compressed the comp.lang.perl.misc articles by 63%. Unfortunately, the code table blew up as a result, and took up 43739 bytes, which was larger than the original uncompressed data.
Most modern data compression doesn't use Huffman coding directly. A better method was proposed in 1977 and 1978 by Jakob Ziv and Abraham Lempel. The Lempel-Ziv methods scan the input data, and when they find a substring that occurs twice, the replace the second occurrence with a reference back to the first. The references can then be Huffman-compressed.
These methods have several advantages over the basic scheme I implemented. One important benefit of Lempel-Ziv compression methods is that they don't have to read and analyze the entire input in advance; they can construct a code table as they go along, basing it on only the portion of the input seen so far. This is important for practical applications. The data compression in your modem wouldn't be very useful if the modem had to gather and analyze a week's worth of traffic before it could send or receive anything.
Another benefit of this method is that because the code table is imlpicit in the input seen so far, the code table doesn't need to be recorded explicitly. The decoding process can infer the code table from the coded data itself. This avoids the embarrassing inflamations that we saw where the code table took up more space than was actually saved by the compression process.
One extra payoff of building the code table on the fly is that if
the algorithm notices that the code table it's using isn't performing
well, it can throw it away and start over in the middle. If the data
is in several pieces that have very different characters, say a
graphic image embedded in a text file, this method will be a win over
straight Huffman coding because it'll be able to apply an appropriate
code table to each part of the data. LZW, the compression algorithm
used by the DOS
lha program, doesn't do this, but the
variation of it employed by the Unix
does. The algorithm used by the GNU project's
zlib is different but also periodically throws away the
code tables and starts over.
The best thing about Lempel-Ziv and related methods is that they don't need to decide in advance how to break up the input into symbols. LZW, for example, puts any string that it hasn't seen before into the code table, under the assumption that if it appeared once, it'll probably appear again. As the input comes in, longer and longer substrings of the input go into the code table; long substrings go in only when their shorter prefixes have appeared multiple times. This means that if the file is best broken up into words, the algorithm will eventually detect that; if it is best broken up into single characters, the algorithm will detect that too.
If you want an easy but possibly amusing project, try altering the code table functions in the module so that the code tables are smaller. At present, the module does not assume that the coding is done per-character, so you shouldn't break that.
Actually, though, assigning the codes per-word seems to blow up the code table more than it saves. I haven't found a case yet where it's worthwhile. I'd be interested in seeing more analysis of this.
Finally, the decision-tree data structure in the decoder is probably over-clever. It would be simpler to represent the same information with a state table, this way:
0 1 -------------------- 0 1 A 1 C 2 2 E S
Each internal node in the decision tree is assigned a state, which is a number; the root node gets the number 0. To decode, the decoder keeps track of the state number, which says what internal node it's currently at. Each time it reads a bit, it looks in the table to decide where to go next. If it sees a symbol, that means it erached a leaf, and should output that symbol and start over at state 0; if it sees a number, that means it's now at a different internal node and should read more bits. I'm really not sure whether this would be more efficient than the way I did do it, but it would probably be easier to understand.
Symbols, Signals, and Noise, J.R. Pierce, pp. 94--97. Harper, New York, 1961.
The comp.compression FAQ, is an excellent starting source of information, especially part 2. It is available from ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/.
My column finally has a name! Bricolage is a hot word these days in the computer learning business; it's French for tinkering or pottering. Thanks to Deven Ullman, who suggested it, and to the other people who suggested other names.
Return to: Universe of Discourse main page | What's new page | Perl Paraphernalia| File Compression Page