LZ77 算法核心:滑动窗口与字符串匹配原理

为什么压缩软件总在啃一段老故事

翻看 ZIP、gzip、PNG 这些老牌格式的内核,几乎都能追到同一个词:LZ77。这套方法最早在二十世纪七十年代被提出,核心思路也朴素——"刚刚出现过的东西,能不能用更短的引用代替"。今天的桌面压缩工具,处理文本类文件时所采用的滑动窗口机制,本质上仍是这一思路的延伸。

要理解 LZ77,只需抓住两个关键词:滑动窗口和字符串匹配。

滑动窗口:把"看过的内容"装进一只口袋

把压缩过程想象成一个滑动的窗口,窗口只能装下最近看过的一段数据。每读入新字符,窗口就往后挪一格,把最旧的数据挤出去,腾出空间迎接新内容。这个窗口大小,通常以 KB 为单位——具体多大,不同实现各有取舍,但关键在于:窗口里装的是"已经处理过的原文",不是整个文件。这正是 LZ77 能用很少内存处理大文件的原因。

窗口之外,还有一段"向前看"的区域,负责在窗口里寻找匹配。这种"已处理区+前瞻区"的二段式结构,后来成了字典压缩的通用骨架。

字符串匹配:用三件套描述"我见过它"

压缩时,程序不停尝试在新数据里找到与窗口内已有的内容重复的片段。一旦找到,就用一个三元组来代替原文:偏移距离、匹配长度、下一个未匹配字符。这三件套,正是 LZ77 输出码流的最小单位。

• 偏移:从当前位置往回数,匹配片段的头在窗口里哪个位置。
• 长度:连续相同的字符有几格。
• 下一个字符:匹配结束后的那个"不一样"的字符,也一并输出来,避免错过边界。

读端只要拿到这个三元组,就能在窗口对应位置把同样的字符串"复制"回去,还原出原文。窗口跟着滑动,前后保持同步,这就是无损恢复的关键。

为什么"查找"成了它的命门

LZ77 思路不难,真正费时的是"在哪一格里找到了那个片段"。最朴素的算法是从当前光标往前逐字节比对——慢,但简单。后来的实现大多引入哈希表或二叉树,把查找从线性扫描降到接近常数时间。

这也是为什么处理图片和视频时,常见的做法是先用分块、字典、BWT 等技术重排数据,再交给类似 LZ77 的步骤压缩——目的是让数据里出现更多的"重复片段",让滑动窗口能拿到更大的命中。这也是 DEFLATE、Zstandard 等"后起之秀"在不同时代接力的共同方向。

LZ77 留下的两条遗产

第一:输出里既有"字面量",也有"指针"。原始字符混搭位置引用,成了后续字典编码器的通用语法。

第二:滑动窗口是一个内存有限的局部视野。它的好处是数据流式处理、首尾衔接自然;代价是跨越大窗口的重复会被错过。这一点,被后来的字典压缩、上下文模型等方法各自用不同方式补足。

一句话总结

LZ77 的伟大之处不在某个聪明的公式,而在一个朴素想法的工程化:把"我见过它"这件事,做成由偏移、长度、未匹配字符组成的最小指令,然后放在一个不断滑动的窗口里反复运行。理解了这一点,再去翻 DEFLATE、Zstandard、字典压缩的细节,会顺畅很多。

如果想继续了解字典编码与熵编码如何接力工作,可以读读《字典编码 vs 熵编码:一条压缩流水线上的两环》;要是想看现代压缩器的字典设计对比,可以翻翻《Zstandard 与 LZ4:现代字典压缩的设计取舍》。

如果平时主要在桌面上处理图片、压缩包这类文件,对工具内部的算法不必抠太深,选一个本地处理、批量友好、隐私不外传的桌面工具就够了——比如 闪压的文件压缩与解压模块就把这些原则落到了产品里。