Huffman coding , which we discussed in the previous chapter, can be used to compress almost any kind of data: The only requirement is that the data consists of a list of “symbols” whose relative frequency is known or can be
estimated. It doesn’t matter whether those symbols represent bytes, letters, pixels, or something entirely different: As long as some symbols occur more frequently than others, Huffman’s algorithm lets us construct a prefix code that produces an efficient binary encoding of
the data.
In practice, however, Huffman coding is usually outperformed by compression methods that are able to exploit other sources of redundancy. As an example, consider the he lyrics of Daft Punk’s song “Around the World,” which consists of a
single phrase that is repeated approximately 140 times:
Around the world, around the world
Around the world, around the world
Around the world, around the world
Around the world, around the world
…
If we count how often each letter occurs, we can construct the corresponding Huffman code and then encode the lyrics by replacing each letter with its codeword. The resulting bit sequence will be much more compact than, say, the ASCII encoding of the song, but it’s still highly redundant because the same
sequence of codewords is repeated 140 times.
Similar (but usually less extreme) forms of repetition can be found in many kinds of computer documents, whether it is plain text, HTML files, source code, or compiled machine code. For these kinds of data, far better compression rates can be achieved by using algorithms that don’t encode individual
characters but try to find redundancy at the level of words, phrases, or more generally sequences of bytes.
One common approach to this problem is known as dictionary-based compression, which is based on the idea of building a “dictionary” of common words or byte sequences. During compression, each occurrence of such a byte sequence is replaced with a reference to this dictionary, and during
decompression these references are expanded again. For example, if we use a dictionary that contains the single entry “round the world”, we can encode each line of the lyrics above as “A\(\langle 0\rangle \), a\(\langle 0\rangle \)”, where \(\langle
0\rangle \) denotes a reference to the only entry. Of course, if we want to decode data compressed in this way, we need to include a copy of the dictionary with the compressed data. The challenge is therefore to construct a dictionary that contains every common byte sequence in a file but doesn’t takes
up as little space as possible in the output.
A beautiful and ingenious solution to this problem was found by Abraham Lempel and Jacob Ziv in the late 1970s. They invented a class of compression algorithms — now often referred to as Lempel-Ziv compression — that build the dictionary incrementally while advancing through the file. Each byte sequence added to the dictionary is taken from the uncompressed data to the left of the current position, which makes it possible to
construct exactly the same dictionary both when compressing the file and when decompressing it. It is therefore not necessary to transmit the dictionary explicitly.
The most widely used algorithm based on this idea is LZ77, named after the last names of its two inventors Lempel and Ziv and the year it was published. With LZ77, the dictionary simply consists of all byte sequences that occur within a fixed number of bytes before the current position.
This part of the file is referred to as the dictionary region, whereas the sequence of bytes that starts at the current position is called the lookahead region.
Example10.1. To see how this works, assume we want to compress the string “YABBA DABBA DOOOOO,” which consists of 18 ASCII
characters. To keep things simple, we set the size of the dictionary region to 6 bytes and the size of the lookahead region to 4 bytes. At the start of the algorithm, the dictionary region is empty and the lookahead region contains the
first four characters “YABB”:
As we advance through the file, new bytes enter the dictionary and lookahead regions at the right, and old bytes leave them at the left. When the current position has moved to the beginning of “DABB”, the dictionary contains the first six bytes of the input:
Every contiguous sequence of bytes in the dictionary region is considered an individual entry; some of the entries contained in this the dictionary are “YABBA␣”, “YAB”, “ABBA”, “BA␣”, and “␣”.
Compression
During compression, LZ77 uses this dictionary as follows. In each step, the algorithm tries to compress the byte sequence at the current position by searching for the longest match in the dictionary. If a match is found, the algorithm outputs a reference to the corresponding position in the dictionary; we
write this as Match(offset, length), where offset is the relative position in the dictionary and length the number of matched bytes. If no match is found, the algorithm instead outputs the current byte \(b\) in uncompressed form; we write this
as Byte(b). We refer to Match and Byte as tokens. Compressing a file using LZ77 amounts to transforming a sequence of bytes into a more compact sequence of tokens.
.
Step
Dictionary / Input
Token
Notes
1
Byte(Y)
No match
2
Byte(A)
No match
3
Byte(B)
No match
4
Byte(B)
Match too short
5
Byte(A)
Match too short
6
Byte(\(32\))
No match
7
Byte(D)
No match
8
Match(offset=6, length=4)
4-byte match
9
Match(offset=6, length=2)
2-byte match
10
Byte(O)
No match
11
Match(offset=1, length=4)
4-byte match
Figure 10.1 Example of LZ77 compression. LZ77 transforms the input into a sequence of tokens, each of which encodes either a single character or a sequence of characters.
Example10.2. Figure 10.1 shows the steps
performed by LZ77 and the tokens it produces as it compresses the string “YABBA DABBA DOOOOO.” The output of the algorithm is the sequence of 11 tokens shown in the third column. Since LZ77 starts with an empty dictionary, the first few bytes are
always encoded as Byte tokens. In steps 4 and 5, the letters “B” and “A” are encoded as Byte tokens even though they do occur in the dictionary. As we will explain in more detail later, most
implementations of LZ77 ignore matches that are shorter than two or three bytes.
The first real match is found in step 8: all four bytes “ABBA” at the current position are also found at the start of the dictionary:
Since the match is found 6 bytes to the left of the current position and is 4 bytes long, the token Match(offset=6, length=4) is written to the output. Another match of length 2 is found in the following step.
The last two steps in Fig. 10.1 illustrate an important special case. A sequence of identical bytes, in this case “OOOOO”, can be represented using a single Byte token for the first byte and a
Match token for the remainder of the sequence. Unlike the tokens we have seen so far, this Match token references bytes that aren’t in the dictionary yet. This usually wouldn’t make sense, but for repetitive byte sequence like this, we can
interpret a token like Match(offset=1, length=4) as “copy the byte at offset 1 four times.” We will see below how this token is handled during decompression.
LZ77 compresses data by replacing common byte sequences with Match tokens. At first glance, it might therefore seem advantageous to allow arbitrarily large values for offset and length, because this would allow us to always find the longest match that
occurs in the input. But for reasons that will become clear as we continue our discussion of LZ77, it’s usually necessary to restrict their range as follows:
\(\seteqnumber{0}{10.}{0}\)
\begin{align*}
1 &\le \Id {offset} \le \Const {MaxOffset}\\ \Const {MinLength} &\le \Id {length} \le \Const {MaxLength}
\end{align*}
The upper bound for offset, MaxOffset, determines the size of the dictionary region and how far back we search for possible matches. This parameter has a major impact on the performance of LZ77, because large dictionaries consume more memory and take
longer to search. The upper bound for length, MaxLength, determines the longest match that can be represented. Increasing this parameter usually improves the compression rate since it allows longer byte sequences to be represented, although there is a point of
diminishing returns since long repetitions tend to be rare in real-world data. As mentioned in the example above, the main purpose of the MinLength parameter is to ensure that short matches are encoded using Byte tokens instead of Match tokens. We will discuss appropriate values for these parameters later in this chapter when we discuss the encoding of compressed data in Sections 10.4 and 10.5.
A formal description of the LZ77 compression algorithm is shown in Algorithm 10.1. The input is an array of bytes \(B\) and the output a sequence of Match and Byte tokens that represent the input in compressed form. The algorithm iterates over \(B\) from left to right, using the variable \(p\) to store the current position. In each step, the inner for loop searches for the longest match of the current input in the
preceding MaxOffset bytes; the best match found so far is stored in length and offset. The while loop on line 6 compares the byte sequence starting at \(p-o\) to the one
at the current position \(p\) and counts the number of matching bytes \(n\). After searching the dictionary, the algorithm outputs a single token that represents one or more bytes starting at \(p\). If the best match is longer than MinLength bytes it
outputs a Match token and advances \(p\) by length bytes; otherwise, it outputs a Byte token and advances \(p\) by a single byte.
Algorithm 10.1
Given an array of bytes \(B\), compute a list of Match and Byte tokens that represents the same bytes in compressed form.
Decompression
To recover the original text from the sequence of tokens produced by LZ77, we process each token from left to right and output the byte sequence it describes. For tokens of the form Byte(\(b\)) we output the single byte \(b\), and for tokens of the form Match(offset, length) we copy a sequence of length bytes starting offset places to the left of the current position. During decompression, the dictionary region consists of the last \(D\) bytes that were written to the output. When decoding a
token, the dictionary always contains exactly the same bytes as it did when the token was produced, so the decompression algorithm can recover the uncompressed byte sequence exactly.
.
Step
Token
Output
1
Byte(Y)
2
Byte(A)
3
Byte(A)
4
Byte(A)
5
Byte(A)
6
Byte(␣)
7
Byte(D)
8
Match(off=6,len=4)
9
Match(off=6,len=2)
10
Byte(O)
11
Match(off=1,len=4)
Figure 10.2 When decompressing LZ77 tokens, each token produces one one or more bytes to the output that are added to the output. For Match tokens, these bytes are copied from the dictionary region at the end of the current output, which is indicated
using thick lines.
Example10.3. Let’s decode the tokens that were generated by the compression algorithm in Fig. 10.1; the resulting steps are shown in Fig. 10.2. At the start of the algorithm, both the output and the dictionary are empty. The first seven tokens are Byte tokens, which are decoded by writing their values to the output. One by one, this also populates the dictionary region, which consists of up to six bytes at the end of the output. In Step 7, we have successfully decoded the first seven characters, the last six of
which make up the dictionary region.
The next token, Match(offset=6, length=4), is decoded by copying 4 characters from the dictionary region at offset 6 from the right, which is the string “ABBA” at the beginning of the dictionary. Similarly, the next token Match(offset=6, length=2) duplicates the two bytes “␣D” at offset 6.
The two final tokens produce the string “OOOOO”. The Byte(O) token adds a single “O” to the output, which is then replicated by Match(offset=1, length=4). This Match token is special because the dictionary doesn’t yet contain all four bytes that must be copied. The trick is to interpret Match tokens that extend beyond the end of the dictionary as multiple Match tokens of
length 1. In this case, we treat Match(offset=1, length=4) as a sequence of four Match(offset=1, length=1) tokens, each of which duplicates the last “O” in the dictionary.
Copying the first “O” produces
The new “O” is now the last byte in the dictionary, so we can copy that too and obtain
The third and fourth “O” are handled the same way. Other Match tokens that extend beyond the current dictionary region are handled similarly; see Exercise 10.1. At this point, no more
tokens are left and we have successfully recovered the original byte sequence.
Algorithm 10.2 shows a formal description of the decompression algorithm for LZ77. The variable \(p\) keeps track of the current position in the output. After initializing \(p\) to 0, the algorithm iterates
over the tokens and either writes a single byte in the case of a Byte token or a sequence of bytes copied from preceding positions in the output in the case of Match token.
Algorithm 10.2
Expand a given list of LZ77 tokens into an uncompressed array of bytes.
That’s the essence of LZ77 — a simple but surprisingly effective method for detecting and eliminating redundancy in many types of files.
Exercises
Exercise 10.1. Consider the LZ77-Decompress algorithm (Algorithm 10.2).
a) Show that a single token of the form Match(offset=\(o\), length=\(l\)) produces the same byte sequence as \(l\) tokens of the form Match(offset=\(o\),
length=1).
b) Describe the output of produced for Match(offset=\(o\), length=\(l\)) if \(l>o\), in other words, if the match extends beyond the end of the dictionary region.
Exercise 10.2. Use the representation of tokens in Listing 10.1 to implement LZ77-Compress and LZ77-Decompress.
Listing 10.1ch10 / SimpleToken
// Data type for representing LZ77 tokens.
public sealed interface SimpleToken {
record Byte(byte value) implements SimpleToken {
}
record Match(int offset, int length) implements SimpleToken {
}
}
