> lz77 | sliding | window <
// LZ77 - Sliding window compression with dictionary references
Dictionary Coding
References repeated patterns using offset and length.
Sliding Window
Maintains a moving window for pattern matching.
Algorithm Base
Foundation for ZIP, GZIP, DEFLATE, and PNG.
>> technical info
How LZ77 Works:
LZ77 maintains a sliding window of recently seen data. For each position, it searches the window for the longest matching substring. If found, it outputs a reference (offset, length, next character). If not found, it outputs a literal (0, 0, character). This replaces repeated patterns with short references, achieving compression.
LZ77 Example:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Why Use LZ77:
- ▸Lossless compression
- ▸No prior knowledge needed
- ▸Adaptive to data
- ▸Simple implementation
- ▸Basis for modern algorithms
>> frequently asked questions
What is LZ77?
LZ77 is a universal lossless data compression algorithm published by Abraham Lempel and Jacob Ziv in 1977. It achieves compression by replacing repeated occurrences of data with references to a single copy existing earlier in the uncompressed data stream.
How does the sliding window work?
The sliding window consists of two parts: a search buffer (recently processed data) and a lookahead buffer (data to be compressed). The algorithm searches the search buffer for the longest match with the beginning of the lookahead buffer, then outputs a reference or literal.
LZ77 vs modern compression?
LZ77 is the foundation of many modern compression algorithms. DEFLATE (used in ZIP and GZIP) combines LZ77 with Huffman coding. LZSS improves LZ77 by eliminating redundancy. LZ78 and LZW build dictionaries differently but share the same principles.
What are optimal window sizes?
Typical window sizes range from 32KB to 64KB for general data. Larger windows find more matches but require more memory and time. DEFLATE uses 32KB. The lookahead buffer is typically 256-512 bytes. The best size depends on your data's repetition patterns.
LZ77 算法详解：滑动窗口和反向引用怎么工作？
LZ77（Lempel-Ziv 1977）是现代无损压缩的基石。工作原理：
滑动窗口（Sliding Window）：维护一个固定大小的“最近数据”缓冲区（如 DEFLATE 的 32KB）。
搜索 + 前瞻（Search + Lookahead）：
• 读入前瞻缓冲区的字节序列。
• 在搜索窗口里找与前瞻起始位置 最长匹配 的子串。
• 输出一个三元组：(offset, length, next_char)。
• offset：匹配在窗口中的反向偏移。
• length：匹配长度。
• next_char：匹配结束后的下一个字符（没有匹配时 offset=length=0）。
• 窗口向前滑动 length+1 字节。
示例：压缩 ABCABCABC
• 位置 0-2：输出 (0,0,A) (0,0,B) (0,0,C)（字面量）
• 位置 3：ABC 在偏移 3 处重现，输出 (3,3,A)（往回指 3 字节，匹配 3 字节）
• 位置 7：BC 在偏移 3 处重现，输出 (3,2,)
为什么有效？自然语言和源代码有大量局部重复：单词、短语、变量名、缩进。LZ77 用一个指针代替整个重复片段，非常高效。
LZ77 系列：LZSS（省略无匹配时的 offset/length）、LZ78（显式字典）、LZW（GIF/compress 用）、LZMA（7zip/xz）、LZ4（极速但弱）、Zstandard（现代最优综合）。
LZ77 和 DEFLATE、gzip、zip 有什么关系？
它们是严格的层级关系：
LZ77（算法）→ DEFLATE（算法组合）→ gzip / zlib / ZIP（文件格式）。
DEFLATE（RFC 1951）= LZ77 变体 + Huffman 编码：
1. 先用 LZ77 找重复，输出混合流：字面量（literal）、长度（length）、距离（distance）。
2. 再用 Huffman 对混合流做熵编码。literal 和 length 共用一棵 Huffman 树，distance 单独一棵。
3. DEFLATE 窗口固定 32KB，匹配长度 3-258 字节。
不同容器格式：
• gzip（RFC 1952）：DEFLATE 数据 + gzip header（文件名、时间戳、CRC32）。典型扩展名 .gz。
• zlib（RFC 1950）：DEFLATE 数据 + 2 字节 header + Adler-32 校验。用于 PNG、HTTP 压缩、git 对象。
• ZIP：多文件归档，每个文件独立 DEFLATE 压缩 + 中央目录。
• PKZIP：最早实现，1989 年 Phil Katz 发明，DEFLATE 这个名字就来自他。
现代替代品：Zstandard（Facebook 2015，比 gzip 快 3-5 倍，压缩率更好），Brotli（Google 2013，HTTP 压缩首选，内置 100+ KB 静态字典）。
LZ77 vs LZ78 vs LZW — 到底有什么区别？
三者都是 Lempel-Ziv 系列，但字典管理方式不同：
LZ77（1977）：
• 滑动窗口 = 隐式字典。
• 输出 (offset, length, next)。
• 没有显式字典，窗口外的旧数据就遗忘。
• 代表：DEFLATE、LZMA。
LZ78（1978）：
• 显式构建字典，每次输出 (dict_index, next_char)。
• 字典无限增长（或定期清空）。
• 历史意义大，实际很少直接使用。
LZW（1984，Welch）：
• LZ78 的改进：不输出 next_char，字典预填入所有单字节。
• 每次输出只是一个字典索引。
• 代表：GIF、TIFF、Unix compress（.Z）。
• 曾被 Unisys 专利保护到 2003-2004 年，曾导致 GIF 使用风波和 PNG 格式诞生。
现代优先级：LZ77-based（DEFLATE, Zstd, LZMA）> LZW > LZ78。