第14章 The Burrows-Wheeler Transform：块排序压缩

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

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

对“14 Block-Sorting Compression”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：14 Block-Sorting Compression

• 14.1 The Burrows–Wheeler Transform：在本页正文中以“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的对象、状态、复杂度或工程边界核对。
• 14.2 Two Other Simple Transforms：在本页正文中以“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的对象、状态、复杂度或工程边界核对。
• 14.3 The bzip Compressor：在本页正文中以“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的对象、状态、复杂度或工程边界核对。
• 14.4 On Compression Boosting∞：在本页正文中以“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的对象、状态、复杂度或工程边界核对。
• 14.5 On Compressed Indexing∞：在本页正文中以“跟踪 BWT、MTF、RLE 与熵编码如何逐层改变局部统计”的对象、状态、复杂度或工程边界核对。

从“可逆重排能否让普通编码器变聪明”开始

block-sorting compression先做一件反直觉的事：它不立即删除 redundancy，而是重排字符，让相似 context 的前驱聚到一起。后续简单的 Move-To-Front、Run-Length Encoding 与 entropy coder 才能吃到这些 runs 和偏斜分布。

先预测 abracadabra 的字符若只排序成 aaaaabbcdrr 是否够用。它压缩友好，却丢失所有次序，许多不同字符串会产生相同结果。目标必须同时满足两点：输出 locally homogeneous，又能无歧义恢复原串。

Burrows-Wheeler transform（，BWT）正好完成这个桥接。它是 permutation，不改变字符数；真正的 compressed bits 由后面的 MTF、RLE 与 statistical coding 产生。

Forward BWT：排序所有 cyclic rotations

给输入 s 追加唯一 sentinel $，规定它小于其他字符。概念算法：

1. 构造 s$ 的全部 n+1 个 cyclic left rotations。
2. 按从左到右的字典序排序这些 rows，得到矩阵 M'。
3. 读取最后一列 L，并保存 $ 的位置 r；也可把 $ 从 L 去掉，返回 L-hat 与 r。

对 abracadabra$，最后一列是 ard$rcaaaabb，删除 sentinel 得 ardrcaaaabb，r=3。结尾的 aaaabb 体现 local homogeneity：排序后，拥有相似右侧 context 的 rows 相邻，它们在 L 中对应的 preceding symbols 也被放在一个连续区域。

不同于字典 compressor 直接用 old substring reference，BWT 利用全局 context order。自然语言与很多 Markovian data 的下一个/前一个符号受邻近 context 影响，因此这些连续区域往往只有少数 distinct symbols。

ForwardBWT(s):
  t = s + sentinel
  rows = all cyclic rotations of t
  sort rows lexicographically
  L = last character of every sorted row
  return (L without sentinel, position of sentinel in L)

这个 pseudo-code 只用于定义。显式矩阵有 Θ(n²) 字符，16 MB block 会产生不可接受的概念空间。实现利用 sentinel 使“排序 rotations”等价于“排序 suffixes”：若 SA[i] 是第 i 小 suffix 的起点，则：

所以已有 Suffix Array 后只需线性扫描生成 L；总时间/IO 由 SA construction 决定，而不是构造旋转矩阵。

Backward BWT：first-last property 与 LF mapping

M' 的第一列 F 是 L 的 sorted permutation。只知道 F 不能还原次序；可逆性来自两个性质：

1. 同一 row 中，L[i] 是 F[i] 在原循环串中的 preceding symbol。
2. 相同字符在 L 与 F 中的 occurrences 保持相同相对次序。

LF mapping定义为：若 L[i] 的第 k 个 occurrence 对应 F[j] 的第 k 个 occurrence，则 LF[i]=j。

设 C[c] 是小于 c 的字符总数，Rank(c,i) 计数 L[0,i) 中 c 的 occurrences，则：

从 sentinel 对应 row 起，当前 L 字符是原串中当前位置的 predecessor；跳到 LF(row) 后再次读取 L，就向原串左移一个字符。重复 n 次可逆序填满 s，时间 O(n)。显式 LF array 占 O(n) words，也可用压缩 Rank structure 在线计算。

