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

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

文本里充满重复的片段：同一个词、同一段前缀反复出现。LZ77 的思路是把「重复」换成一句话——「往回 distance 个字符、抄 length 个」，只在抄不到时才落下一个字面字符。这种「指回之前出现过的内容」的做法叫 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 的前缀寻找尽可能长的匹配。

下面拖动 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 · 压成三元组之后

上面的三元组流就是 LZ77 的输出。注意它本身还没有真正变小：每个三元组都占着 distance / length / next 三个字段。真正的体积收益来自两点——其一，一个 $(distance, length, \dots )$ 顶替了原文里 length 个字符；其二，这串三元组里的字面字节和长度 / 距离数值会再交给 Huffman 按频率编短。LZ77 负责「消重复」，Huffman 负责「压高频」，两步叠起来才是 DEFLATE。

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

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

decode · 重建原文 / 重叠回引

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

对每个 (distance, length, next):

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

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

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

下面输入一段文本，会先用 LZ77 编码成三元组，再逐个三元组单步解码，看输出如何一点点重建出原文。试试 aaaaaaaa 或 mississippi 这类含重复的输入，观察重叠回引。解码是动手编码的逆过程。

3.1 · 为什么 length 可以大于 distance

朴素的直觉是「回退 distance 个字符，那最多也只能抄 distance 个」。但 LZ77 的拷贝是逐字符、边写边读的：抄第 distance+1 个字符时，要读的位置已经是本步刚刚写出去的字符了。于是 $(1, 5, \dots )$ 这样的三元组会把同一个字符复制 5 遍——这等价于 run-length encoding,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 的收益直接取决于文本里有多少可被回引的重复。下面统计一段文本编码后，有多少字符是靠回引覆盖的、多少只能作为字面字符落下：

重复越多，「回引覆盖的字符」占比越高、三元组越少，压缩率越好；接近随机的文本几乎全是字面字符，LZ77 这一步几乎不省——这时真正起作用的是后面的 Huffman。两步互补：LZ77 管重复，Huffman 管高频。

4.2 · 三种 dictionary coding 的取舍

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

方案	字典是什么	token 形式	代表用途
LZ77	最近 N 个字符（滑动窗口）	每步都是三元组 (distance, length, next)	概念原型
LZSS	同 LZ77（滑动窗口）	1 bit 标志区分：字面字符或 (distance, length)，匹配太短就退化为字面，不强塞 next	DEFLATE 实际用的就是它
LZ78 / LZW	显式增长的编号字典	输出字典条目编号，边解码边重建同一份字典	GIF · 早期 `compress` · TIFF

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

4.3 · DEFLATE：两层叠加

RFC 1951 定义的 DEFLATE 把数据切成块，每块两步处理：

其一，LZ77（LZSS 形式）:32 KB 滑动窗口，匹配长度 3–258 字节。输出一串 symbol——要么是字面字节 (0–255)，要么是「长度 + 距离」对。

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

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

落到哪里:gzip / zlib 是 DEFLATE 加不同的外层封装（头部、校验和）;PNG 的 IDAT 用 zlib 流存像素；HTTP 的 Content-Encoding: gzip 压缩响应体。现代格式进一步用更强的熵编码替换 Huffman——zstd / brotli 用 ANS / 算术编码，但「先 dictionary coding 消重复，再熵编码压高频」这个两层结构始终未变。