Burrows–Wheeler 变换

BWT 把“字符后面接着什么上下文”转换成排序后相邻行中的局部规律。排序矩阵的首列按字符分组，末列则保留每一行向前一个字符；相同字符的出现次序稳定对应，使 LF 可以沿原文本逐字符后退。这条稳定对应把排序后的行重新连接成文本中的先后关系。

边界与用途 ​

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

不附终止符的版本可以另外保存原始文本所在的行号，即主索引，用它定位逆变换的起点。

循环移位等价类理路词的共轭与循环移位Conjugate words · Cyclic rotation of a word · Circular string · 词的旋转等价把词切为 uv 再连接成 vu 定义旋转等价；本原根的长度决定不同旋转的个数和相同旋转起点的间隔。明确哪些线性记录只相差切口；最小循环表示理路字典序最小循环移位Lexicographically minimal string rotation · Least circular shift · Minimal rotation · 最小表示法通过首次失配一次排除一段旋转起点，在线性时间求循环串的字典序最小表示，并以本原根周期恢复全部并列起点。可在线性时间选取一个规范代表，并在周期串上报告全部并列起点。这种选择会有意忘记原切口，不能代替无终止符 BWT 为恢复原始线性文本保存的主索引。需要把一般词分成唯一的 Lyndon 块时，可使用Duval 算法理路Duval 线性 Lyndon 分解算法Duval's algorithm · Duval factorization · Duval算法用三个索引维护 Lyndon 块的重复前缀，遇到较小字符或串尾就批量输出完整块，在 O(n) 时间和常数工作空间内生成 CFL 分解。；该分解与 BWT 的排序末列是不同输出。

banana$ 的完整轨迹 ​

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

首列 $F$ 为 $aaabnn。以从 0 开始的下标计，末列中第 2 个 a 位于位置 5，首列中第 2 个 a 位于位置 2，因此 $LF(5)=2$。这两个位置对应原文中同一次字符出现，所在的循环行相差一次向前移位。

逆变换与区间更新 ​

采用从 0 开始的下标，令 $C[c]$ 表示文本中严格小于 $c$ 的字符数，${\mathrm{rank}}_c(L,i)$ 统计半开前缀 $L[0,i)$ 中的 $c$。则

每个字符的各次出现分别占据 $F$ 中互不重叠的连续编号，因此 LF 是行号上的排列理路排列Permutation有限集合到自身的双射，或其元素的有序排列。。它把当前行的最后一个字符移到开头，跳到对应的循环行。从末列中 $ 所在行出发，反复读取当前末列字符并应用 LF，读取与文本等长的字符后，将序列逆序，就得到带终止符的原文本。

FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。的 backward search 维护后缀区间 $[l,r)$；前加字符 $c$ 后变为 $[C[c]+{\mathrm{rank}}_c(L,l),C[c]+{\mathrm{rank}}_c(L,r))$。这里模式不含终止符，以免把跨文本末尾的循环片段算成普通出现。区间空表示模式不存在。区间更新使用 $C$ 与 rank 查询；若还要报告匹配在原文中的位置，可以配合采样的后缀数组值进行定位。