BuildLF(L):
  C = cumulative counts: C[c] = count of symbols smaller than c
  seen = all zeros
  for i = 0 .. length(L)-1:
    LF[i] = C[L[i]] + seen[L[i]]
    seen[L[i]] = seen[L[i]] + 1
 
InvertBWT(L, sentinelRow):
  row = sentinelRow
  for output position from end to start:
    output[position] = L[row]
    row = LF[row]

实际格式可能返回去掉 $ 的 L-hat 与 r，也可能保留 sentinel。inverse 的起始 row 和第一次输出字符随约定变化；算法正确性测试必须固定一种 convention，不应只凭例子调 off-by-one。

MTF：把局部同质字符统一成小整数

Move-To-Front（，MTF）初始化为 alphabet 的固定顺序。处理字符 c 时，输出它当前 index p，再把 c 移到 front。inverse 用同一 initial list：取 index p 处字符输出，再移到 front，双方始终同步。

若 L 中同字符连续出现，第一个可能输出较大 index，之后都输出0；若一个小集合频繁交替，输出通常也只在0、1、2附近。不同局部区域即使使用不同字符，也统一变成 small-integer alphabet。本页例 bananacocco 从列表 a,b,c,n,o 得到 11311134101。

MTF 自己通常不缩短序列。它利用 locality of reference 改变 distribution，随后可用 Elias integer code、RLE 或统计 coder。它不与 Huffman“静态前缀码最优”矛盾：同一 symbol 在不同时间可能对应不同 index/codeword，MTF pipeline 不属于静态逐符号 prefix-code 类别。

RLE0：只压 MTF 产生的零游程

普通 RLE 把 maximal run c^ℓ 变成 ⟨ℓ,c⟩。run 长时收益大，run 短时 pair 反而膨胀。BWT+MTF 的结构明确告诉我们最值得压的是0-runs，因此 bzip 采用 restricted RLE0，而不是为所有 symbol 都付 run header。

非零 MTF indices 先加1，腾出0和1两个 alphabet symbols 专门表示 run code。Wheeler code 对长度 ℓ：

例如五个0：ℓ+1=6，binary 为110，删除 leading 1 后写10。decoder 读 maximal 0/1 sequence，补回 leading 1、转整数再减1。输出 digit 数不超过原0-run长度；长 run 越省。

bzip Compressor：每一层为下一层制造分布

bzip compressor的主链是：

1. BWT 把相似 context 的 preceding symbols 聚成局部同质 L。
2. MTF 把重复/近邻字符变成0和 small integers。
3. RLE0 把0-runs 变成短 0/1 code。
4. Huffman-like statistical stage 对最终 alphabet 编码。

preamble 还要保存 block original size、CRC、sentinel/primary index、使用过的 alphabet 与统计表。单看 transforms 的 symbol count 不能代表文件大小。

bzip 按 block 工作，因为 forward BWT 与 inverse LF 的内存访问较分散，整文件全局排序昂贵。大 block 有更长 context 和更强 homogeneity，通常 compression ratio 更好；但 SA/BWT construction memory、compression latency 与 inverse cache misses 都增加。与 LZ window 不同，扩大 BWT block 也会明显拖慢 decompression。

Compression Boosting：用多个0阶块模拟k阶模型

compression boosting解释了 BWT 不只是“看起来 runs 多”。在 sorted rows 中，以同一 context w 开头的 rows 连续；其 L 区段 Lw 恰好收集原串中 w 的 preceding symbols。

若0阶 compressor C0 对任意 t 使用至多 |t|H0(t)+overhead(t) bits，把 L 按所有 k-context 分成 Lw 并逐块压缩，则主项：

因为 Lw 与原串中跟随/前驱同一 context 的 symbol multiset 对应。块 header 与 C0 redundancy 形成 additive term；Arithmetic 的 per-block overhead 很小，Huffman 每块最多不足1 bit/symbol 的简单界则更粗。

