第13章 Dictionary-Based Compressors：基于字典的压缩器

来源、版次与独立重写边界

“13 Dictionary-Based Compressors”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“13 Dictionary-Based Compressors”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“比较 LZ77、LZ78 与 LZW 的窗口、短语字典和解码同步”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：13 Dictionary-Based Compressors

• 13.1 LZ77：在本页正文中以“比较 LZ77、LZ78 与 LZW 的窗口、短语字典和解码同步”的对象、状态、复杂度或工程边界核对。
• 13.2 LZ78：在本页正文中以“比较 LZ77、LZ78 与 LZW 的窗口、短语字典和解码同步”的对象、状态、复杂度或工程边界核对。
• 13.3 LZW：在本页正文中以“比较 LZ77、LZ78 与 LZW 的窗口、短语字典和解码同步”的对象、状态、复杂度或工程边界核对。
• 13.4 On the Optimality of Compressors∞：在本页正文中以“比较 LZ77、LZ78 与 LZW 的窗口、短语字典和解码同步”的对象、状态、复杂度或工程边界核对。

从“重复子串为何还要逐字符付费”开始

dictionary-based compressors采取与上一章不同的入口。统计编码先估计 symbol probability；字典方法先发现 substring repetition，把一整段重复内容替换成 position、phrase id 或其他 token。

先预测字符串 abcabcabcabc。0阶模型只知道 a、b、c 各占三分之一，无法表达“每三个字符必然重复”；一个字典 phrase abc 却可直接复用三次。字典并非替代 bit coder：LZ parser 产生 distance、length、id、literal 后，仍要用整数编码、Huffman 或 Arithmetic Coding 把这些字段写成 bits。

静态字典适合已知领域，却要预共享或随文件发送；英语词典对意大利语、可执行文件或像素流未必有效。Lempel 与 Ziv 的关键做法是让输入自身成为动态 dictionary：双方从空状态或单字符表开始，按已解码前缀同步扩展，不必传整本词典。

因此字典压缩有两层成本：

减少 phrase 数不保证 bitstream 更短。一个很长 match 若来自极远距离，distance 可能比两个较近 match 更贵；工程解析器应比较 encoded bit cost，而不只是 longest match length。

LZ77：滑动窗口中的最长旧子串

LZ77维护已处理窗口 W 与待处理 buffer B。解析器找 B 的最长前缀 α，使它从当前位置向前 distance d 处出现；经典格式输出三元组 ⟨d,|α|,c⟩，其中 c 是 match 后的下一字符。无匹配时输出 ⟨0,0,B[1]⟩。

“在 W 中搜索”是便于理解的简称。本页允许 previous occurrence 从 W 开始并延伸进 B，因此 match 可以与当前输出重叠。dictionary 是窗口起点向右延伸的所有可复制子串，并不需要显式枚举。

LZSS：literal 与 copy 二选一

LZSS修正经典三元组的两处浪费：有 match 时不再附加后继字符，无 match 时不再写两个0。它输出 literal ⟨0,c⟩，或 copy ⟨d,ℓ⟩。

对 aabbabab，一种 LZSS greedy parse 是 a | a | b | b | ab | ab，对应 literal a、copy ⟨1,1⟩、literal b、copy ⟨1,1⟩、copy ⟨3,2⟩、copy ⟨2,2⟩。实际格式通常用独立 flag、混合 Huffman alphabet 或保留值域区分 literal 与 length。

ParseLZSS(position):
  (distance, length) = longestMatch(window, lookAhead)
  if length is shorter than the format threshold:
    emit Literal(input[position])
    advance by 1
  else:
    emit Copy(distance, length)
    advance by length

window 越大，可见的旧串越多，phrase 可能更长、数量更少；但索引内存、候选数和压缩时间上升。decompression 通常更快，因为它只按 token 顺序写 output，且 distance 限于几百 KB 或几 MB 时 source 很可能仍在 cache。

重叠 copy 为什么合法

若 token 是 ⟨2,6⟩，length 大于 distance。不能用一次不支持重叠的 bulk copy 从固定 source snapshot 读取；应按前向顺序执行：

