LZ77 is a lossless data compression algorithm introduced by Abraham Lempel and Jacob Ziv in 1977. It operates by using a sliding window dictionary to identify and encode repeated sequences of data; instead of storing the repeated data directly, it outputs references (length–distance pairs) to earlier occurrences. LZ77 forms the foundation for many subsequent compression techniques, including LZSS, LZW, and the DEFLATE algorithm used in formats such as gzip and PNG.
1 History
1.1 Authors and publication
Abraham Lempel and Jacob Ziv, both Israeli computer scientists, published the LZ77 algorithm in a 1977 paper titled "A Universal Algorithm for Sequential Data Compression" in the journal *IEEE Transactions on Information Theory*. The work introduced a new paradigm for lossless compression based on adaptive dictionary methods, departing from earlier statistical approaches. The algorithm's name derives from the authors' initials and the year of publication.
1.2 Context and predecessor algorithms
Before LZ77, compression methods such as Huffman coding and run-length encoding relied on fixed statistical models or simple redundancy detection. LZ77 was the first practical "universal" algorithm, meaning it required no prior knowledge of the data's statistical properties. Its sliding-window approach was inspired by earlier ideas in information theory but was novel in its implementation and efficiency. The algorithm established a family of LZ-based compressors that became dominant in the 1980s and 1990s.
2 Algorithm
2.1 Basic principle
LZ77 compresses data by replacing repeated occurrences of strings with references to a single copy of that string earlier in the data stream. The encoder maintains a "sliding window" of recently processed data and searches for the longest match between the upcoming data and any substring in the window. When a match is found, it is encoded as a length–distance pair; otherwise, unmatched symbols are output directly (as "literals").
2.2 Sliding window structure
The sliding window is partitioned into two contiguous buffers: the search buffer (history) and the lookahead buffer (future data). As encoding proceeds, the window shifts forward.
2.2.1 Search buffer
The search buffer contains a fixed number of previously encoded symbols (typically a few kilobytes to tens of kilobytes). It serves as the dictionary for matching. The encoder can scan this buffer to find the longest prefix of the lookahead buffer that appears in the search buffer.
2.2.2 Lookahead buffer
The lookahead buffer holds the next few symbols to be encoded (commonly a few hundred bytes). The encoder attempts to match the beginning of this buffer with substrings in the search buffer. Symbols in the lookahead buffer that are not part of a match are output as literals.
2.3 Encoding process
The encoder iteratively processes the input: for each position, it finds the longest match in the search buffer. If a match of sufficient length exists, it outputs a length–distance pair; otherwise, it outputs the literal symbol. The window then slides forward by the length of the match (or by 1 for a literal), and the process repeats.
2.3.1 Length–distance pairs
A length–distance pair consists of two integers: *length* (the number of matched symbols) and *distance* (how far back in the search buffer the match begins). For example, a pair (3, 5) means "the next three symbols are identical to the three symbols that began 5 positions ago." The decoder uses this information to reconstruct the data.
2.3.1.1 Example of encoding a simple string
Consider the string "abracadabra". With a search buffer of length 7 and a lookahead buffer of length 4, the encoding might proceed as:
- Output 'a' as literal.
- Output 'b' as literal.
- Output 'r' as literal.
- Output 'a' as literal.
- Output 'c' as literal.
- Output 'a' as literal.
- At "d": no match; output 'd' as literal.
- At "abra": the substring "abra" appears 7 positions earlier; output (4, 7).
The compressed output replaces the final four symbols with a single reference.
2.3.2 Minimum match length and literal flags
To avoid inefficient compression, most LZ77 implementations require a minimum match length (often 2 or 3) before using a length–distance pair. Very short matches would consume more space for the pair than the symbols themselves. A flag bit in the output stream distinguishes between literals and pairs, or the encoder can use a dedicated escape symbol.
2.4 Decoding process
Decoding is simpler than encoding: the decoder reads the compressed stream, outputs literals directly, and for each length–distance pair copies the sequence from the already-decoded output buffer (which acts as the dictionary). Because the decoder maintains the same sliding window state, it can reconstruct the original data exactly. No search operation is required during decoding.
3 Variants and derivatives
3.1 LZSS (1982)
LZSS (Lempel–Ziv–Storer–Szymanski) is a modification that eliminates literal flags and uses a single-bit prefix to distinguish between a literal byte and a length–distance pair. It also imposes a minimum match length of 2 and often uses a binary tree to speed up searches. LZSS is used in the PKZIP archiver and the Microsoft compressed file format.
3.2 LZW (1984)
LZW (Lempel–Ziv–Welch) builds a dictionary of variable-length strings from the input data as it is processed, without a sliding window. Instead of outputting length–distance pairs, each string is assigned a code word. LZW was widely used in the GIF image format and the Unix compress utility.
3.3 LZ77 in contemporary formats (DEFLATE, gzip, PNG)
DEFLATE, designed by Phil Katz in 1993, combines LZ77 with Huffman coding. It uses a sliding window (up to 32 KB) and encodes matches and literals with a second-stage entropy coder. DEFLATE is the core of gzip (file compression) and PNG (image compression). Most internet compression (HTTP, TLS) relies on DEFLATE or its variants.
4 Applications
4.1 File compression tools
LZ77-based algorithms are at the heart of many file compression utilities: PKZIP, gzip, bzip2 (which uses a variant), and 7‑Zip (using DEFLATE for ZIP compatibility). These tools achieve moderate to high compression ratios for text and binary data.
4.2 Network streaming compression
Protocols such as HTTP (Content-Encoding: gzip, deflate), WebSocket permessage-deflate, and SSH compression use LZ77 derivatives to reduce bandwidth. The low memory footprint and fast decoding of LZ77 make it suitable for real‑time streaming.
4.3 Embedded systems
LZ77's modest memory requirements (the sliding window and a small lookahead buffer) allow its use in microcontrollers, firmware, and IoT devices. For example, many embedded file systems and radio protocols employ lightweight LZ77 compressors to save storage or transmission time.
5 Performance considerations
5.1 Compression ratio
The compression ratio of LZ77 depends on the data's redundancy and the window size. Typical ratios range from 2:1 to 4:1 for English text, and up to 10:1 for highly repetitive data. The ratio degrades for small files or random data.
5.2 Speed trade‑offs
Encoding speed is limited by the string search in the sliding window. The naive O(n·m) search (n = input length, m = window size) can be accelerated with hash tables, binary trees, or ternary content‑addressable memories (TCAMs). Decoding is always O(n) and very fast, making LZ77 popular for distribution formats where decompression speed matters.
5.3 Window size and memory usage
Larger windows improve compression ratios but increase memory consumption and search time. Typical window sizes are 4 KB (small embedded systems) to 32 KB (DEFLATE) and up to 256 KB in modern compressors like LZMA. The memory usage scales linearly with window size, so the choice is a trade‑off between compression performance and hardware constraints.