LZ77 Algorithm Explained: How Dictionary Compression Works

Bottom line: LZ77 is a sliding window-based dictionary compression algorithm. The core idea is "use historical data as a dictionary, and reference back when encountering repeated content." Encoding outputs triplets (distance, length, next_char): look back distance characters to find a match of length characters, followed by one unmatched character next_char. Taking the 11-character string "abracadabra" as an example, LZ77 encoding requires only 5 triplets, demonstrating significant compression. LZ77 is a core component of DEFLATE (ZIP/GZIP/PNG) and the common ancestor of modern compression algorithms like LZSS/LZMA/LZ4. Below we start from the sliding window principle, progressively demonstrating the encoding process.

If you're not yet familiar with Huffman coding principles, we recommend first reading Huffman Coding Principle: The Foundation of Compression Algorithms.

1. What Is Dictionary Compression

Compression algorithms fall into two main schools: statistical coding (e.g., Huffman coding) assigns variable-length codewords based on character frequency; dictionary compression replaces repeated content with "pointer references." LZ77 belongs to the dictionary compression school — it doesn't pre-build a dictionary table but uses processed historical data as an implicit dictionary. When encountering repeated content, it uses a "backreference pointer" to point to a previously occurring position.

School	Core Principle	Representative Algorithms	Advantage	Disadvantage
Statistical coding	Variable-length codes by frequency	Huffman, arithmetic coding	Approaches entropy bound	Poor at long-range repetition
Dictionary compression	Replace repeated content with references	LZ77, LZW, LZMA	Excels at repetitive patterns	Ineffective on random data
Hybrid coding	Dictionary + statistical two-stage	DEFLATE, ZSTD	Overall optimal	More complex implementation
Transform coding	Transform to frequency domain then quantize	DCT (JPEG), DWT	High lossy compression efficiency	Information loss

In practice, the most popular compression algorithms are almost all "hybrid coding" — first LZ77 eliminates repetitive patterns, then Huffman applies frequency-based compression to the residuals. DEFLATE is the classic combination of LZ77 + Huffman, widely used by ZIP, GZIP, and PNG.

2. LZ77 Algorithm Principle in Detail

The core of LZ77 is the sliding window mechanism. The window is divided into two parts: the search buffer (processed historical data) and the lookahead buffer (unprocessed future data). During encoding, a segment is taken from the lookahead buffer, and the longest match is found in the search buffer — if found, a triplet is output; if not, the raw character is output.

2.1 Sliding Window Structure

The sliding window size directly determines compression effectiveness — larger windows allow searching more historical data, increasing match probability. Different algorithms have very different window sizes.

Algorithm	Search Buffer	Lookahead Buffer	Max Match Length	Typical Scenario
Original LZ77	Few KB	Tens of bytes	16 bytes	Educational examples
DEFLATE	32KB	258 bytes	258 bytes	ZIP/GZIP/PNG
LZMA	8MB (configurable)	273 bytes	273 bytes	7z/xz archival
LZ4	64KB	Unlimited	Unlimited	Real-time compression
ZSTD	8MB (max 1GB)	Unlimited	Unlimited	Modern general-purpose

2.2 Triplet Encoding Format

LZ77's output unit is the triplet (distance, length, next_char). The meaning of each field is shown in the table below.

Field	Meaning	Range (DEFLATE)	Encoding Bits	Example
distance	Lookback distance (how many chars back to find match)	1–32768	15 bit	distance=10 → 10 chars back
length	Match length (how many consecutive chars matched)	3–258	8 bit	length=5 → 5 chars matched
next_char	Character following the match	0–255	8 bit	next_char='d' → ASCII 100

The cleverness of the triplet: after a match, an extra next_char is output, ensuring the encoder always advances at least 1 character and never gets stuck. If no match is found (length=0), both distance and length are 0, and only next_char is output — effectively degrading to raw character storage.

2.3 Match Finding Strategy

Match finding is LZ77's performance bottleneck — taking a segment from the lookahead buffer and finding the longest match in the search buffer. Brute-force search has O(n×m) complexity; real implementations use hash tables or suffix trees for acceleration.

Search Strategy	Data Structure	Search Complexity	Space Overhead	Typical Application
Brute-force	None	O(n×m)	None	Educational examples
Hash chain	Hash table + linked list	O(n) average	Low	zlib (DEFLATE)
Hash bucket	Hash table + array	O(1) average	Medium	LZ4
Suffix tree	Suffix tree/array	O(n) worst case	High	LZMA

3. Case Study: "abracadabra" Encoding Demo

Let's fully encode "abracadabra" (11 characters) with LZ77. Initial state: the search buffer is empty, and the lookahead buffer contains the entire string. We scan position by position, finding the longest match in the historical data.

Original text: a b r a c a d a b r a

Encoding process:

Step	Current Position	Lookahead Content	Search Buffer Lookup	Output Triplet	Description
1	Position 1	abracadabra	Empty, no match	(0, 0, 'a')	First character, direct output
2	Position 2	bracadabra	"a", no match for "b"	(0, 0, 'b')	First occurrence, direct output
3	Position 3	racadabra	"ab", no match for "r"	(0, 0, 'r')	First occurrence, direct output
4	Position 4	acadabra	Found "a" in "abr"	(0, 0, 'a')	"a" found but subsequent doesn't match
5	Position 5	cadabra	No "c" in "abra"	(0, 0, 'c')	First occurrence, direct output
6	Position 6	adabra	Found "a" in "abrac"	(0, 0, 'a')	"a" matches but subsequent doesn't
7	Position 7	dabra	No "d" in "abraca"	(0, 0, 'd')	First occurrence, direct output
8	Position 8	abra	Lookback 7, found "abra" match	(7, 4, end)	Matched "abra" 4 characters

