We will now turn to the problem of implementing the basic algorithms for LZ77 discussed in the previous section. As in our discussion of Huffman coding in the previous chapter, our final goal is to write a small compression program that takes a stream of bytes and outputs a compressed sequence of bits.
In the case of LZ77, this problem can be divided into two steps:
1. Convert the byte sequence into a sequence of LZ77 tokens. The main challenge in this step is to quickly find potential matches in the dictionary.
2. Convert the tokens into an efficient bit sequence. We will discuss two possible encodings for tokens: a simple one called LZSS that maps tokens to bit patterns of fixed length, and a more complex one that adds a second layer of compression by applying Huffman
coding to the tokens themselves.
In this section and the next we will discuss the first step, how to convert the input into a sequence of tokens. In Sections 10.4 and 10.5 we will explain methods for encoding
tokens.
The first step of LZ77 compression is to analyze the input and turn it into a sequence of Byte andMatch tokens. Algorithm 10.1 made this look easy: iterate over the input,
find the longest match in the dictionary using two nested for loops, and output the resulting tokens one by one. Real-world implementations of LZ77 are significantly more complex, however, because they need perform well with large dictionaries and large files.
The performance concerns start with the representation of tokens. In Java, the natural way to represent Byte and Match tokens would be to define two records Byte and Match that implement a common interface 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 {
}
}
We used these data types to implement LZ77 in Exercise 10.2.
However, when working with large files and millions of tokens, we can save time and memory by packing both kinds of tokens inside the 64 bits of a single long integer: For Byte tokens, we set the upper 56 bits to zero and store the value in the
least significant 8 bits, and for Match tokens, we use the upper 32 bits to store the offset field and the lower 32 bits to store the length field:
We can easily distinguish the two kinds of tokens in this representation: The offset field is a positive integer, so the upper 56 bits are zero for Byte and nonzero for Match tokens.
With this convention, creating Byte tokens and retrieving their values can be accomplished as shown in Listing 10.2. In makeByte() function converts single byte into a token by converting it to long and then clearing the upper 56 bits. The isByteToken()
function checks whether a given long represents a Byte token by checking whether the upper 56 bits are all zero. Listing 10.3 defines similar functions for working with Match tokens. The makeMatch() function combines two 32-bit integers into a single long, and getLength() and getOffset() extracts the the original values.
Listing 10.2ch10 / LZToken
// Create BYTE token for 'value'.
public static long makeByte(byte value) {
return (long) value & 0xffL;
}
// Return value of BYTE token as number between 0 and 255.
public static int getByte(long token) {
return (int) token;
}
// Is token a BYTE?
public static boolean isByteToken(long token) {
return (token & ~0xffL) == 0;
}
Listing 10.3ch10 / LZToken
// Create MATCH token.
public static long makeMatch(int offset, int length) {
return ((long) offset << 32) | (long) length;
}
// Retrieve length and offset fields of a MATCH token.
public static int getLength(long token) {
return (int) token;
}
public static int getOffset(long token) {
return (int) (token >>> 32);
}
How much memory does this representation save in practice? On a typical 64-bit computer, the Byte and Match records defined in Listing 10.1 consume
16 bytes and 24 bytes of memory, respectively, compared to the 8 bytes per token we achieve by storing them in a long integer; we therefore reduce memory consumption by between 50 % and
67 %.
It turns out that this new representation is also faster because, on most computers, processing arrays of longs is more efficient than processing arrays of SimpleTokens. One reason is that reading
data from memory is a relatively slow operation on modern CPUs, so reducing the footprint of a single token is already a win. In addition, processing contiguous blocks of memory (which Java uses for arrays of primitive types such as integer or long) is faster than processing objects that are scattered across the computer’s memory (which often happens to objects like SimpleToken).
For more information on the impact of CPUs and their memory architecture on program performance, see the book by Bryant and O’Hallaron [22, Chapter 6].
Cyclic Buffers
We mentioned earlier that all implementations of LZ77 restrict the range of possible Match tokens by placing limits on its offset and length fields:
\(\seteqnumber{0}{10.}{0}\)
\begin{align*}
1 &\le \Id {offset} \le \Const {MaxOffset}\\ \Const {MinLength} &\le \Id {length} \le \Const {MaxLength}
\end{align*}
As a result, only bytes in a small region around the current input position are accessed by the algorithm: The last MaxOffset bytes to the left of the current position serve as the dictionary and the following MaxLength bytes to the right are
accessed when searching for the longest match. We therefore only need to keep a small region consisting of \(\textsf {MaxOffset} + \textsf {MaxLength}\) bytes of the input in memory at any time, which is especially important when dealing with large files.
To map the currently visible portion of the file to an array of bytes in memory we use a clever data structure known as a cyclic buffer. A cyclic buffer is an array of size \(N\) that wraps around at both ends: The last element buffer[N-1] is followed by the first element buffer[0] and buffer[0] is preceded by
buffer[N-1]. As we iterate over the input, we place the bytes we read into successive entries of the buffer, the first byte into buffer[0], the second into buffer[1], and so on. Every time we reach the end of the buffer we wrap around to its start, so the byte at
position \(N\) in the file overwrites the entry in buffer[0], the one at position \(N+1\) the entry in buffer[1], and so on.
Figure 10.3 illustrates how we can use such a cyclic buffer to store the currently visible part of the input when implementing LZ77. We assume that \(\mathsf {MaxOffset}=6\) and \(\mathsf
{MaxLength}=4\), so we use a buffer of size 10. The first diagram shows the contents of the buffer after the first six bytes of the input have been processed: The left half of the buffer stores the dictionary region and the right half the part of the input that must be compressed next; the current
position is 6. In the second diagram, the input has advanced by one byte, which moves the current position to 7, shifts the dictionary region one place to the right, and stores the next byte read from the input in the buffer’s leftmost entry. The final diagram shows the contents of the buffer
after advancing by four more bytes; now the dictionary region wraps around to the start of the buffer.
Figure 10.3
A cyclic buffer is a fixed-size array that wraps around at both ends. Here, we use an array of length 10 to be able to access the next 4 bytes of the input and up to 6 bytes previous bytes.
To map file positions to buffer indexes we use the modulo operator: If \(k\) is the current position in the file, \(k\bmod N\) gives us the index of the current byte, \((k-1)\bmod N\) the index of the previous byte, and so on. Since \(k\) is nonnegative, we can use the remainder
operator % to implement this mapping:
buffer[k % buffer.length];
Since computing the remainder is fairly expensive, a common trick is to make the size of the buffer \(N\) a power of 2, which allows us to compute the remainder \(k\bmod N\) by extracting the least significant bits of \(k\) using the expression \(k\AND (N-1)\); accessing an entry in the
buffer can then be written as
buffer[k & (buffer.length - 1)];
This may look like a mild case of premature optimization, but writing to and reading from the buffer are among the most common operations performed by our implementation of LZ77. Especially when compressing large files, this simple optimization saves millions of remainder operations, which does
have a measurable performance impact.
We delegate the details of creating and managing cyclic buffers to a separate class called CyclicBuffer whose only member is an array of bytes buffer (Listing 10.4). The
constructor of CyclicBuffer takes the desired size of the buffer as its only argument. To be able to implement the buffer’s wrap-around logic using bit operations, this size is rounded to the next larger power of 2 before allocating the array for
buffer. The two methods get() and set() can now perform their index
computations using bitwise AND instead of modulo operations.
Listing 10.4ch10 / CyclicBuffer
// A fixed-size cyclic buffer of bytes.
public class CyclicBuffer {
private final byte[] buffer;
public CyclicBuffer(int size) {
// Round the buffer size to next larger power of 2.
buffer = new byte[1 << IntMath.ceilBinaryLog(size)];
}
public byte get(int index) {
return buffer[index & (buffer.length - 1)];
}
public void set(int index, byte v) {
buffer[index & (buffer.length - 1)] = v;
}
}
For a given number \(n\), the nearest power of 2 that is at least as large as \(n\) is \(2^{\lceil \log _2 n\rceil }\): we first take the binary logarithm of \(n\), round it up to the next larger integer, and then turn the result into a power of 2.
We already met the expression \(\lceil \log _2 n\rceil \) in Section 5.3 and also implemented a function ceilBinaryLog() that computes it. Combined with a left shift to compute a power of 2, this gives us the following expression, which is used to initialize the buffer used in CyclicBuffer():
1 << IntMath.ceilBinaryLog(size)
Producing the Next Token
We collect the code for reading the input and generating tokens in a class called LZTokenizer, which is outlined in Listing 10.5. The InputStream
being compressed is stored in input, and the parameters of the LZ77 algorithm in maxOffset, maxLength, and minLength. The constructor LZTokenizer() first initializes the four fields defined above and then calls initBuffers() and initIndex() to prepare a few additional data structures.
Listing 10.5ch10 / LZTokenizer
// Converts a stream of bytes into a sequence of LZ77 tokens.
public class LZTokenizer {
private final InputStream input;
private final int maxOffset;
private final int maxLength;
private final int minLength;
public LZTokenizer(InputStream input, int maxOffset, int maxLength,
int minLength) throws IOException {
this.input = input;
this.maxOffset = maxOffset;
this.maxLength = maxLength;
this.minLength = minLength;
initBuffers();
initIndex();
}
// ...
}
We use one cyclic buffer to store the bytes from the input that are currently visible; this is the “window” through which we view the file, so we call the corresponding field window. We manage this buffer using two integers front and
lookaheadSize: front is the current position in the file and points to the next uncompressed byte, and lookaheadSize is the current number of bytes in the lookahead region. Except at the end of the file, lookaheadSize is
always equal to maxLength.
Listing 10.6ch10 / LZTokenizer
private CyclicBuffer window; // the currently visible part of the input
private int front; // the current position
private int lookaheadSize; // number of bytes in window after 'front'
public boolean hasRemaining() {
return lookaheadSize != 0;
}
private void initBuffers() throws IOException {
this.window = new CyclicBuffer(maxOffset + maxLength);
this.front = 0;
this.lookaheadSize = 0;
while (lookaheadSize < maxLength) {
int nextByte = input.read();
if (nextByte == -1)
break;
window.set(lookaheadSize++, (byte) nextByte);
}
}
The input window is initialized in initBuffers(). First, we allocate a cyclic buffer that is large enough to hold the dictionary regionand the lookahead
region, so its size must be at least maxOffset + maxLength. We then fill the lookahead region with the first maxLength bytes from the file, writing each byte to window and incrementing lookaheadSize afterward.
The main method in class LZTokenizer is nextToken(), which computes and returns the next token (Listing 10.7). The function first searches the dictionary to find the longest match for the byte sequence in the lookahead region. We use a method called findMatches() to compute a list of
positions where a match might be found and then compare each of these positions to the bytes at front. The length and offset of the longest match found so far are stored in bestLength and bestOffset. If the best match is sufficiently long, the function
returns a Match token and advances the input by bestLength bytes; otherwise, it returns a Byte token and advances by a single byte.
Listing 10.7ch10 / LZTokenizer
// Compute a token for one or more bytes at the current position.
public long nextToken() throws IOException {
// Find the longest match
int bestLength = 0, bestOffset = 0;
for (int matchStart : findMatches()) {
int n; // length of current match
for (n = 0; n < lookaheadSize; n++) {
if (window.get(front + n) != window.get(matchStart + n))
break;
}
if (n > bestLength) {
bestLength = n;
bestOffset = front - matchStart;
}
}
// Return either MATCH or BYTE token
if (bestLength >= minLength) {
advanceInput(bestLength);
return LZToken.makeMatch(bestOffset, bestLength);
} else {
advanceInput(1);
return LZToken.makeByte(window.get(front - 1));
}
}
Because we will later want to process tokens in large batches instead of individually, we also provide a method readTokens() that reads as many tokens as possible and stores them in the given array
of long integers (Listing 10.8). The function returns the number of tokens that was read; this is less than size of the array if the end of the input was encountered.
Listing 10.8ch10 / LZTokenizer
// Compute multiple tokens. Returns the number of tokens generated.
public int readTokens(long[] tokens) throws IOException {
int len = 0;
while (hasRemaining() && len < tokens.length)
tokens[len++] = nextToken();
return len;
}
