10 Lempel-Ziv Compression
10.5 Compressing LZ77 Tokens¶
The LZSS encoding we discussed in the previous section encodes each Byte and Match token using a fixed number of bits. In practice, however, some tokens occur much more frequently than others. Wouldn’t it therefore be preferable to encode common tokens using fewer bits than rare tokens? The answer is yes, but designing such an encoding poses a few interesting and unexpected challenges.
A straightforward solution would be to count how often each token occurs and then use Huffman’s algorithm to design an optimal bit encoding. At first sight, this works well. For example, if we split the full text of Alice in Wonderland into tokens and construct the corresponding Huffman code, we can encode each token using an average of 13.3 bits, whereas LZSS requires 17.2 bits on average. There is a catch, however: The 13.3 bits for Huffman coding do not include the size of the Huffman tree, which must be transmitted along with the compressed data. Unfortunately, this tree is massive since there are more than 20 000 different tokens. If we include the size of the encoded tree in the calculation, the storage requirements more than doubles to 27.3 bits per token, which is almost 60 % more than the simple LZSS encoding.
It’s easy to see why Huffman coding doesn’t work well in this case by considering the frequency distribution of tokens shown in Table 10.1. There are 74 unique Byte tokens, the majority of which (61 or 82 %) occurs at least ten times; this is the kind of distribution for which Huffman coding works well. In contrast, most of the 20 027 Match tokens occur just once, so the gains made by Huffman coding are more than offset by the need to include a Huffman tree with more than 20 000 nodes in the output. There is simply too little redundancy in the Match tokens to justify the overhead of Huffman coding.
But there are still ways to improve on the fixed-length encoding used by LZSS. As a first step, let’s take a closer look at the Match tokens that occur when compressing Alice in Wonderland. Figure 10.4 shows a histogram of all the offset values. It’s obvious that small offset values occur much more frequently than large values, which means that in most cases the best match is found in the preceding few thousand bytes. The histogram of the length values looks similar, which means that most matches are close by and fairly short. We therefore need a way to encode integers like offset and length so that small values take up fewer bits in the output than large values.
Variable-Length Codes for Integers
There are many ways to encode integers using a variable number of bits. We already encountered two examples in the previous chapter: The unary code discussed in Exercise 9.6 encodes a positive integer \(n\) as a sequence of \(n\) ones followed by a single zero, and the UTF-8 encoding discussed in Exercise 9.14 stores numbers between 0 and 0x10FFFF using one to four bytes. Another class of such variable-length integers can be obtained by encoding an integer’s binary representation and the length of this representation separately.
Let’s start with a simple example of such an encoding. Given a nonnegative integer \(n\), we first encode its bit length \(\bitlen (n)\) using a fixed number of bits \(L\) and then append the \(\bitlen (n)-1\) least significant bits of the binary representation of \(n\) itself. (For \(n=0\) and \(n=1\), we append no additional bits.) Table 10.2 demonstrates this encoding for a few small values of \(n\), in this case using \(L=5\) bits to encode \(\bitlen (n)\). The first two columns show the number being encoded in decimal and binary form, the next two columns its bit length, and the final column the resulting bit sequence, which is obtained by extending \(\bitlen (n)\) to 5 bits and then appending the lowest \(\bitlen (n)-1\) bits of \(n\).
| \(n\) | \(\bitlen (n)\) | Codeword | ||
| \(0\) | \(0_2\) | \(0\) | \(0_2\) | 00000 |
| \(1\) | \(1_2\) | \(1\) | \(1_2\) | 00001 |
| \(2\) | \(10_2\) | \(2\) | \(10_2\) | 00010 0 |
| \(3\) | \(11_2\) | \(2\) | \(10_2\) | 00010 1 |
| \(4\) | \(100_2\) | \(3\) | \(11_2\) | 00011 00 |
| \(5\) | \(101_2\) | \(3\) | \(11_2\) | 00011 01 |
| \(6\) | \(110_2\) | \(3\) | \(11_2\) | 00011 10 |
| \(7\) | \(111_2\) | \(3\) | \(11_2\) | 00011 11 |
| \(8\) | \(1000_2\) | \(4\) | \(100_2\) | 00100 000 |
| \(\vdots \) | \(\vdots \) | \(\vdots \) | \(\vdots \) | \(\vdots \) |
| \(3410\) | \(110101010010_2\) | 12 | \(1100_2\) | 01100 10101010010 |
| \(\vdots \) | \(\vdots \) | \(\vdots \) | \(\vdots \) | \(\vdots \) |
The range of numbers that can be encoded using this format depends on the number \(L\) of bits used to encode \(\bitlen (n)\). The largest positive number that can be encoded is
\[ n_{\max } = 2^{2^{L}-1}-1. \]
Conversely, if \(n_{\max }\) is the largest number of interest, we need at least
\[ L=\bitlen \bigl (\bitlen (n_{\max })\bigr ) \]
bits to encode the bit length of \(n_{\max }\). For \(L=5\) the largest value that can be encoded is \(n_{\max }=2^{31}-1\), which is also the largest number that can be stored in a signed 32-bit integer.
The following method demonstrates how to encode an integer n in this format. The resulting bit sequence is written to out and the parameter lengthBits indicates the number of bits that are used for \(\bitlen (n)\).
public static void writeInteger(
int n, int lengthBits, BitOutputStream out)
throws IOException {
int length = IntUtil.bitLength(n);
out.writeBits(length, lengthBits);
if (length > 1)
out.writeBits(n, length - 1);
}
•BitOutputStream: writeBits()
•IntUtil: bitLength()
Decoding an integer stored in this format is just as easy. We first read \(L\) bits to recover \(\bitlen (n)\). If \(\bitlen (n)\le 1\), we are done and return \(\bitlen (n)=n\). Otherwise, we read \(\bitlen (n)-1\) additional bits for the least significant bits of \(n\) and finish by adding the missing most significant bit:
static int readInteger(BitInputStream in, int lengthBits)
throws IOException {
int length = (int) in.readBits(lengthBits);
if (length <= 1)
return length;
return (1 << length - 1) | (int) in.readBits(length - 1);
}
The main limitation of the code we just described is that it cannot encode integers using fewer than \(L\) bits, which can be a problem if small numbers are overwhelmingly common. We can easily remedy this problem by choosing a different code for \(\bitlen (n)\). For instance, given an arbitrary prefix code bitlenCode, we can generalize the implementation of writeInteger() as follows:
static void writeInteger(
int n, PrefixCode bitlenCode, BitOutputStream out) {
int length = IntUtil.bitLength(n);
bitlenCode.writeSymbol(length, out);
if (length > 1)
out.writeBits(n, length - 1);
}
•BitOutputStream: writeBits()
•IntUtil: bitLength()
•PrefixCode: writeSymbol()
To read an integer stored in this format, we first use bitlenCode to decode the bit length and then read the remaining bits as before.
The LZH Encoding
We can now turn to the problem of designing a more efficient encoding for LZ77 tokens. Here is our general plan of attack:
-
• For Byte tokens, we will use a Huffman code because typically some bytes occur much more frequently than others.
-
• For Match tokens, we will encode the offset and length fields as variable-length integers, similar to the ones we just described. We will use Huffman codes to encode the bit lengths of the two fields.
The use of Huffman coding requires that the compression algorithm processes the input in two passes: The first pass converts the input into LZ77 tokens and constructs the necessary Huffman codes, and the second pass converts the tokens into bit sequences and writes them to the output.
The simplest implementation of the plan outlined above requires three Huffman codes: one for the Byte tokens and one each for the \(\bitlen (\Id {offset})\) and \(\bitlen (\Id {length})\) fields of Match tokens. In practice, it is more efficient to use one combined Huffman code for Byte tokens and length fields and a separate Huffman code for the offset fields. Listing 10.16 shows the outline of LZHEncoder, the class that will house the resulting compression algorithm. We will call the resulting format LZH because it is a combination of Lempel-Ziv compression and Huffman coding. The two Huffman codes we will use are stored in offsetCode and tagCode. As before, maxOffset, maxLength, and minLength are three parameters that control the conversion of the input into tokens. Because values of length below minLength are never used, we will encode the reduced length
\[ \Id {length}' = \Id {length} - \mathtt {minLength} \]
instead.
Listing 10.16ch10 / LZHEncoder
// A class for compressing data using LZ77 and Huffman coding.
public class LZHEncoder {
// Prefix codes for encoding tokens.
PrefixCode offsetCode;
PrefixCode tagCode;
// Parameters for LZ77.
final int maxOffset;
final int minLength;
final int maxLength;
// ...
}
The first code offsetCode is the simpler of the two and encodes the bit lengths of the offset fields in Match tokens. In contrast, the second code tagCode is more complicated because it can encode three different kinds of information, depending on the context:
-
• The first 256 symbols represent all possible Byte tokens.
-
• The next symbol with value 256 is a special tag that marks the end of the compressed data.
-
• The remaining tags starting at 257 represent Match tokens and store the bit length of \(\Id {length}'\),
The meaning of all possible tags is summarized in Fig. 10.5.
| Tag | Symbol | ||
| Byte(0) | 0 |
| } Byte tokens |
| Byte(1) | 1 | ||
| … | … | ||
| Byte(255) | 255 | ||
| end of file | 256 | ||
| \(\bitlen (\Id {length}') = 0\) | 257 |
| } Match tokens |
| \(\bitlen (\Id {length}') = 1\) | 258 | ||
| … | … |
Listing 10.17 demonstrates how tagCode and offsetCode are computed. We first prepare two frequency tables, tagCount and offsetCount, which are used to tally the frequency of the different tags and \(\bitlen (\Id {offset})\) values, respectively. For each Byte token in the input, we increment the corresponding entry in tagCount, and for each Match token, we increment the entry for \(\bitlen (\Id {length}')\) in tagCount and the one for \(\bitlen (\Id {offset})\) in offsetCount. Once this is done, we use the resulting frequency tables to construct the two Huffman codes.
Listing 10.17ch10 / LZHEncoder
// Analyze LZ77 tokens and prepare Huffman codes.
void prepareCodes(long[] tokens, int numTokens) {
int[] tagCount =
new int[257 + bitLength(maxLength - minLength) + 1];
int[] offsetCount = new int[bitLength(maxOffset) + 1];
tagCount[256] = 1; // end of file occurs exactly once
for (int i = 0; i < numTokens; i++) {
long token = tokens[i];
if (LZToken.isByteToken(token)) {
tagCount[LZToken.getByte(token)] += 1;
} else {
int length = LZToken.getLength(token) - minLength;
int offset = LZToken.getOffset(token);
tagCount[257 + bitLength(length)] += 1;
offsetCount[bitLength(offset)] += 1;
}
}
tagCode = HuffmanCode.construct(tagCount);
offsetCode = HuffmanCode.construct(offsetCount);
}
•HuffmanCode: construct()
•IntUtil: bitLength()
•LZHEncoder: maxLength, minLength, offsetCode, tagCode
•LZToken: getByte(), getLength(), getOffset(), isByteToken()
Using these two Huffman codes we can now encode a single LZ77 token as follows. If the token is a Byte token, we use tagCode to output the symbol with same numeric value. If the token is a Match token, we output four pieces of data, as shown in Listing 10.18:
-
1. The value \(257+\bitlen (\Id {length}')\), encoded using tagCode.
-
2. The \(\bitlen (\Id {length}')-1\) least significant bits of \(\Id {length}'\).
-
3. The value \(\bitlen (\Id {offset})\), encoded using offsetCode.
-
4. The \(\bitlen (\Id {offset})-1\) least significant bits of offset.
As you can see, values encoded using tagCode serve two purposes: They announce the type of token that follows in the stream and, for added efficiency, include some information about that token as well.
Listing 10.18ch10 / LZHEncoder
// Encode a single token and write the resulting bits to output.
private void writeToken(BitOutputStream output, long token)
throws IOException {
if (LZToken.isByteToken(token)) {
tagCode.writeSymbol(LZToken.getByte(token), output);
} else {
int length = LZToken.getLength(token) - minLength;
int offset = LZToken.getOffset(token);
tagCode.writeSymbol(257 + bitLength(length), output);
if (length > 1)
output.writeBits(length, bitLength(length) - 1);
offsetCode.writeSymbol(bitLength(offset), output);
if (offset > 1)
output.writeBits(offset, bitLength(offset) - 1);
}
}
•IntUtil: bitLength()
•LZHEncoder
•LZToken: getByte(), getLength(), getOffset(), isByteToken()
•PrefixCode: writeSymbol()
The general process for compressing a file using LZH is similar to the one for LZSS compression: We convert the file into a list of tokens and then encode each token as a sequence of bit. The main difference is that LZH compression requires an additional pass over the list of tokens to analyze their distribution and construct the necessary Huffman codes. This poses a new problem: When compressing large files, it may not be possible to store all tokens in memory, and scanning the entire input twice is costly and not always possible. Most compression programs therefore split large files into smaller blocks that fit into memory and can then be compressed independently.
The compress() method in Listing 10.19 compresses a given input by splitting it into blocks of a \(2^{20}\) tokens. For each block, we initialize tagCode and offsetCode by calling prepareCodes(). We then write the codes themselves to the output, and finally encode each token using writeToken(). After the last block has been processed, we end the output stream with a single end of file tag.
Listing 10.19ch10 / LZHEncoder
public void compress(InputStream input, BitOutputStream output)
throws IOException {
final int blockSize = 1024 * 1024;
var tokens = new long[blockSize];
var lz = new LZTokenizer(input, maxOffset, maxLength, minLength);
output.writeBits(maxOffset, 32);
output.writeBits(blockSize, 32);
while (lz.hasRemaining()) {
int numTokens = lz.readTokens(tokens);
prepareCodes(tokens, numTokens);
tagCode.writeCode(output);
offsetCode.writeCode(output);
for (int i = 0; i < numTokens; i++)
writeToken(output, tokens[i]);
}
tagCode.writeSymbol(256, output); // end marker
output.flush();
}
The final member of LZHEncoder we need to implement is the constructor, which initializes the parameters maxOffset, minLength, and maxLength. We again prevent short matches by setting minLength to 3, but the improved encoding of Match tokens gives us considerably more latitude when it comes to setting the other two parameters. For instance, we can afford to increase maxLength to 1024, which is a more than a hundred times larger than the value we used for LZSS.
The most important parameter is maxOffset, because it determines the size of the dictionary region. Instead of using a fixed value, we let users of LZHEncoder control maxOffset indirectly by specifying the desired compression quality as a non-negative integer quality. We set
\[ \mathtt {maxOffset} = 2^{10 + \Id {quality}}, \]
so the dictionary doubles in size every time we increment quality. At the lowest quality 0, the dictionary is just 1024 bytes in size, and the largest quality we accept is 15, which corresponds to a dictionary of 32 megabytes (Listing 10.20).
Listing 10.20ch10 / LZHEncoder
public LZHEncoder(int quality) {
if (quality < 0 || quality > 15)
throw new IllegalArgumentException();
maxOffset = (1 << (10 + quality)) - 1;
minLength = 3;
maxLength = 1024;
}
In practice, each increment of quality reduces the size of the compressed output by a few percentage points. At the same time, however, each increment also increases the running time by approximately 30 % to 100 %, mainly because a larger dictionary must be searched.
The decompression algorithm for LZH is discussed in Exercise 10.4.
Exercises
Exercise 10.3. The Elias gamma code is a variable-length code for integers that is similar to the codes discussed in this section. For a given number \(n\), it encodes the number’s bit length and the actual bits as follows:
-
1. Write a sequence of \(\bitlen (n)-1\) zero-bits followed by a single one-bit.2
-
2. Append the \(\bitlen (n)-1\) least significant bits of \(n\).
Use this code to encode the numbers in Table 10.2.
Exercise 10.4. Complete the implementation of LZH compression in Section 10.5 by writing a program that takes the output of LZHEncoder and decodes it, recovering the original uncompressed file.
2 This is a so-called unary code, which we already discussed in Exercise 9.6.