Long before the invention of personal computers, the Internet, and mobile phones, at a time when letters were mostly transported by horse or occasionally by train, humans got their first taste of “instant communication” with the
invention of telegraphy in the middle of the 19th century. Not only did the telegraphy system revolutionize the speed of communication, it also pioneered many techniques that are still at the heart of our modern computer networks, most importantly the idea
of encoding information using electrical signals.
The telegraphy system was based on the Morse code shown in Fig. 9.1, which maps each letter of the Latin alphabet to a sequence of short and long electrical pulses that are separated by short delays. These codewords are then sent one after another, adding longer delays to form words and sentences. Other symbols such as digits and punctuation marks were not included in the original Morse code and had to be spelled out; for instance, the word
STOP was used to indicate the end of a sentence. To reduce the average time required to transmit telegrams, not all codewords have the same length: The Morse code uses short codewords for common letters such as E and T and long codewords for uncommon letters such as
Q and X.
.
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Figure 9.1 The Morse code translates letters of the Latin alphabet to codewords consisting of short and long electrical pulses. To reduce transmission time, common letters are encoded using short codewords and uncommon letters using long codewords.
Today, we use similar techniques to compress data that is transmitted over computer networks or stored on external devices such as hard drives. In fact, almost every piece of data you load from the Internet is compressed before it is sent over the network, and many file formats employ some form of data
compression to save memory. It’s not an exaggeration to say that the Internet in its current form as well as many other aspects of modern computing would be inconceivable without data compression. In this chapter and the next, we will discuss a few fundamental algorithms
for data compression and their implementations. Specifically, we will focus on algorithms that ensure that the data being compressed can be recovered exactly, down to the last bit. Such methods are also known as lossless compression algorithms.
Similar to the way the telegraph system used the Morse code to convert English text into electrical signals, modern computers use binary codes to translate information into long strings of ones and zeros that can be transmitted, stored, and processed digitally. The process of converting data to bits is conventionally referred to as encoding and recovering the data from the bits as decoding. Let’s take a look at a few ways to design such binary codes.
The simplest binary codes are so-called fixed-length codes in which all letters are mapped to bit sequences of the same length. An important example of such a code is ASCII, the American Standard Code for Information Interchange, which was first published in 1963 and remains the basis for most text-based file formats. ASCII specifies 7-bit codewords for a total of
128 characters, including the Latin alphabet, decimal digits, as well as a selection of punctuation marks and mathematical symbols.1
The full ASCII code is shown in Fig. 9.2. Each character has a numerical code between 0 and 127 that is computed by adding the hexadecimal numbers at the top and to the left of the table. Even though
7 bits would be sufficient to represent all 127 ASCII characters, the codewords are usually extended to 8 bits by setting the highest bit to 0. This makes it easier to process ASCII text on byte-based computers.
1 The lack of support for languages other than English is a major limitation of ASCII. In Exercise 9.14 we briefly discuss Unicode, the official standard for representing international text.
Example9.1. The ASCII encoding of “ABRACADABRA” can be found as follows. The letter ‘A’ is in the row labeled 40 and the column labeled 1, so its numerical value is the hexadecimal number 0x41. Looking up the codewords of the remaining ten characters in the same way, we obtain the following sequence of 11
hexadecimal numbers:
Each of these numbers is converted to binary to obtain the bit sequence for the character, so 0x41 becomes 00110001, 0x42 becomes 00110010, and so on. The result is the following sequence of 88 bits:
Figure 9.2 The ASCII standard uses numeric codes between 0 and 127 for a range of symbols and special characters. To find the code in this case, add the hexadecimal numbers in the first row and first column.
In addition to normal characters such as letters and digits, ASCII also defines codes for so-called control characters, which were originally used to control output devices such as printers and terminals. The symbols in the first two rows of Fig. 9.2 as well as the DEL symbol in the last row are control characters. Only a handful of the control characters are still in active use, the most important being HT (horizontal tabulator), which is used to indent lines in text files, as well as CR (carriage return) and LF (line feed), which are used to represent line endings.
Fixed-length codes like ASCII have the obvious advantage of being easy to encode and decode, but they lack flexibility. The obvious solution is to introduce variable-length codes in which not all codewords are required to have the same number of bits. Here is an example of a simple variable-length code:
.
symbol
A
B
R
C
D
codeword
0
10
11
110
001
We can use this code to encode the word “ABRACADABRA” by mapping each letter to the corresponding bit sequence:
.
A
B
R
A
C
A
D
A
B
R
A
0
10
11
0
110
0
001
0
10
11
0
The final encoding is therefore 0101101100001010110.
The problem with this code becomes clear as we try to recover the original message from the bit sequence. Let’s try to decode 0101101100001010110 to see what happens. The first three bits are 010, and it’s not hard to see that this bit sequence can only be obtained by concatenating the codewords of
A and B, so we can decode the first two letters “AB”. But the next three bits 110 are problematic since they can either stand for the two-letter sequence “RA” or the single letter C. At this point, we no longer no whether the original message started
with “ABRA” or “ABC”. As we will see in Exercise 9.4, there are 16 different ways of decoding the entire bit sequence. The code is said to be ambiguous.
Prefix Codes
How can we prevent such ambiguities? In other words, how can we ensure that every a bit sequence produced by a binary code can be decoded in exactly one way? One solution to this problem is based on the following observation: The root cause of the ambiguities in the previous example was that the
codewords for A and R (0 and 11) could also be interpreted as the first bits of the codewords for D and C (001 and 110). We say that the codewords for A and R are prefixes of the codewords for D and C, respectively.
More generally, a prefix is a sequence of characters that appears at the start of a string. For example, the word MARK is a prefix of MARKET since the entire word MARK appears at the start of MARKET, but it is not a prefix of
REMARK (it appears at the end, not the start) or MARTIAL (only the first three letters match).
What happens if no codeword is a prefix of another codeword? For example, we can make the code above prefix-free by modifying two of the offending codewords, for example by encoding A as 01 and C as 0001:
.
symbol
A
B
R
C
D
codeword
01
10
11
0001
001
We call binary codes in which no codeword is a prefix of another codeword prefix-free codes or simply prefix codes.
If we use this code to encode “ABRACADABRA” again, we now obtain the bit sequence
To decode this bit sequence, we again start by searching for the longest codeword that matches the start 011011. In this case, the only matching codeword is 01, so the first letter must be A. The remaining bit sequence is 101101…, and
again there is only one matching codeword, which we decode as B. We continue in this manner until we have split the entire bit sequence into codewords and decoded the original message:
.
00
10
11
01
0001
01
001
01
10
11
01
A
B
R
A
C
A
D
A
B
R
A
At no point during the decoding process do we encounter a situation where more than one codeword matches the start of the bit sequence.
It’s not hard to see that this is no coincidence and that prefix codes are always unambiguous. Consider the problem of decoding an arbitrary bit sequence generated using such a code. Since this bit sequence was generated by concatenating one or more codewords, there must be at least one codeword that matches the start of the sequence. But there also cannot be more than one matching codeword, since then the code wouldn’t be a prefix code. The first symbol can therefore be decoded unambiguously. By applying the same
reasoning to the remainder of the bit sequence, we see that the entire message can be decoded unambiguously.
The fact that two codewords in a prefix code never have the same prefix has another important consequence: There is a one-to-one correspondence between prefix codes and certain binary trees. For example, the
tree representation of the code
.
symbol
A
B
R
C
D
codeword
01
10
11
0001
001
is shown in Fig. 9.3. There is one leaf node for each of the symbols A, B, R, C, and D. Now follow the path from the root to each of the leaves and write down a 0 every time you move left and a 1 every time you move
right. The sequence of zeros and ones you obtain in this way is the codeword of the symbol stored in the leaf. For example, the letter A is reached by moving left and then right (codeword 01) and R is reached by moving twice to the right and once to the left (codeword 110). More
generally, if we are given any binary tree whose leaves are labeled with symbols, we can convert it into a prefix code by following the path from the root to each of the leaves.
Figure 9.3 Tree representation of a prefix code. Each symbol is stored in a leaf, and the path from the root determines the symbol’s codeword.
Conversely, given a prefix code, we can construct the corresponding binary tree by following the path for each codeword and creating nodes and leaves as necessary (see Exercise 9.7). This
direct correspondence between prefix code and binary trees is extraordinarily useful in practice and the basis of many algorithms that operate on prefix codes.
Exercises
Exercise 9.1.The ASCII code in Fig. 9.2 is defined in such a way that certain operations
are easy to perform.
a) Implement functions isDigit(), isLower(), and isUpper() that determine whether a given ASCII character is a decimal digit, a lower-case letter, or an upper-case letter.
b) Write a function toUpper() that takes an ASCII-encoded character and converts it to upper-case if possible and leaves it unchanged otherwise.
Exercise 9.2.One of the oldest and simplest encryption methods is the Caesar cipher, named after the Roman emperor Julius Caesar. In this cipher, every letter is replaced by another letter a fixed distance away, with letters at the end of the alphabet wrapping around. If we set the offset to \(3\), for instance, A
becomes D, B becomes E, …, and Z becomes C. Characters that aren’t letters between A and Z are left unchanged.
a) Explain how to encrypt and decrypt ASCII-encoded letters using the Caesar cipher. (See also Exercise 9.1.)
b) Jul vf guvf pvcure eneryl hfrq?
Exercise 9.3. When designing codes, it is often more efficient to group multiple letters into one symbol instead of encoding each letter individually. For example, using the
following code
.
symbol
AB
R
AC
AD
A
codeword
000
001
010
011
100
we can encode “ABRACADABRA” using merely 21 bits:
000001010011000001100.
Design a similar code that uses groups of at most two characters to encode the same string using fewer than 15 bits.
Exercise 9.4. We noted in the text that the bit sequence 0101101100001010110 has 16 different interpretations when trying to decode it with the ambiguous code
.
symbol
A
B
R
C
D
codeword
0
10
11
110
001
One of these interpretations is the original text “ABRACADABRA”. What are the other 15?
Exercise 9.5.Consider the following table of codewords:
.
symbol
A
B
R
C
D
codeword
1
001
101
01
000
Is this a prefix code? Sketch the binary tree associated with this code.
Exercise 9.6.A unary code encodes every nonnegative integer \(k\) as a sequence of \(k\) zeros followed by a single one; in other words, the numbers \(0, 1, 2, 3\) are encoded as \(\bits {1}, \bits {01}, \bits {001}, \bits {0001}\), and
so on. Now consider the code we obtain by reversing each codeword, so that the numbers \(0, 1, 2, 3\) are mapped to \(\bits {1}, \bits {10}, \bits {100}, \bits {1000}\). Which of these two codes is a prefix code, and which can be decoded unambiguously?