LZ77: sliding-window dictionary compression
LZ77 is the lossless compression algorithm published by Abraham Lempel and Jacob Ziv in 1977, and it is the single most influential idea in practical data compression. Its trick is the sliding window: as the compressor reads the input, it keeps a look-back buffer of recently seen bytes, and whenever the upcoming bytes have already appeared within that window, it replaces them with a (distance, length) back-reference instead of writing them out literally.
LZ77 is the first stage of DEFLATE, the default ZIP method, and the core of LZMA used in 7z. Understanding it makes the rest of lossless compression fall into place: most modern "fast" compressors are a larger or smarter sliding window bolted to a better entropy coder.
How the sliding window works
The compressor maintains two regions: a window of recently processed bytes (the "dictionary," looking backwards) and a lookahead of upcoming bytes it is about to encode. For each position, it searches the window for the longest byte sequence that matches the start of the lookahead. If it finds a match longer than a small minimum, it emits a token — a back-reference of the form "copy length bytes from distance bytes back." If there is no useful match, it emits the next byte as a literal. The decoder walks the same window forward: literals are written directly, and a back-reference tells it to copy bytes it just produced.
The match length is bounded (DEFLATE allows 3 to 258 bytes) and the distance is bounded by the window size. DEFLATE uses a 32 KB window, so a back-reference can reach up to 32,768 bytes into the past but no further. That window size is the single biggest determinant of how well LZ77 compresses repetitive data: a larger window finds more, longer, more distant matches, which is why LZMA (with a window measured in megabytes) beats DEFLATE on ratio.
Literals, matches, and tokens
The output of the LZ77 stage is a stream of tokens — literals (a raw byte) and matches (a distance/length pair). This stream is not yet small: a match token itself takes bits to encode the distance and length, so a match only pays off when the bytes it saves outweigh the cost of describing it. That is why there is a minimum match length (3 in DEFLATE): anything shorter is not worth a token.
Raw LZ77 tokens are also not very compact on their own. The real compression gain comes from the second stage that follows: an entropy coder, almost always Huffman coding in DEFLATE or range coding in LZMA, which packs the token stream so that frequent tokens (common literals, common short distances) take few bits and rare tokens take many. LZ77 creates the redundancy the entropy coder then exploits.
LZ77 vs LZ78 and LZW
LZ77 is one of two algorithms in the original Lempel-Ziv family. Its sibling, LZ78 (1978), works differently: instead of a sliding window, it builds an explicit, growing table of strings encountered, and emits references into that table. The popular LZW variant of LZ78 powered the old Compress utility and the GIF format. Both eliminate redundancy; the distinction is whether the "dictionary" is an implicit sliding window over recent data (LZ77) or an explicitly constructed string table (LZ78/LZW). This distinction is the essence of dictionary coding generally.
In practice LZ77 descendants won. They tend to give better ratios for general data, they adapt naturally to local redundancy without a separate table, and the sliding-window model maps cleanly onto a fast entropy-coding second stage. DEFLATE, gzip, LZMA, zstd, and brotli are all LZ77-family designs.
Why window size is the key knob
Everything that distinguishes modern LZ77 compressors comes down to how big the window is and how cleverly they search it. A bigger window finds matches across longer ranges of input, which helps files with repetition spread over a long distance — log, code, and structured data. A smarter search (hash chains, suffix arrays, or the heavy modeling LZMA uses) finds the *longest* match rather than the *first* one, which is what drives the compression ratio up. The cost is memory and time: a 32 KB window is cheap to search, a multi-megabyte window is not. That tradeoff is why DEFLATE stays fast and universal while LZMA trades speed for a better ratio.
Frequently asked questions
What is LZ77 compression?
LZ77 is the 1977 Lempel-Ziv lossless compression algorithm that eliminates repeated byte sequences using a sliding window. As it reads the input it keeps a look-back buffer of recent bytes; when the upcoming bytes have appeared before within that window, it replaces them with a (distance, length) back-reference. The decoder reproduces the original by copying bytes from its own window. It is the foundation of DEFLATE, gzip, LZMA, zstd, and brotli.
What is the sliding window in compression?
It is the look-back buffer of recently processed bytes that an LZ77-family compressor searches for matches. Its size caps how far back a back-reference can reach: DEFLATE uses a 32 KB window, so a match can copy from up to 32,768 bytes in the past. A larger window finds more and longer matches, which is why compressors like LZMA — with megabyte-scale windows — achieve better ratios.
What is the difference between LZ77 and LZ78?
Both are Lempel-Ziv algorithms that eliminate redundancy, but LZ77 uses an implicit sliding window over recent data and emits distance/length back-references, while LZ78 builds an explicit, growing table of strings and emits references into that table. LZW, the famous LZ78 variant, powered the Unix compress utility and the GIF format. Modern general-purpose compressors are overwhelmingly LZ77 descendants.
Is LZ77 used in ZIP files?
Yes, indirectly. ZIP’s default method DEFLATE is LZ77 followed by Huffman coding — the first stage is a 32 KB sliding window that emits literals and (distance, length) match tokens, and the second stage entropy-codes those tokens. So every standard compressed entry in a ZIP is decompressed by reversing an LZ77 stage.
Is LZ77 lossless?
Yes. LZ77 only exploits redundancy; it never discards information. A back-reference copies bytes that already exist in the output, so the decompressed stream is byte-for-byte identical to the input. Like all lossless methods, the round trip can be checked with a checksum such as the CRC-32 ZIP stores per entry.