Original URL: https://www.uglypear.com/en/blog/lz77-algorithm-explained.html
How does the LZ77 algorithm work? This article explains the LZ77 dictionary compression principle — sliding window, triple encoding, and match finding, with a complete LZ77 encoding demonstration of the string 'abracadabra', covering the LZSS/LZMA/LZ4 evolution path. LZ77 is the foundation of virtually all modern dictionary-based compression algorithms.
1. What Is Dictionary Compression
Compression algorithms fall into two main schools: statistical coding (such as 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 already-processed historical data as an implicit dictionary. When repeated content is encountered, a "back-reference pointer" points to a previously occurring position.
In practice, the most popular compression algorithms are almost all "hybrid coding" — first using LZ77 to eliminate repeated patterns, then using Huffman for frequency compression of the residual data. DEFLATE is the classic combination of LZ77 + Huffman, widely used by ZIP, GZIP, and PNG.
| Compression 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 | Replaces repeated content with references | LZ77, LZW, LZMA | Good at repeated patterns | Ineffective on random data |
| Hybrid Coding | Dictionary + statistics 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 |
2. LZ77 Algorithm Principle Explained
The core of LZ77 is the sliding window mechanism. The window is divided into two parts: the search buffer (already-processed historical data) and the lookahead buffer (data to be processed). During encoding, a segment is taken from the lookahead buffer, and the longest match is found in the search buffer. If found, a triple is output; if not, the raw character is output.
The sliding window size directly determines compression effectiveness — the larger the window, the more historical data available for back-reference searching, and the higher the match probability. Window sizes vary significantly across algorithms.
LZ77's output unit is the triple (distance, length, next_char). The meanings of the three fields are shown in the table below.
| Field | Meaning | Range (DEFLATE) | Encoding Bits | Example |
|---|---|---|---|---|
| distance | Back-reference distance (how many characters back to find match) | 1–32768 | 15 bit | distance=10 → 10 characters back |
| length | Match length (how many consecutive characters match) | 3–258 | 8 bit | length=5 → 5 characters match |
| next_char | Next character after the match | 0–255 | 8 bit | next_char='d' → ASCII 100 |
The cleverness of the triple: after a match, an additional 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 — equivalent to degenerating to raw character storage.
Match finding is the performance bottleneck of LZ77 — taking a segment from the lookahead buffer and finding the longest match in the search buffer. Brute-force search has O(n×m) complexity; practical implementations use hash tables or suffix trees for acceleration.
| Algorithm | Search Buffer | Lookahead Buffer | Max Match Length | Typical Scenario |
|---|---|---|---|---|
| Original LZ77 | Several KB | Tens of bytes | 16 bytes | Teaching examples |
| DEFLATE | 32KB | 258 bytes | 258 bytes | ZIP/GZIP/PNG |
| LZMA | 8MB (configurable) | 273 bytes | 273 bytes | 7z/xz archiving |
| LZ4 | 64KB | Unlimited | Unlimited | Real-time compression |
| ZSTD | 8MB (up to 1GB) | Unlimited | Unlimited | Modern general purpose |
3. Practical Case: "abracadabra" Encoding Demonstration
Let's encode "abracadabra" (11 characters) using LZ77. Initial state: search buffer is empty, lookahead buffer contains the entire string. We scan position by position, finding the longest match in historical data.
Original: a b r a c a d a b r a
Results analysis: Pure LZ77 may expand short strings (triples 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 triple. For longer texts with more repeated patterns (such as code files, logs), LZ77's compression effect improves significantly.
4. LZ77 Variants and Modern Evolution
Since its introduction in 1977, LZ77 has spawned numerous variants, each optimizing a specific dimension for particular scenarios. The table below compares mainstream LZ77 family members.
Looking at the evolution trend, modern algorithms (ZSTD, brotli) have significantly improved speed while maintaining high compression ratios, gradually replacing DEFLATE as the new-generation standard. However, LZ77's core idea — sliding window dictionary references — remains unchanged, and all variants are built on this foundation.
For the specific application of DEFLATE in PNG format, refer to PNG Compression Principle Explained. For the difference between lossless and lossy compression, refer to Lossless vs Lossy Compression: Core Differences.
| Search Strategy | Data Structure | Search Complexity | Space Overhead | Typical Application |
|---|---|---|---|---|
| Brute-force search | None | O(n×m) | None | Teaching 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/suffix array | O(n) worst case | High | LZMA |
5. Frequently Asked Questions (FAQ)
Q1: What is the LZ77 algorithm?
LZ77 is a dictionary compression algorithm based on sliding windows, proposed by Lempel and Ziv in 1977. The core idea: use previously processed data as a dictionary, and when repeated content is encountered, replace the raw data with a (distance, length, next_char) triple, where distance represents the back-reference distance, length represents the match length, and next_char represents the next character after 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 the search buffer (already-processed historical data) and the lookahead buffer (data to be processed). 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 have higher match probability but greater memory overhead. The window size determines the upper limit of the maximum back-reference distance.
Q3: What's 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, outputting dictionary indices during encoding. LZ77 is better suited for data with local repetition (such as text), while LZ78 is better for globally repeated data. In practice, LZ77's descendants (DEFLATE/LZMA/LZ4) are far more popular than LZ78's 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 compression ratio but the slowest speed; DEFLATE uses a 32KB window + Huffman, with medium compression ratio and speed; LZ4 sacrifices compression ratio for extreme speed, with the lowest compression ratio but decompression speeds up to 4GB/s. Selection depends on the scenario: LZMA for archiving, DEFLATE/ZSTD for general purpose, LZ4 for real-time.
| Step | Current Position | Lookahead Content | Search Buffer Lookup | Output Triple | Notes |
|---|---|---|---|---|---|
| 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 | "a" found in "abr" | (0, 0, 'a') | "a" appears but subsequent doesn't match |
| 5 | Position 5 | cadabra | No "c" in "abra" | (0, 0, 'c') | First occurrence, direct output |
| 6 | Position 6 | adabra | "a" found 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 | Back 7 finds "abra" match | (7, 4, end) | Matches "abra" 4 characters |
6. Summary
LZ77 is the ancestor of dictionary compression algorithms. Its core principle is "sliding window + triple reference": using historical data as an implicit dictionary, outputting (distance, length, next_char) triples when repeated content is encountered. Pure LZ77 may expand short text, but combined with Huffman coding (DEFLATE), it becomes the standard compression scheme for ZIP/GZIP/PNG. The modern variant LZMA pursues extreme compression ratio, LZ4 pursues extreme speed, and ZSTD balances both.
The three keys to understanding LZ77: first, the sliding window determines the match range (DEFLATE 32KB, LZMA 8MB); second, the triple is the basic encoding unit (back-reference + length + next character); third, the match-finding strategy determines performance (hash chain is fastest, suffix tree is optimal). The LZ77 + Huffman hybrid coding is the gold standard for modern lossless compression.
| Encoding Method | Output Units | Bits per Unit | Total Bits | vs Original Savings |
|---|---|---|---|---|
| ASCII raw | 11 characters | 8 | 88 | — (Baseline) |
| LZ77 (no match optimization) | 8 triples | 31 (average) | 248 | -182% (expansion) |
| LZ77 (optimized flag bits) | 8 units | 12 (average) | 96 | -9% (slight expansion) |
| LZ77+Huffman | 8 units | 4.5 (average) | 36 | 59% |
| Algorithm | Key Improvement | Compression Ratio | Compression Speed | Decompression Speed | Typical Application |
|---|---|---|---|---|---|
| LZ77 (original) | Triple encoding | Low | Slow | Medium | Teaching |
| 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 archiving |
| LZ4 | Sacrifices ratio for extreme speed | Low | Extremely fast | Extremely 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 | Extremely fast | Modern general purpose |
| Scenario | Recommended Algorithm | Reason | Compression Ratio Reference |
|---|---|---|---|
| File archiving | LZMA (xz) | Highest compression ratio, speed not a priority | 70%–85% |
| General compression | ZSTD | Balances compression ratio and speed | 60%–80% |
| Real-time transmission | LZ4 | 4GB/s decompression speed, ultra-low latency | 50%–65% |
| Web transmission | DEFLATE/GZIP | Best compatibility, all browsers support | 50%–70% |
| Image format | DEFLATE (PNG) | Lossless compression, suitable for graphics | 50%–75% |
| In-memory data | LZ4 | Low CPU usage, suitable for high-frequency compression | 50%–65% |
FAQ
Q: How does the LZ77 algorithm work?
A: LZ77 is a dictionary-based compression algorithm that uses a sliding window approach. It maintains a 'search buffer' (previously processed data) and a 'lookahead buffer' (data to be compressed). It finds the longest match in the search buffer for the lookahead data and outputs a triple: (distance, length, next character). If no match is found, it outputs (0, 0, character). The window slides forward after each encoding step. This process is reversed during decompression.
Q: What is the sliding window in LZ77?
A: The sliding window is the core data structure of LZ77. It consists of two parts: 1) Search buffer (typically 32KB for DEFLATE) — contains recently processed data that serves as the dictionary. 2) Lookahead buffer (typically 258 bytes) — contains data to be encoded. The window slides forward as encoding progresses, with new data entering the lookahead and old data leaving the search buffer. The window size determines the maximum match distance and memory usage.
Q: How does LZ77 differ from LZSS, LZMA, and LZ4?
A: LZSS (Lempel-Ziv-Storer-Szymanski): LZ77 variant that only outputs matches when they save space (minimum match length threshold). LZMA (Lempel-Ziv-Markov chain): LZ77 variant with Markov chain-based prediction, larger dictionary (up to 4GB), and range coding. LZ4: LZ77 variant optimized for speed, uses a hash table for fast matching, sacrifices ratio for throughput. These form the evolution path from LZ77 to modern compression algorithms used in ZIP, 7Z, and real-time systems.
Q: What applications use LZ77 compression?
A: LZ77 and its variants are used in: DEFLATE (ZIP, GZIP, PNG) — the most widely used compression format, LZMA (7Z, XZ) — high compression ratio archiving, LZ4 — real-time compression in databases and file systems, zstd (Zstandard) — modern compression from Facebook, and brotli — web compression (HTTP content-encoding). LZ77 is the foundation of practically all modern dictionary-based compression.
Summary
The key to lz77 algorithm explained: how does... lies in identifying the sources of bloat and handling them accordingly. Choose the right compression strategy based on your scenario, prioritizing the largest contributors. SmartSlim can handle all compression steps in one click.
Related:
Top comments (0)