后缀树与后缀数组

人类基因组包含约 32 亿个碱基对。生物信息学家每天都需要在其中寻找一段几十个字符的 DNA 序列——这是一个对 32 亿字符字符串做模式匹配的问题，而且同一个基因组上要做的不是一次查询，是成千上万次。能在合理时间内完成这项工作的数据结构，正是后缀树（Suffix Tree）和后缀数组（Suffix Array）。

问题背景：字符串的全局索引#

普通字符串搜索（如 KMP 算法）对单次搜索已经是线性时间。但"线性"在这里意味着每次查询都要把 32 亿个字符从头扫一遍：查一千个不同的片段，就要扫一千遍基因组。对同一个文本做大量查询时，正确的做法是先建一次索引，之后每次查询只看模式串本身的长度——查一段 30 个字符的序列，代价只跟这 30 个字符有关，和基因组有多长无关。后缀树和后缀数组就是这样的索引结构。后缀树最早由 Peter Weiner 在 1973 年提出，当年被称为"年度算法"。

后缀与后缀树#

给定字符串 $S$（长度 $n$），其第 $i$ 个后缀 $S[i..n]$ 是从位置 $i$ 到末尾的子串。$S$ 共有 $n$ 个后缀（加上空字符串共 $n+1$ 个）。

后缀树（Suffix Tree） 是将所有后缀插入一棵压缩前缀树（Trie）后得到的树，其中：

• 每个从根到叶子的路径对应一个后缀
• 路径上的标签拼接得到该后缀本身
• 内部节点（分支点）对应多个后缀共有的公共前缀
• 叶节点存储对应后缀的起始位置

关键性质：$S$ 的所有子串都对应后缀树中某个节点的路径前缀。因此，查找模式 $P$ 是否存在于 $S$ 中，只需在后缀树中沿 $P$ 的字符路径向下走，时间复杂度为 $O(|P|)$——与文本长度无关。

线性时间构建：Ukkonen 算法#

天真地将所有 $n$ 个后缀插入前缀树，时间和空间都是 $O(n^2)$。1995 年，埃斯科·乌科宁（Esko Ukkonen）提出了在线性 $O(n)$ 时间内构建后缀树的算法。Ukkonen 算法的核心思想是在线构建（Online Construction）：从左到右逐个读入字符，每读入一个字符，当前文本的全部既有后缀都被自动延长——这一步几乎不用做任何事，因为叶子边的标签是"到当前位置为止"的活引用；真正要做的只是为新产生的那个后缀（整个当前文本）找到落点。

朴素地找落点要从根重新走一遍，累计 $O(n^2)$。Ukkonen 用两件武器把摊还代价压到常数：

• 隐式后缀树（Implicit Suffix Tree）：构建的中间阶段，许多后缀尚未显式落到叶子，而是"藏"在某条边的中间。算法不急于展开它们，只维护"最深处还需工作的位置"（活动点，Active Point）与"还剩多少个后缀待处理"（剩余计数，Remainder）。终止符 $ 在最后加入，强制所有后缀落为叶子，隐式树变为显式树。
• 后缀链接（Suffix Link）：每个内部节点（对应某个子串 $\alpha$）存一条指向"$\alpha$ 去掉首字符所得子串"节点的链接。处理完一个后缀的分裂后，下一个待处理的后缀正是去掉首字符的那个——沿后缀链接一步跳达，而不必从根重走。这正是"不重复遍历"的来源。

内部节点至多 $n-1$ 个（每次分裂只新增一个），每条边只存起止位置的一对整数而非子串本身，因此总空间 $O(n)$——这就是"压缩"前缀树的含义。

这个算法实现复杂，但时间和空间均为 $O(n)$（以字母表大小为常数时）。早期线性构建算法还有 Weiner（1973，后缀树的最初提出者）和 McCreight（1976）的方案，均先于 Ukkonen。

后缀数组：更实用的替代#

后缀树有一个实际问题：常数因子大，内存消耗高（每个字符约需 20–40 字节）。后缀数组（Suffix Array） 是 1990 年由 Gene Myers 和 Udi Manber 提出的替代方案——把所有后缀按字典序排序，只记录其起始位置的排列，得到一个整数数组 $SA[0..n-1]$。