for i = 0 .. length - 1:
  output[position + i] = output[position - distance + i]
position = position + length

前两次写出的字符会立即成为后四次的 source，因此 seed ab 可扩展为 abababab。这也是 run 与周期串压得很好的原因。解码器必须先验证 distance 非零、distance 不超过已有 output、length 不使输出越界，并限制 declared original size，防止损坏流造成越界或解压炸弹。

gzip：3-gram 哈希链与双 Huffman 字母表

brute-force 枚举窗口中每个起点并比较 look-ahead，成本太高。gzip 的核心索引把窗口内每个 3-gram 映射到 occurrence positions。当前 buffer 的首个3字符查到候选链后，只对这些位置计算 LCP，选择足够好的 match。

候选按最近到最远排列有两个好处：近 match 的 distance code 往往更短，cache locality 也更好。压缩等级可以扩大 window、检查更多 hash-chain entries 或进行更深 lazy matching；这提升找到长 match 的概率，却增加 CPU。

gzip/DEFLATE 不把 literal/copy 先写一个额外类型 bit。它把 literal symbols、end-of-block 与 copy lengths 放进第一棵 Huffman alphabet：解出 literal 就直接输出，解出 length 才去第二棵 distance alphabet 读取 distance。额外 low bits 表示同一 length/distance bucket 内偏移。

一次更长 match 未必 bit-optimal。设候选 j 的字段成本为：

解析应比较“本 token + 后续最优 suffix”的总成本。greedy longest match 只看当前 ℓ；lazy matching 至少比较“现在发 match”与“先发一个 literal、下一位置可能发更好 match”。更完整的 optimal parsing 可在位置图上做 shortest path，但计算更贵。

LZ78：显式的 prefix-complete phrase dictionary

LZ78不再用固定窗口隐式表示全部子串。字典 D 初始含 id 0 对应空串；在未解析 suffix S' 上找最长 dictionary phrase f，读取下一字符 c，输出 ⟨id(f),c⟩，并把 fc 作为新 phrase 加入 D。

每个新 phrase 只比已有 phrase 多一个字符，所以 D 必然 prefix-complete：若 phrase 在字典中，它的所有前缀也在。用 uncompacted Trie 时，每个 node 就是一个 phrase id，每条 edge 是一个字符；从 root 沿 S' 走到缺边，当前 node 给出 f，补一条 c edge 即完成查询和插入。

ParseLZ78(input):
  dictionary = { 0: empty }
  while input remains:
    f = longest dictionary phrase matching the input prefix
    c = the next input character
    emit (id(f), c)
    dictionary.add(f + c)
    consume length(f) + 1 characters

decoder 读到 ⟨id,c⟩，查出 phrase f，输出 fc，并以相同下一个 id 插入 fc；编码器和解码器自然同步。id 随输入增长，不能永远用小整数。大文件可选择 freeze dictionary、clear and restart，或按 LRU 删除；删除会使 id reuse 与双方一致性更复杂，实际格式通常使用明确 reset code。

LZ77 的 window 限制重复距离，却容纳窗口内任意 substring；LZ78 不遗忘旧 phrase，但只保存解析规则选出的子集。二者的“字典大小”和 match 能力不能只按条目数横向比较。

LZW：只输出 id，以及那个尚不存在的 code

LZW由 Welch 在1984年提出。初始化 D 为全部单字符，字节流通常占 ids 0到255。encoder 找最长 phrase f，输出 id(f)，把 f+c 加入字典；下一次解析从 c 开始。由于 c 成为下一 phrase 的首字符，无需像 LZ78 那样随 id 显式发送字符。

decoder 维护 previous phrase f'。读到下一 code 后得到 current phrase f''，输出 f''，并插入：

难点是 current code 偶尔恰好等于“下一条待插入 id”，所以字典里还查不到 f''。这发生于 encoder 刚插入 f'+f'[1]，随后立刻匹配它的情形。decoder 虽看似循环依赖，仍知道未知 f'' 的首字符必是 f'[1]，于是令 f''=f'+f'[1]，输出并插入即可。

