> lz77 | sliding | window <
// LZ77 —— 使用滑动窗口和字典引用的无损压缩算法
字典编码
通过偏移量和长度引用复用重复子串。
滑动窗口
维护一个滑动窗口来查找最长匹配。
现代压缩基础
是 ZIP、GZIP、DEFLATE、PNG 等格式的核心基础算法。
>> 技术说明
LZ77 的工作原理:
LZ77 维护一段最近出现数据的滑动窗口，在每个位置中在窗口内搜索与当前前视缓冲区开头最长匹配的子串。如果找到匹配，就输出 (偏移量, 长度, 下一个字符) 形式的引用；如果找不到，则输出 (0,0,字符) 的文字字面量。这样可以把重复片段替换成较短的引用，从而实现无损压缩。
LZ77 示例:
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,)
为什么选择 LZ77？:
- ▸无损压缩，不丢失任何信息
- ▸不需要预先了解数据格式
- ▸能够自适应不同数据的重复模式
- ▸实现难度适中、逻辑清晰
- ▸是许多现代压缩算法的基础组件
>> 常见问题
什么是 LZ77？
LZ77 是 Abraham Lempel 和 Jacob Ziv 于 1977 年提出的通用无损数据压缩算法。它通过用指向早先出现片段的引用替换数据流中的重复内容来实现压缩。
滑动窗口是如何工作的？
滑动窗口由搜索缓冲区（已处理数据）和前视缓冲区（待压缩数据）组成。算法在搜索缓冲区中查找与前视缓冲区开头最长的匹配，然后输出相应的引用或文字字面量。
LZ77 与现代压缩算法的关系？
LZ77 是许多现代压缩方案的基础。ZIP 和 GZIP 中使用的 DEFLATE 将 LZ77 与 Huffman 编码结合使用。LZSS 在 LZ77 的基础上减少冗余，而 LZ78 和 LZW 则以不同方式构建字典，但仍遵循相似的思想。
推荐的窗口大小是多少？
对于通用数据，典型窗口大小在 32KB 到 64KB 之间。更大的窗口可以找到更多匹配，但需要更多内存和时间。DEFLATE 使用 32KB 窗口，前视缓冲区通常为 256–512 字节。最佳大小取决于你数据中的重复模式。
// 计算示例
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// 代码示例
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> 更多问题
问：(偏移, 长度, 字符) 三元组是什么意思？
答：偏移表示在已见过的窗口中回退多远，长度是复制的字节数，字符是接下来的新字节。解码器据此逐步还原输出。
问：为什么复制区间可以重叠？
答：偏移小于长度时，复制会读取刚写入的字节，从而表示重复：(1, 5, x) 会把前一个字符输出 5 次。
问：LZ77 用在哪里？
答：LZ77 是 DEFLATE（gzip、zlib、PNG、ZIP）的核心，其变体见于 LZ4、Snappy、Zstandard 和 Brotli。窗口大小和搜索策略决定压缩率与速度。