LZ77 and back-references
Huffman looks at how often a value appears. LZ77 looks for a repeated sequence. Suppose the output so far is abcabc and the next bytes are abc. Instead of writing those three bytes again, an encoder can say “copy three bytes from six bytes back.” A decoder can do that because it already restored the earlier abc.
A complete small example
For the eight bytes ABABABAB, this module first writes literal A and literal B. At the third input byte, the remaining ABABAB matches the pattern two bytes back. A match (distance=2, length=6) tells the decoder to repeat from that earlier position. The decoder starts with AB, then appends A, B, A, B, A, B to reach the original eight bytes. The match may overlap newly appended output; the copy rule handles that deliberately.
This example does not make a smaller archive here. Two literal tokens take four bytes, the match token takes four bytes, and the archive also needs its 12-byte header. Compression ratio depends on token costs and how often long matches occur, not just on whether a repetition exists.
The exact bytes of this example's lz77 archive are:
| Part | Hexadecimal bytes | Meaning |
|---|---|---|
| Magic | 4c 5a 37 37 | ASCII LZ77. |
| Original length | 08 00 00 00 00 00 00 00 | Eight, stored as a little-endian u64. |
| First literal | 00 41 | Tag 0, then A (0x41). |
| Second literal | 00 42 | Tag 0, then B (0x42). |
| Match | 01 02 00 06 | Tag 1, distance 2, length 6. |
That is 20 archive bytes for 8 input bytes. The table is an instance of this repository's wire format, not just an abstract LZ77 notation. The archive-format chapter explains the same header fields for other codecs.
The codec in src/lz77.rs writes two kinds of tokens:
| Tag | Following fields | Meaning |
|---|---|---|
0 | one byte | Copy that literal byte into output. |
1 | two-byte little-endian distance, then one-byte length | Copy length bytes from distance bytes back. |
The archive begins with LZ77 and the original size as an eight-byte little-endian integer. The decoder stops after restoring that many bytes. It rejects invalid distances, lengths under three, unknown token tags, and copies that overshoot the expected output size.
Finding a match
At each input position, find_match scans back at most 4 KiB for the longest matching run. It emits a back-reference when at least three bytes match, up to a maximum length of 255. Otherwise it emits one literal and advances one byte. This is easy to read but deliberately naive: scanning many candidate positions can be slow on large inputs.
Overlapping copies are allowed. A distance of 1 can repeat the last output byte many times: after outputting A, a match (1, 5) produces AAAAA. The decoder’s copy loop uses the distance modulo to reread bytes in the earlier pattern. The interactive example uses a smaller window so the matches are easier to inspect.
For the input AAAAAA, the encoder can write literal A followed by (distance=1, length=5). The decoder initially has one A. Each of the next five copy steps reads the byte one position behind the growing output, so it appends another A. No future input byte is needed to decode the match.
The tradeoff
The one-byte token tag makes every literal cost two bytes in this simple format. A file with few repeats can therefore grow quickly. Production LZ formats often combine matches with entropy coding and use better match finders. This module is a clean place to learn references and decoder validation.
The source walkthrough follows find_match and the decoder's tag switch. A long run of one byte can be represented by a distance-1 match: the decoder repeatedly copies from the most recently restored byte. The make roundtrip CODEC=lz77 target checks that encoding and decoding restore the same bytes.
Next: Byte PPM, which predicts each next byte from its context. To follow the token loops in Rust, read the LZ77 code walkthrough.