DecodeLZW(codes):
  previous = dictionary[firstCode]
  emit previous
  for code in remaining codes:
    if code exists:
      current = dictionary[code]
    else if code equals nextDictionaryId:
      current = previous + first(previous)
    else:
      reject the stream
    emit current
    dictionary.add(previous + first(current))
    previous = current

LZW 必须定义 code width 从9位扩到10/11/12位的确切时刻、dictionary full 时 freeze 还是 clear、clear code 和 EOF code。encoder 与 decoder 只要差一个插入时机，就会从某个 code 起完全分叉。GIF 用 LZW 压缩调色板索引；它的颜色 palette 与像素 code stream 是不同层。

On the Optimality of Compressors：先说清楚“最优”的量词

optimality of compressors不能只说“输出小”。早期结果假设无限串来自 stationary ergodic source，LZ77/LZ78 的 ratio 渐近逼近源熵；现实中通常不知道生成源，因此本页转向可从单个字符串计算的 kth-order empirical entropy。

设 context ω 长度为 k，Sω 是所有紧随 ω 的字符组成的串，nω 是 ω 出现次数。一种等价写法是：

H0 只看全局 symbol counts；Hk 按 k-character context 分组，若每个 context 后继几乎确定，Hk 可接近0，即使全局字符比例均匀。

coarsely optimal 要求对每个固定 k，存在趋于0的 fk(n)，使所有增长序列满足：

但当 Hk 本身趋近0，加性 fk 仍可能比熵大很多。λ-optimality 更严格，要求输出率受 λ 倍经验熵加低阶相对项控制：

本页给出边界：LZ78 是 coarsely optimal，却存在低熵串使其 output/H0 比值无界，因此不是任意常数 λ 的最优；配合 RLE 的修改版可对 H0 达到3-optimal，但对更高 k 不成立。

固定 sliding window 的 LZ77 甚至不是 coarse optimal：构造重复周期长度略超 window 的字符串，Hk 接近0，而 parser 每轮已忘记足够远的对应块，只能产生线性数量 phrases。取消窗口后可得到 coarse optimal，并对 H0 有常数因子界；但远距离 references 的整数编码成本仍让它对 k≥1 存在无界相对差距。

这些反例不是说 gzip 或 LZW 实用性差，而是说明“有限内存、快速匹配、随机块恢复”与“对所有字符串、所有阶经验熵的渐近界”是不同目标。下一章的 Burrows-Wheeler Transform 会通过全局重排让相似 contexts 聚集，再借统计/游程编码获得更强的多阶界。

工程验收：parser、token coder 与 decoder 分开测

端到端 benchmark 同时报告 compressed bytes、bits/input-byte、parse tokens、average match length、distance distribution、compress/decompress MB/s、peak dictionary memory 与 block random-access latency。安全测试覆盖 truncated token、超窗 distance、巨大 length、非法 LZW code、reset 边界、整数溢出和 declared size 不一致。

先预测，再操作三个章专属实验

LZ77 token = (distance, length, next-symbol)

可重放工程合同

“13 Dictionary-Based Compressors”的实验必须保留：输入 hash、窗口、匹配、token、字典新增、输出位置与 round-trip。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

本章回顾

1. 基于字典的压缩器先把重复 substring 换成 token，再编码 token 字段。
2. LZ77 用滑动窗口隐式表示旧子串，经典 phrase 是 distance、length、next char。
3. LZSS 把输出改成 literal 或 distance-length，消除冗余字段。
4. overlap copy 必须前向逐字符，使刚写出的内容可继续充当 source。
5. gzip 以3-gram 哈希链筛候选，用搜索预算换速度与 match quality。
6. DEFLATE 把 literal 与 length 放入同一 Huffman alphabet，再单独编码 distance。
7. LZ78 输出 phrase id 与下一字符，显式字典天然 prefix-complete。
8. LZW 预装单字符并只输出 id，decoder 用 previous 与 current 首字符同步插入。
9. LZW 遇到尚不存在的 next id 时，用 previous+first(previous) 解开循环。
10. coarse 与 λ-optimality 的误差尺度不同；工程快不等于所有 Hk 下渐近最优。

名词解释