以 $S = \text{banana}$ 为例：

在后缀数组上，对模式 $P$ 的查询变为二分搜索（所有包含 $P$ 的后缀在 SA 中是连续的区间），时间复杂度 $O(|P| \log n)$（可降至 $O(|P| + \log n)$）。

最长公共前缀数组（LCP Array）：记录后缀数组中相邻后缀的最长公共前缀长度，与后缀数组配合，能在 $O(1)$ 时间内回答任意区间内后缀的 LCP 查询，是很多高级应用的基础。

LCP 的线性构造（Kasai 等，2001）：LCP 数组不必逐个后缀两两比较。按文本位置顺序处理后缀时，存在一条单调性——"下一个后缀与前一名的 LCP 至少比当前少 1"——使得每个字符至多被扫两次，一遍线性扫描即可建成整个数组。这一结果让"后缀数组 + LCP"在功能上完整覆盖了后缀树的绝大多数用途，而空间常数小一个数量级。实践中后缀树因此几乎被全面取代：理论课教后缀树，工程实现用后缀数组。

线性时间构建后缀数组#

直接对所有后缀排序需要 $O(n^2)$（比较每个后缀最坏需要 $O(n)$）。线性时间构建算法：

• DC3/Skew 算法（Kärkkäinen & Sanders, 2003）：分治构建，将 $2/3$ 的位置构建子问题，递归解决后合并
• SA-IS（Nong, Zhang & Chan, 2009）：实践中最快的线性时间算法，内存效率高，广泛用于工业实现

SA-IS 的核心机制"诱导排序（Induced Sorting）"值得一看，它是"用少量已排好序的信息撬动全局"的范例。先把每个位置按"该后缀与后继后缀的大小关系"分为 L 型与 S 型，其中 S 型且前一个是 L 型的位置称为 LMS 位置。关键观察是：LMS 子串的相对顺序一旦确定，所有后缀的顺序就能被"诱导"出来——把已排序的 LMS 后缀放进桶（按首字符分桶），一遍正向扫描即可把所有 L 型后缀插到桶内正确位置，再一遍反向扫描插入 S 型。而 LMS 子串至多 $n/2$ 个，对它们递归即可。每层递归问题规模减半、扫描代价线性，总工作量仍是线性。

核心应用#

最长重复子串（LRS）：LCP 数组的最大值所在位置对应的两个后缀的公共前缀即为最长重复子串。

最长公共子串（LCS）：将两个字符串用特殊分隔符拼接，构建联合后缀数组，查找来自不同字符串的相邻后缀的最长公共前缀。

基因组比对：BWA-MEM、Bowtie 等主流基因组比对工具基于后缀数组（配合 Burrows-Wheeler 变换），能在数分钟内将测序读段比对到整个人类基因组。

全文搜索引擎：搜索引擎的倒排索引可以看作后缀数组思想的工程化变体。

数据压缩：Burrows-Wheeler 变换（BWT）将字符串重排使相同字符聚集，大幅提升压缩率，而 BWT 可以用后缀数组在 $O(n)$ 时间内计算。bzip2 就用了这个思路。

FM-Index：把索引压进文本的熵里#

后缀数组把索引空间压到每字符几个字节，但对整个基因组、整个 Web 语料，连这个也太贵——索引不该比文本本身大出好几倍。FM-Index（Ferragina & Manzini，2000 年，FOCS）给出的答案相当反直觉：不存后缀数组，存 Burrows-Wheeler 变换后的文本本身，查询照样能做。

机制建立在 BWT 的一个代数性质上：BWT 矩阵中第 $i$ 行的末字符，恰好是该行后缀的前一个字符；再配合"同一字符在首列与末列中出现次序一致"这一映射（LF-mapping），就可以从模式的末尾字符出发，逐字符向前收缩后缀数组中对应区间的上下界——这叫后向搜索（Backward Search）。每步只需两张表：各字符的累计计数表，和 BWT 串上的 rank 查询（"前 $k$ 个位置中字符 $c$ 出现几次"）。查询共 $O(|P|)$ 步，每步常数级。

