dictionary coding · 滑动窗口 · 编码 / 解码 · DEFLATE

LZ77 滑动窗口压缩 · 拆解 dictionary coding

文本里充满重复的片段：同一个词、同一段前缀反复出现。LZ77 的思路是把「重复」换成一句话——「往回 distance 个字符、抄 length 个」，再补一个字面字符。（每步都带字面字符是经典 LZ77 的设计；工程实现的 LZSS 才改成字面与匹配二选一，见 §5。）这种「指回之前出现过的内容」的做法叫 dictionary coding，字典就是一段滑动窗口。本系列从窗口的两个缓冲区讲起，单步跟一遍最长匹配编码、再单步把三元组流解码还原（顺便看 length > distance 的重叠回引），最后理解它如何与 Huffman 编码组成 DEFLATE，支撑起 gzip / zlib / PNG。本页四节：滑动窗口 → 动手编码 → 解码 → DEFLATE 与变体。

1 · 滑动窗口：字典就在刚读过的字符里

concept · search buffer + look-ahead

LZ77 不维护一份外部字典，它的「字典」就是刚刚读过的那段原文。一个固定大小的窗口在文本上从左向右滑动，被一个 cursor 分成两半：

search buffer（cursor 左侧，长度 ≤ window size）：已经读过、可以被回引的内容，即字典。

look-ahead buffer（cursor 右侧，长度 ≤ look-ahead size）：接下来待编码的字符。

每一步都在 search buffer 里，为 look-ahead 的前缀寻找尽可能长的匹配。

本节只看「窗口的样子」，真正逐步产出三元组在 §2。

图 1-1 · 滑动窗口的两个缓冲区。可拖动 cursor 或调整缓冲区大小，观察窗口如何随之滑动、当前位置能匹配到多长的回引。

1.1 · 为什么是「滑动」窗口

窗口大小固定（真实 DEFLATE 是 32 KB）,cursor 每编码完一段就向右移动，于是 search buffer 的左边界也跟着右移——太久以前出现的内容会滑出窗口、不再能被回引。这是一个工程取舍：窗口越大，能利用的重复越远、压缩率越高，但匹配搜索越慢、distance 字段需要的位数也越多。

distance 的含义：它是「从 cursor 往回数多少个字符到匹配起点」，不是绝对下标。所以同一段重复，无论出现在文本多靠后的位置，只要它和上一次出现的相对距离不变，distance 就一样——这让回引可以在整个窗口内复用。

2 · 编码：每步的最长匹配与三元组

algorithm · 最长匹配单步编码

编码是一个循环，每一轮处理 cursor 处的内容，产出一个三元组 (distance, length, next)：

在 search buffer 里，为 look-ahead 的前缀找最长匹配（可一直比到 look-ahead 内部）。

命中（length > 0）：输出 (distance, length, next)——回退 distance、抄 length 个，再加一个匹配中断处的字面字符 next。

未命中(length = 0)：输出 (0, 0, next)——没有可回引的内容，只落一个字面字符。

随后 cursor 前移 length + 1（抄走的 length 个 + 那一个字面字符），回到循环开头。

「+1 的字面字符」是经典 LZ77 的设计：它保证每一步都至少消化掉一个新字符，循环必然推进，也让没有任何匹配的全新字符有办法被表达。一段文本会被压成一串三元组，可逐个执行观察。

图 2-1 · 编码的逐三元组执行：每轮在窗口里找最长匹配，输出一个三元组并把 cursor 前移 length 加一。

2.1 · 压成三元组之后

§2 产出的三元组流就是 LZ77 的输出。注意它本身还没有真正变小：每个三元组都占着 distance / length / next 三个字段。真正的体积收益来自两点——其一，一个 (distance, length, next) 顶替了原文里 length 个字符——但这只在 length 够大时才划算：length 为 1、2 的匹配换不回一个 distance 字段的开销，所以 DEFLATE 规定最小匹配 3 字节、LZSS 设匹配阈值（实测本页覆盖率一节的默认文本，27 个三元组里 25 个 length 不超过 1）；其二，这串三元组里的字面字节和长度 / 距离数值会再交给 Huffman 按频率编短。LZ77 负责「消重复」，Huffman 负责「压高频」，两步叠起来才是 DEFLATE。

窗口越大，匹配越多：把 window size 调大，远处的重复也能被回引，三元组数量通常下降；但代价是每步搜索更慢、distance 数值更大。真实实现（如 zlib）用 hash chain 等结构加速这步最长匹配搜索，而不是此处演示的朴素逐位扫描。

3 · 解码：照着三元组把原文抄回来

decode · 重建原文 / 重叠回引

解码不需要任何搜索，因此比编码快得多——这正是 LZ77 这类非对称压缩在「压一次、解多次」场景（网页、安装包）里的优势。拿到三元组流，逐个执行：

对每个 (distance, length, next):

若 length > 0：从当前输出末尾回退 distance 个字符，逐个抄 length 个字符追加到输出。

再把字面字符 next 追加到输出。

处理下一个三元组，直到流结束。

输入的文本会先用 LZ77 编码成三元组，再逐个三元组单步解码，输出一点点重建出原文。aaaaaaaa（distance 为 1）与 abcabcabcabc（distance 为 3 的周期重叠）都会产出 length > distance 的重叠回引；实测 mississippi 在本页参数下最长只到 length = distance，看不到重叠。解码是动手编码的逆过程。

图 3-1 · 解码的逐三元组还原。可换输入观察 length 大于 distance 时的重叠回引如何边写边读。

3.1 · 为什么 length 可以大于 distance

