LZ77 Sliding-Window Compression

LZ77 is a family of lossless compressors that replaces repeated input with references into a bounded history window. The original 1977 design used a sliding dictionary; practical formats choose their own token syntax, match finder, and entropy coder.

Literals, History, and Matches #

At an input position, the encoder searches the previously emitted bytes for a matching prefix. It emits a literal when no useful match exists, or a back-reference containing at least a distance and a length. Some formats add a literal after every match; others emit a stream of independent literals and matches. The decoder copies length bytes from distance bytes before its current output position.

Copies may overlap their source. If the history ends in a, a match with distance 1 and length 5 produces aaaaa: each copied byte becomes the source for the next byte. A decoder must copy in forward byte order or use a loop with equivalent cascading semantics. Neither memcpy nor a snapshot-style memmove implements every valid overlapping match.

Match Search and Parsing #

A larger window finds more distant repetition but consumes memory and requires more distance bits. Hash chains, binary trees, suffix structures, and bounded candidate searches trade compression ratio for CPU time.

A greedy parser chooses the longest match at the current position. A lazy parser first records a candidate, checks whether the next position has a better match, and emits a literal instead when that improves the total cost. Dynamic programming can search a larger parse space, but costs more CPU and memory. None of those encoder choices affect decoder correctness because the token stream is self-contained.

Bounds and Defensive Decoding #

Every format defines its own minimum match length, maximum length, window size, and distance encoding. For example, DEFLATE permits distances up to 32 KiB and lengths up to 258 bytes. A decoder must reject a distance greater than the history already available, an invalid length or distance code, integer overflow while computing output positions, and output beyond the caller’s limit. Resource limits should cover both total output and work, because a small input can expand into a very large output stream.

DEFLATE and Related Formats #

DEFLATE entropy-codes literal/length and distance symbols with Huffman trees, then uses the LZ77 window for the referenced bytes. LZ4 uses a compact token format around the same copy operation, while Zstandard combines a windowed LZ match stage with different entropy coders. LZ78 and LZW instead maintain an explicit dictionary of phrases; their dictionary update rules must not be substituted for LZ77 history references.

References #

• J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, 1977.
• RFC 1951: DEFLATE
• RFC 7932: Brotli Compressed Data Format, for another windowed LZ design.