更强的 booster 不必事先固定 k。可在 LCP/ suffix-tree induced intervals 上动态规划选择 partition，使“各块 compressed cost + boundary cost”最小，并达到不差于任意固定 k partition 的结果。这里的提升不是训练一个 k阶概率表，而是用 BWT 的全局排列把高阶依赖物理地分组。

Compressed Indexing：BWT 既能压，也能搜索

compressed indexing沿用 BWT、C 与 Rank。FM-index 可理解为 compressed suffix array，也可理解为 searchable bzip representation。

核心操作：

• Count(P) 返回以 P 为 prefix 的 sorted rows 区间 [first,last]，区间长度是 occurrence count。
• Locate(P) 把这些 rows 映射回原文 positions。
• Extract(i,j) 通过采样与 LF steps 恢复指定 substring。

backward search 从 P 的最后字符开始。若当前 [first,last] 是以 suffix P[i..] 开头的 rows，向左加字符 c=P[i-1]：

对 abracadabra$ 的 pattern ab，先由 F 中 b 的范围得 [6,7]；再用 L 的 a-ranks 扩为 [2,3]，因此出现2次。每轮只做常数次 Rank，若 Rank O(1)，Count 时间 O(|P|)。

BackwardSearch(P):
  first = 0
  last = n - 1
  for c in reverse(P):
    first = C[c] + Rank(c, first)
    last  = C[c] + Rank(c, last + 1) - 1
    if first > last:
      return empty
  return [first, last]

Locate 需要 SA position。FM-index 每隔 μ 个 text positions 采样 row→position；对未采样 row 反复 LF，至多 μ 步遇到 sample，再把步数加回。采样空间约 n log n / μ bits，定位每个 occurrence 最坏 O(μ) Rank calls。μ 小更快更大，μ 大更省更慢。

Extract 同理采样 text/SA 对应点，再沿 LF 向左生成字符。Rank structure 可用 wavelet tree、bitvectors 与 succinct dictionaries 在接近 nHk(s) 空间支持访问和计数；这让 index 接近 bzip 的空间，却保留全文搜索。

Rank 的定义有两种常见 convention：inclusive L[0..i] 或 half-open L[0..i)。公式必须成套使用。上文统一 half-open；测试应覆盖 first=0、last=n-1、字符不存在、单字符 pattern、sentinel 与重复字符，否则 off-by-one 会静默漏掉首尾 occurrence。

端到端实现与验证

性能报告至少包含 block size、bits/input-byte、BWT construction time、inverse time、peak memory、cache misses、MTF/RLE0 分布、Rank ns/query、Count µs/character 与 Locate occurrences/s。正确性覆盖空块、单字符、全相同、全不同、重复 sentinel byte 的 escaping、CRC、truncated metadata、corrupted run 与超大 primary index。

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

LF(i) = C[L[i]] + Occ(L[i], i)

可重放工程合同

“14 Block-Sorting Compression”的实验必须保留：旋转/后缀次序、L 列、primary、Occ、MTF/RLE 流与逆变换结果。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

本章回顾

1. 块排序压缩先重排 context，再交给简单局部变换与统计编码。
2. Burrows-Wheeler变换排序带 sentinel 的 cyclic rotations，输出 L 与 primary index。
3. BWT 不缩短输入；它把相似右 context 的 preceding symbols 聚到 L 的连续区域。
4. 实现不构造平方矩阵，而由 Suffix Array 的前驱字符在线性时间导出 L。
5. LF 映射连接 L/F 中同字符同 occurrence，迭代 LF 可逆序恢复原串。
6. MTF 把 locality of reference 变成0和 small integer；RLE0 专门压零游程。
7. bzip 依次执行 BWT、MTF、RLE0、统计编码，并按 block 平衡空间与速度。
8. compression boosting 把 L 按 context 分块，用多个 H0 coder 达到 Hk 主项。
9. FM-index 的 backward search 用 C 与 Rank 在压缩 L 上维护 suffix-row interval。
10. Locate 与 Extract 通过 LF sampling 以辅助空间换查询步数。

名词解释