LZ77 与 LZSS 滑动窗口原理:压缩算法怎么"抄近路"

为什么压缩算法要"抄近路"

日常我们压缩一个文档,常常会发现:文档中存在大量重复片段。比如一段合同里反复出现的甲方名称,一段代码里反复出现的关键字,一篇文章里反复出现的常见词。如果把每个字符都老老实实存进文件,等于把同一段话写了很多遍,白白占空间。

LZ77 系列算法的核心,正是发现并利用"重复"这件事。它不像传统编码那样一个符号一个符号处理,而是先在已经读过的内容里"找一找",看看当前这段,是不是之前已经出现过。如果是,就只记录"它和前面哪里一样、往后匹配了多少个字符"——这就把一段重复内容压缩成几个数字。

这就是"滑动窗口"思路的来源:压缩不是静态的过程,而是一边读数据、一边维护一段"最近看过的内容",每读一个新片段都回头比对,看能不能复用。

滑动窗口到底是什么

想象你正在看一份很长的文档,眼睛只能回看最近几页,不能翻到全文搜索。这就是滑动窗口的直观感受:它是一段固定长度的"最近缓冲区",压缩过程随着读取位置往前移动,这个窗口也同步往前滑,旧内容从后端丢弃,新内容从前端进来。

压缩算法每读到一个新片段,会在窗口里"反向搜索":有没有完全一样的子串?如果有,就记录两个关键信息——距离(从当前位置往回数多少字节能找到匹配)和长度(往后还能连续匹配多少字节)。原本一长串字符,就被压缩成"距离 + 长度"这一对数字。

这一对数字,在压缩领域通常叫做"回溯指针 + 匹配长度"。它不存字符本身,只存"位置和长度",解码时只要照着这两个数字,就能从已解压的内容里复制出来。

LZSS 对 LZ77 的关键修补

原始 LZ77 的设计有个明显缺点:如果遇到一个根本找不到匹配的单字符,它仍然要输出一组"距离 + 长度"来标记"我什么也没匹配上",这一组数据反而比直接存一个字符还要占空间。这在文本里有大量短字符或生僻字符时,会让压缩率反而变差。

LZSS(LZ77 的一个实用变种)的修补思路很直接:先看有没有足够长的匹配——比如至少三个字符以上——才用"距离 + 长度"压缩;否则就老老实实存一个原字符。

这种"长短匹配分流"的策略,让 LZSS 在实际文本上的压缩效率大幅优于原始 LZ77。这也是为什么今天绝大多数压缩工具,底层逻辑都建立在 LZSS 这一套思路上,只是细节参数各不相同。

字典压缩的真正含义

很多文章会用"字典"来类比 LZ77 系列。这里的字典不是我们查单词的字典,而是"压缩过程中已经见过、随时准备复用的一段内容"。

滑动窗口里的所有内容,就构成了当前可用的"字典"。它不需要提前训练,不需要离线建模,而是随着压缩进行实时累积。这点和基于统计概率的熵编码形成鲜明对比——后者要先分析符号出现频率,再据此分配更短的编码给高频符号。

LZ77 系列字典编码的好处是:对任何类型的输入都立即可用,不需要预处理。今天我们熟知的 ZIP、7Z,都把 LZSS 作为默认的字典编码阶段,后面再接一层熵编码做二次压缩,这种组合叫做"流水线",几乎是无损压缩的事实标准。

为什么这种思路能省空间

节省空间的关键在于:重复的字符不重复存储。一组"距离 + 长度"的数字往往只需两到三个字节,但能替代十倍、几十倍长的重复片段。

在代码、文档、网页源码这些文本类内容里,重复片段尤其多,LZ77 系列的压缩效果通常非常显著。这也是为什么操作系统、软件安装包、源码仓库这种场景,几乎清一色使用基于 LZ77 系列的压缩格式。

对图片、视频这种已经经过专用编码的内容,LZ77/它的变种依然能再做一层二次压缩,因为即便编码过的数据,内部依然会有结构性的重复模式可被复用。

滑动窗口的代价与权衡

任何算法都有代价,LZ77 系列也不例外。滑动窗口越长,字典越大,理论上能匹配更远的重复,但查找匹配要消耗更多计算;窗口短,查找快,但可能错过远距离重复。

现代实现普遍用哈希表或二叉树来加速"在窗口里找匹配"这件事,把本应很慢的线性搜索变成接近常数时间的查找。这也是为什么今天压缩大文件虽然 CPU 占用不低,但不至于让人无法忍受——算法工程层面的细致优化,已经把过去理论上的瓶颈抹平了。

一句话总结

LZ77/LZSS 的精髓可以浓缩为一句话:当一段内容过去出现过,与其再存一遍,不如只告诉解码器"它在哪里、和它一样长"。 这就是现代无损压缩最常用、也最经得起时间检验的核心思想。

---

需要把任意文件打成 ZIP 或 7Z 压缩包?试试闪压的文件压缩模块:支持分卷压缩、AES-256 加密、批量操作,本地处理文件不出门。想深入理解压缩算法的整体流水线,可以看我们之前的压缩算法科普文,想了解字典编码与熵编码如何分工,可以读这篇字典编码与熵编码流水线。需要批量压缩办公文档,可以用 PDF 压缩 或 Office 压缩 模块,所有操作都在本地完成。