LZ77 滑动窗口压缩

LZ77 是一类无损压缩器，它将重复输入替换为指向有限历史窗口的引用。最初的 1977 年设计使用滑动字典；实际格式会自行选择令牌语法、匹配查找器和熵编码器。

字面量、历史和匹配 #

在输入位置上，编码器会在之前输出的字节中搜索匹配前缀。如果不存在有用的匹配，就输出字面量；否则输出至少包含距离和长度的回溯引用。某些格式在每次匹配后添加一个字面量；其他格式则输出独立字面量和匹配组成的流。解码器从当前输出位置之前 distance 个字节处复制 length 个字节。

复制可能与源重叠。如果历史以 a 结尾，距离为 1、长度为 5 的匹配会产生 aaaaa：每个复制的字节都会成为下一个字节的源。解码器必须按字节正向复制，或使用具有等价级联语义的循环。memcpy 和快照式的 memmove 都不能实现每一种有效的重叠匹配。

匹配搜索和解析 #

更大的窗口可以找到更远的重复内容，但会消耗更多内存，并需要更多距离位。哈希链、二叉树、后缀结构和有界候选搜索会在压缩比与 CPU 时间之间进行权衡。

贪心解析器会选择当前位置的最长匹配。懒惰解析器先记录一个候选匹配，检查下一个位置是否有更好的匹配，并在这样可以改善总成本时改为输出字面量。动态规划可以搜索更大的解析空间，但需要更多 CPU 和内存。这些编码器选择都不会影响解码器正确性，因为令牌流是自包含的。

边界和防御性解码 #

每种格式都会定义自己的最小匹配长度、最大长度、窗口大小和距离编码。例如， DEFLATE 允许距离最大为 32 KiB，长度最大为 258 字节。解码器必须拒绝大于当前已有历史的距离、无效的长度或距离代码、计算输出位置时的整数溢出，以及超出调用者限制的输出。资源限制应同时覆盖总输出量和工作量，因为很小的输入也可能扩展为非常大的输出流。

DEFLATE 和相关格式 #

DEFLATE 使用霍夫曼树对字面量/长度符号和距离符号进行熵编码，然后使用 LZ77 窗口获取被引用的字节。LZ4 围绕相同的复制操作使用紧凑的令牌格式，而 Zstandard 将窗口化 LZ 匹配阶段与不同的熵编码器结合起来。LZ78 和 LZW 则维护短语的显式字典；不能用它们的字典更新规则替代 LZ77 的历史引用。

参考资料 #

• J. Ziv 和 A. Lempel，《Sequential Data Compression 的通用算法》，IEEE Transactions on Information Theory，1977 年。
• RFC 1951：DEFLATE
• RFC 7932：Brotli 压缩数据格式，介绍另一种窗口化 LZ 设计。