Burrows–Wheeler 变换

BWT 把“字符前面接着什么上下文”转换成排序后相邻行中的局部规律。排序矩阵的首列按字符分组，末列则保留每一行向前一个字符；相同字符的出现次序稳定对应，使 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-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。的 backward search 维护后缀区间 $[l,r)$；前加字符 $c$ 后变为 $[C[c]+ran{k}_c(l),C[c]+ran{k}_c(r))$。区间空表示模式不存在。它把本页边界段要求的 rank/select 与采样定位接到 BWT 上；BWT 自身仍只是一列字符。