4.1.10.5.21.1 LZ77 Compression Algorithm
The LZ77 compression algorithm is used to analyze input data and determine how to reduce the size of that input data by replacing redundant information with metadata. Sections of the data that are identical to sections of the data that have been encoded are replaced by a small amount of metadata that indicates how to expand those sections again. The encoding algorithm is used to take that combination of data and metadata and serialize it into a stream of bytes that can later be decoded and decompressed.
Compression Algorithm Terminology
The following terms are associated with the compression algorithm. Some of the terms also apply to the DIRECT2 encoding algorithm defined in the next section.
input stream: The sequence of bytes to be compressed.
byte: The basic data element in the input stream.
coding position: The position of the byte in the input stream that is currently being coded (the beginning of the lookahead buffer).
lookahead buffer: The byte sequence from the coding position to the end of the input stream.
window: A buffer that indicates the number of bytes from the coding position backward. A window of size W contains the last W processed bytes.
pointer: Information about the beginning of the match in the window (referred to as "B" in the example later in this section) and its length (referred to as "L" in the example later in this section).
match: The string that is used to find a match of the byte sequence between the lookahead buffer and the window.
Using the Compression Algorithm
To use the LZ77 compression algorithm:
Set the coding position to the beginning of the input stream.
Find the longest match in the window for the lookahead buffer.
Output the P,C pair, where P is the pointer to the match in the window, and C is the first byte in the lookahead buffer that does not match.
If the lookahead buffer is not empty, move the coding position (and the window) L+1 bytes forward.
Return to step 2.
Compression Process
The compression algorithm searches the window for the longest match with the beginning of the lookahead buffer and then outputs a pointer to that match. Because even a 1-byte match might not be found, the output cannot contain only pointers. The compression algorithm solves this problem by outputting after the pointer the first byte in the lookahead buffer after the match. If no match is found, the algorithm outputs a null-pointer and the byte at the coding position.
Compression Process Example
The following table shows the input stream that is used for this compression example. The bytes in the input, "AABCBBABC", occupy the first nine positions of the stream.
Input stream
-
Position 1 2 3 4 5 6 7 8 9 Byte A A B C B B A B C
The following table shows the output from the compression process. The table includes the following columns:
Step: Indicates the number of the encoding step. A step in the table finishes every time that the encoding algorithm makes an output. With the compression algorithm, this process happens in each pass through step 3.
Position: Indicates the coding position. The first byte in the input stream has the coding position 1.
Match: Shows the longest match found in the window.
Byte: Shows the first byte in the lookahead buffer after the match.
Output: Presents the output in the format (B,L)C, where (B,L) is the pointer (P) to the match. This gives the following instructions to the decoder: Go back B bytes in the window and copy L bytes to the output. C is the explicit byte.
Note One or more pointers might be included before the explicit byte that is shown in the Byte column. That is, a metadata pointer does not always need to be followed by an explicit byte. An input stream of "ABCABCABC", for example, can be represented as "(0,0)A(0,0)B(0,0)C(3,3)(6,3)" using the (B,L)C notation, with the last two elements being pointers without explicit bytes. The compressed output can be any combination of pointers and explicit bytes.
Compression process output
|
Step |
Position |
Match |
Byte |
Output |
|---|---|---|---|---|
|
1. |
1 |
-- |
A |
(0,0)A |
|
2. |
2 |
A |
B |
(1,1)B |
|
3. |
4 |
-- |
C |
(0,0)C |
|
4. |
5 |
B |
B |
(2,1)B |
|
5. |
7 |
A B |
C |
(5,2)C |
The result of compression, conceptually, is the output column—that is, a series of bytes and optional metadata that indicates whether that byte is preceded by some sequence of bytes that is already in the output.
Because representing the metadata itself requires bytes in the output stream, it is inefficient to represent a single byte that has previously been encoded by two bytes of metadata (offset and length). The overhead of the metadata bytes equals or exceeds the cost of outputting the bytes directly. Therefore, the protocol considers sequences of bytes to be a match only if the sequences have three or more bytes in common.