空间上，BWT 串把相同字符聚集在一起，天然适合再压缩，整个索引可以做到接近文本本身的高阶熵。索引即压缩、压缩即索引——前文提到的 Bowtie、BWA 等基因组比对工具内部就是 FM-Index：整个人类基因组的索引可以装进一台普通工作站的内存，这是纯后缀数组做不到的。

后缀自动机：另一条路#

与后缀树/后缀数组并列的另一个重要结构是后缀自动机（Suffix Automaton, SAM）。SAM 是接受字符串 $S$ 的所有子串的最小确定性有限自动机（DFA），状态数和转移边数均为 $O(n)$，在线性时间内构建。

SAM 能高效解决的问题与后缀数组高度重叠（最长公共子串、子串统计、最长重复子串），但视具体问题而言，有时一个比另一个更简洁。在竞技编程中，SAM 因其简洁的在线构建算法而备受青睐。

后缀树 vs 后缀数组 vs 后缀自动机：

三者在理论上可以互相转换，实际选择取决于问题性质和实现偏好。

代价与争议#

实现复杂：Ukkonen 算法和 SA-IS 都是出了名的难以正确实现，调试困难。实际工程中往往使用经过充分测试的库（如 libdivsufsort）。

内存 vs 速度：后缀树功能更强大（支持更多查询类型），但内存是后缀数组的 5–10 倍。大多数实际应用选择后缀数组。

压缩后缀数组：对超大文本（如整个 web 的索引），连后缀数组本身也太大，需要压缩后缀数组（Compressed Suffix Array）和 FM-Index，将空间降至接近文本本身的熵。

跨域连接#

• 组合数学：整个结构立在一个计数事实上：一个串有平方级数量的子串，却只有线性数量的后缀，而每个子串都是某个后缀的前缀。于是索引所有子串这件看似要平方空间的事，只需要线性的对象。这是"换一个表示就改变量级"的干净例子。
• 字符串匹配：两者的分工是一次性预处理与反复查询的分工。单次扫描的算法对一次查询已是最优，但每次查询都要碰一遍文本；索引把代价提前付掉，此后每次查询只与模式长度有关。选哪种取决于查询次数，而不是哪个算法更聪明。
• 信息论：让相同字符聚集从而提升压缩率的那个重排，恰好也是让后缀有序的那个重排。压缩能力与索引能力因此同源：可压缩性来自重复，而重复正是后缀之间共享长前缀的表现。压缩后缀数组能把空间压到接近文本本身的信息量，正是这一同源性的直接兑现。
• 基因测序：同一个基因组要被查询成千上万次，这正是索引结构存在的理由。它让"这段序列出现在哪里"的代价与基因组规模脱钩，把测序分析从一次次全局扫描变成一次建索引加大量廉价查询。
• 语料库语言学：搭配与重复串的统计通常先固定一个长度再计数。有了后缀索引，任意长度的重复串及其频次可以被一次性穷举，不必事先决定看多长——研究者由此不再受限于预设的窗口，而是让数据自己给出哪些长度上存在结构。

参考文献#

• Weiner, P. Linear Pattern Matching Algorithms. 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), pp. 1–11. IEEE.
• Manber, U. & Myers, G. Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 22(5), 935–948 (1993).
• Ukkonen, E. On-Line Construction of Suffix Trees. Algorithmica 14(3), 249–260 (1995).
• Kasai, T. et al. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. CPM 2001, LNCS 2089, 181–192.
• Ferragina, P. & Manzini, G. Opportunistic Data Structures with Applications. FOCS 2000, pp. 390–398. IEEE.（FM-Index 原始论文）
• Kärkkäinen, J. & Sanders, P. Simple Linear Work Suffix Array Construction. ICALP 2003. LNCS 2719, 943–955.

延伸阅读#

• Gusfield, D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.（后缀树/后缀数组的标准参考书，Ukkonen 算法的讲法最易读）
• Navarro, G. Compact Data Structures: A Practical Approach. Cambridge University Press, 2016.（压缩后缀数组与 FM-Index 的系统处理）