Encoding efficiency comparison:

Encoding Method	Output Units	Bits/Unit	Total Bits	vs Original Savings
ASCII original	11 chars	8	88	— (baseline)
LZ77 (no match optimization)	8 triplets	31 (avg)	248	-182% (expansion)
LZ77 (optimized flags)	8 units	12 (avg)	96	-9% (slight expansion)
LZ77+Huffman	8 units	4.5 (avg)	36	59%

Result Analysis: Pure LZ77 may expand short strings (triplets take more space than raw characters), which is why LZ77 is typically combined with Huffman coding — DEFLATE is LZ77 + Huffman. In the "abracadabra" case, the match at position 8 "abra" (distance=7, length=4) is the key compression point, representing 4 characters with one triplet. For longer texts with more repetitive patterns (like code files, logs), LZ77's compression effect improves significantly.

4. LZ77 Variants and Modern Evolution

Since LZ77 was proposed in 1977, it has spawned numerous variants, each optimizing a specific dimension for particular scenarios. The table below compares mainstream LZ77 family members.

Algorithm	Key Improvement	Ratio	Compression Speed	Decompression Speed	Typical Application
LZ77 (original)	Triplet encoding	Low	Slow	Medium	Education
LZSS	Flag bits to distinguish match/literal	Medium	Medium	Fast	Early systems
DEFLATE	LZSS + Huffman two-stage	Medium-high	Medium	Fast	ZIP/GZIP/PNG
LZMA	Large window + range coding + optimal parsing	High	Slow	Medium	7z/xz archival
LZ4	Sacrifices ratio for extreme speed	Low	Very fast	Very fast (4GB/s)	Real-time/kernel
LZW	Explicit dictionary table (non-sliding window)	Medium	Fast	Fast	GIF/TIFF
ZSTD	LZ77 variant + FSE + dictionary preset	High	Fast	Very fast	Modern general-purpose

Looking at the evolution trend, modern algorithms (ZSTD, brotli) have significantly improved speed while maintaining high compression ratios, gradually replacing DEFLATE as the new standard. But LZ77's core idea — sliding window dictionary references — remains unchanged; all variants are built on this foundation.

Scenario	Recommended Algorithm	Reason	Reference Ratio
File archival	LZMA (xz)	Highest ratio, speed not a priority	70%–85%
General-purpose	ZSTD	Balances ratio and speed	60%–80%
Real-time transmission	LZ4	4GB/s decompression, ultra-low latency	50%–65%
Web transmission	DEFLATE/GZIP	Best compatibility, all browsers support it	50%–70%
Image format	DEFLATE (PNG)	Lossless, suitable for graphics	50%–75%
In-memory data	LZ4	Low CPU usage, suitable for high-frequency compression	50%–65%

For the specific application of DEFLATE in PNG format, see PNG Compression Principle in Detail. For the difference between lossless and lossy compression, see Lossless vs Lossy Compression: Key Differences.

5. FAQ

Q1: What is the LZ77 algorithm?

LZ77 is a sliding window-based dictionary compression algorithm, proposed by Lempel and Ziv in 1977. The core idea: use previously processed data as a dictionary, and when encountering repeated content, replace the original data with a (distance, length, next_char) triplet, where distance is the lookback distance, length is the match length, and next_char is the character following the match. LZ77 is a core component of DEFLATE (ZIP/GZIP/PNG) and the ancestor of modern algorithms like LZSS/LZMA/LZ4.

Q2: What does LZ77's sliding window mean?

The sliding window is LZ77's core data structure, divided into a search buffer (processed historical data) and a lookahead buffer (unprocessed future data). During encoding, a segment is taken from the lookahead buffer, and the longest match is found in the search buffer. Typical window size is 32KB (DEFLATE standard); larger windows increase match probability but also memory overhead. The window size determines the upper limit of the maximum lookback distance.

Q3: What is the difference between LZ77 and LZ78?

LZ77 uses a sliding window as an implicit dictionary, with matched content directly referencing historical data without storing a separate dictionary; LZ78 uses an explicit dictionary table, storing seen strings as numbered dictionary entries and outputting dictionary indices during encoding. LZ77 is better suited for data with local repetition (like text), while LZ78 is better for globally repetitive data. In practice, LZ77 descendants (DEFLATE/LZMA/LZ4) are far more popular than LZ78 descendants (LZW).

Q4: Which has the highest compression ratio: LZ77, LZMA, or LZ4?

Compression ratio ranking: LZMA > LZ77 (DEFLATE) > LZ4. LZMA uses a larger window (default 8MB), better matching algorithms, and range coding, achieving the highest ratio but the slowest speed; DEFLATE uses a 32KB window + Huffman, with medium ratio and speed; LZ4 sacrifices compression ratio for extreme speed, with the lowest ratio but decompression speeds up to 4GB/s. Choice depends on the scenario: LZMA for archival, DEFLATE/ZSTD for general purpose, LZ4 for real-time.

Summary

LZ77 is the progenitor of dictionary compression algorithms. The core principle is "sliding window + triplet references": using historical data as an implicit dictionary and outputting (distance, length, next_char) triplets when encountering repeated content. Pure LZ77 may expand short texts, but combined with Huffman coding (DEFLATE), it becomes the standard compression scheme for ZIP/GZIP/PNG. The modern variant LZMA pursues ultimate compression ratio, LZ4 pursues ultimate speed, and ZSTD balances both.

Three keys to understanding LZ77: first, the sliding window determines the match range (DEFLATE 32KB, LZMA 8MB); second, the triplet is the basic encoding unit (lookback + length + next character); third, the match finding strategy determines performance (hash chains are fastest, suffix trees are optimal). The LZ77 + Huffman hybrid coding is the gold standard of modern lossless compression.