朴素的直觉是「回退 distance 个字符，那最多也只能抄 distance 个」。但 LZ77 的拷贝是逐字符、边写边读的：抄第 distance+1 个字符时，要读的位置已经是本步刚刚写出去的字符了。于是 (1, 5, next) 这样的三元组会把同一个字符复制 5 遍——distance 为 1 时这退化成 run-length encoding;distance 大于 1 时复制的是周期为 distance 的整段模式（实测 abcabcabcabc 得 (3, 8, c)），比 RLE 更一般。LZ77 因此不必为「连续重复」设专门机制。

编码 / 解码的不对称：编码端要在窗口里搜索最长匹配（慢），解码端只是按指令做内存拷贝（快）。所以 gzip 这类格式压缩时可以花很多时间挑最优匹配 / 选压缩级别，而几乎不影响解压速度——这正是它适合分发场景的原因。

4 · 应用实例：LZ77 + Huffman = DEFLATE

applications · DEFLATE / gzip / PNG

经典 LZ77 的三元组流并不是最终格式——它本身还有冗余。真实世界的压缩格式在 LZ77 之上做了两件事：一是改用更省的 token 形式（LZSS），二是再叠一层 Huffman 熵编码。这两步组合的产物就是 DEFLATE，也就是 gzip / zlib / PNG / HTTP Content-Encoding: gzip 共同的内核。

4.1 · 先看一段文本里「回引」占了多少

LZ77 的收益直接取决于文本里有多少可被回引的重复。统计一段文本编码后，有多少字符靠回引覆盖、多少只能作为字面字符落下：

图 4-1 · 一段文本编码后回引覆盖的字符数与字面字符数的统计对照。

重复越多，「回引覆盖的字符」占比越高、三元组越少，压缩率越好；接近随机的文本几乎全是字面字符，LZ77 这一步不但不省、反而净膨胀（实测 200 个随机小写字母编出 104 个三元组）；这种数据 Huffman 同样压不动，DEFLATE 的兜底是 stored block——原样存放，膨胀被锁在每块 5 字节的块头。两步互补：LZ77 管重复，Huffman 管高频，都失效时还有第三条退路。

4.2 · 三种 dictionary coding 的取舍

Ziv 与 Lempel 在 1977 / 1978 给出两条主线，后续衍生出整个家族。它们的差别在于**「字典」是什么**:

方案	字典是什么	token 形式	代表用途
LZ77	最近 N 个字符（滑动窗口）	每步都是三元组 (distance, length, next)	概念原型
LZSS	同 LZ77（滑动窗口）	字面与匹配二选一，匹配太短就退化为字面，不强塞 next。教科书写法用 1 bit 标志区分，DEFLATE 则把字面与长度并进同一张字母表、靠符号值本身区分	DEFLATE 走的就是这条路
LZ78	显式增长的编号字典	输出 `(前缀编号, 下一个字符)` 二元组，边解码边重建同一份字典	后续 LZW 的基础
LZW	预置全部单字符的编号字典	只输出条目编号（省掉字符字段），需处理自引用的 KwKwK 特例	GIF · 早期 `compress` · TIFF

本系列的单步 demo 用最直观的经典 LZ77 三元组；工程实现普遍是 LZSS 那种「字面 / 匹配」二选一的形式，以避免每步都被迫附带一个字面字符。

4.3 · DEFLATE：两层叠加

RFC 1951 定义的 DEFLATE 把数据切成块，每块可选三种编码方式：stored（原样存放，既不做 LZ77 也不做 Huffman）、fixed Huffman 与 dynamic Huffman。后两种都走下面这两层：

其一，LZ77（LZSS 形式）：32 KB 滑动窗口，匹配长度 3–258 字节、距离 1–32768。输出一串 symbol——要么是字面字节 (0–255)，要么是「长度 + 距离」对，另有符号 256 表示块结束。长度不是 258 个码：257–285 共 29 个长度码各带 0–5 位额外位，距离则是 30 个码各带 0–13 位额外位。

其二，Huffman：对上一步的 symbol 流做熵编码。字面字节与长度共用一棵 Huffman 树、距离用另一棵，高频 symbol 得到更短的 bit 串。两棵树可以是预定义的 (fixed)，也可以按本块统计动态构建 (dynamic)并写进块头。

于是「重复的词组」先被 LZ77 换成短引用，剩下的「高频字节 / 高频长度距离」再被 Huffman 编短。想看第二步如何按频率分配 bit、为何 prefix code 能无歧义解码，见 Huffman 编码树系列。

落到哪里：gzip / zlib 是 DEFLATE 加不同的外层封装（头部、校验和）;PNG 的 IDAT 用 zlib 流存像素；HTTP 的 Content-Encoding: gzip 压缩响应体。现代格式在熵编码层各走各路——zstd 用 **FSE（tANS）**编长度与距离、字面量仍走 Huffman，LZMA 用 range coder，而 brotli 仍是 Huffman，收益来自上下文建模与内置静态字典；但「先 dictionary coding 消重复，再熵编码压高频」这个两层结构始终未变。

6 · 参考文献

Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337–343. https://doi.org/10.1109/TIT.1977.1055714
Ziv, J., & Lempel, A. (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5), 530–536. https://doi.org/10.1109/TIT.1978.1055934
Storer, J. A., & Szymanski, T. G. (1982). Data compression via textual substitution. Journal of the ACM, 29(4), 928–951. https://doi.org/10.1145/322344.322346
Welch, T. A. (1984). A technique for high-performance data compression. Computer, 17(6), 8–19.
Deutsch, P. (1996). DEFLATE compressed data format specification version 1.3 (RFC 1951). IETF. https://datatracker.ietf.org/doc/html/rfc1951