> lz77 | sliding | window <
// LZ77 —— 使用滑动窗口和字典引用的无损压缩算法
0 字符
0 字符
>> 功能特点
[DICTIONARY]
字典编码
通过偏移量和长度引用复用重复子串。
[SLIDING]
滑动窗口
维护一个滑动窗口来查找最长匹配。
[FOUNDATION]
现代压缩基础
是 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 字节。最佳大小取决于你数据中的重复模式。