LZ77, published by Abraham Lempel and Jacob Ziv in 1977, is a lossless, dictionary-based compression algorithm that replaces repeated substrings with back-references into a sliding window of previously seen data. Each encoded token is a triple (offset, length, next-char): offset points back into the search buffer, length says how many characters to copy, and next-char is the first character that does not match. This "parse-then-reference" scheme requires no pre-built dictionary — the compressor and decompressor both reconstruct the same implicit dictionary from the data stream itself, making LZ77 adaptive and universally applicable.
LZ77 underpins some of the most widely used compression formats in computing: DEFLATE (used inside ZIP and gzip) combines LZ77 with Huffman coding, LZSS is a refined variant used in many embedded systems, and modern formats such as LZ4 and Zstandard trace their lineage directly to Lempel-Ziv ideas. This simulator lets you type any text, adjust the search-buffer and lookahead-window sizes, and watch the encoder scan character by character, highlighting matched regions, generated tokens, and the evolving compression ratio.
How does the LZ77 sliding window work?
The algorithm maintains two buffers side by side: the search buffer (history) holding the last S characters already encoded, and the lookahead buffer holding the next L characters to encode. At each step the encoder finds the longest prefix of the lookahead that also appears in the search buffer, records an (offset, length) back-reference, then advances past the matched characters plus the one literal next-char. Both buffers slide forward together — hence "sliding window".
What compression ratio can LZ77 typically achieve?
Compression ratio depends heavily on the input's redundancy. Typical English text compresses to roughly 30–40% of its original size with LZ77 + Huffman (DEFLATE). DNA sequences, which repeat frequently, can achieve 60–80% reduction. Truly random data cannot be compressed at all — every back-reference search fails and every character must be emitted as a literal, making the output slightly larger than the input due to token overhead.
What is the difference between LZ77 and LZ78?
LZ77 uses a fixed-size sliding window into recent output as its implicit dictionary. LZ78 (1978) instead builds an explicit phrase dictionary that grows throughout encoding, using index + new-character tokens rather than offset + length tokens. LZW (Welch, 1984), the basis of the GIF format and early Unix compress, is a refinement of LZ78 that omits the literal character. LZ77 variants typically achieve better compression on natural language; LZ78 variants parse more regularly and can be faster on some hardware.
A larger search buffer gives the encoder more history to search for matches, increasing the probability of finding a long repeated substring. The theoretical compression limit of LZ77 approaches the empirical entropy of the source as the window size tends to infinity. In practice, DEFLATE uses a 32 KB search window; LZ4 can use windows up to 64 KB; Zstandard supports windows up to 2 GB, which is why it achieves substantially better ratios on large files with long-range redundancy such as source-code archives.
Yes, LZ77 is completely lossless. Decompression is straightforward: scan the token stream, and for each (offset, length, char) triple, copy length characters starting at position (current_output_position − offset) from the already-decoded output buffer, then append char. No dictionary or side information is needed beyond the token stream itself. The decompressor therefore runs in O(n) time, typically much faster than the encoder, which must search the window for each position.
LZSS (Storer & Szymanski, 1982) adds a single flag bit before each token to indicate whether it is a back-reference or a raw literal. LZ77 always emits a triple even for unmatched characters (offset=0, length=0, char), wasting bits. LZSS emits just the character byte when no useful match exists, and omits the next-char field from back-references. This reduces overhead for inputs with low redundancy and is the variant used in classic archive formats such as LHA and PKZIP's older methods.
DEFLATE (RFC 1951, used in ZIP, gzip, PNG, zlib) runs LZ77 with a 32 KB search window to produce a stream of literals and back-references, then further compresses that stream with two Huffman trees: one for literal/length values (0–285) and one for distance values (1–32768). The Huffman trees themselves are compressed with a third-level code. This two-stage approach is why gzip consistently outperforms plain LZ77: the Huffman stage captures symbol-frequency redundancy that LZ77 leaves behind.
Random data, by definition, has maximum entropy: every byte is equally likely regardless of context, so the probability of finding a match in the search buffer is very low. Most tokens reduce to (0, 0, char) — pure literals — and the offset/length fields add overhead rather than saving space. This is not a limitation of LZ77 specifically but a fundamental consequence of information theory: no lossless compressor can reduce the expected length of a sequence drawn from a maximum-entropy source.
Naïve LZ77 encoding is O(n·W) where n is input length and W is the search window size, because at each position the encoder scans the entire window for the longest match. With a hash table (as used in zlib), average-case complexity drops to O(n), though the worst case remains quadratic. Suffix arrays and suffix automata can achieve O(n log n) or O(n) worst-case optimal parsing, as used in research-grade compressors like brotli's internal LZ phase.
Executable binaries contain repeated instruction sequences, import tables, and string literals, so LZ77 achieves moderate compression (typically 40–60% size reduction). Uncompressed raster images with uniform regions compress well (PNG uses DEFLATE). However, already-compressed data (JPEG, MP3, MPEG) contains near-random byte distributions after their own entropy coding, so applying LZ77 again yields negligible or negative compression gains — most archive tools detect this and store such files uncompressed.
LZ4 (2011) prioritises decompression speed over ratio, achieving multi-GB/s decompression on modern CPUs by using simple 4-byte hash matching. Zstandard (Facebook, 2016, RFC 8878) adds finite-state entropy coding (a modern asymmetric numeral systems coder) on top of LZ77 matching and achieves ratios competitive with bzip2 at LZ4-like speeds. Brotli (Google, 2015, RFC 7932), used in HTTP content-encoding, combines LZ77 with a 120-entry static context model and a shared dictionary for web assets.