Burrows–Wheeler 变换

定义与例子 ​

列出 (T$) 的全部循环移位，字典序排序成矩阵，BWT 是最后一列；等价地由后缀数组公理库后缀数组Suffix array按字典序排列字符串全部后缀起始位置的数组索引。取每个后缀起点前一字符。banana$ 的排序后 BWT 为 annb$aa。

第一列 $F$ 是 $L$ 排序所得。相同字符在 $L$ 中第 $k$ 次出现，对应 $F$ 中同字符第 $k$ 次出现，称 LF 性质；从终止符行反复 LF 即可逆向恢复文本。唯一终止符固定起始行，否则循环串只能恢复到旋转等价类。

边界与用途 ​

BWT 长度与输入相同，本身没有压缩；它把相似上下文字符聚集，后续 run-length、move-to-front 或熵编码才缩短。没有终止符时，循环移位排序与后缀排序也不等价。

BWT 不是哈希，也不单独支持模式搜索；配合 rank/select 和采样位置才形成 FM-index。

多个终止符或终止符不唯一最小时，循环行锚点与后缀次序都要重新定义。变换可逆也不表示加密；它只是输入字符的一种排列，不提供保密性。

banana$ 的完整轨迹 ​

按字典序排列后缀为 $、a$、ana$、anana$、banana$、na$、nana$，对应 suffix array $(6,5,3,1,0,4,2)$。每个起点取前一字符（起点 0 取终止符）得到 BWT annb$aa。这比显式构造全部循环移位省空间，却与带唯一终止符的移位矩阵定义等价。

首列 $F$ 为 $aaabnn。在末列中第 2 个 a 与首列中第 2 个 a 对应同一循环行，因为稳定排序保留相同字符的相对 occurrence rank；这就是 first–last 性质。

逆变换与区间更新 ​

给末列位置 $i$，$LF(i)=C[L[i]]+ran{k}_{L[i]}(L,i)$ 跳到同一行前移一字符的位置。从 $ 所在行反复 LF，逆序读出字符便恢复唯一文本。没有终止符或主索引，只能恢复某个循环旋转。

FM backward search 维护后缀区间 $[l,r)$；前加字符 $c$ 后变为 $[C[c]+ran{k}_c(l),C[c]+ran{k}_c(r))$。区间空表示模式不存在。这需要 rank 索引与采样定位，BWT 自身只是一列字符。

压缩与安全边界 ​

BWT 不减少字符数。相似上下文使同字符形成 runs，run-length/熵编码才利用它；在随机文本上 runs 可能不短。变换可逆所以不是哈希，更没有保密性。

参考资料

• Burrows, Wheeler, A Block-sorting Lossless Data Compression Algorithm, 1994.
• Ferragina, Manzini, “Opportunistic Data Structures with Applications,” FOCS 2000.