后缀树

1. Introduction

后缀树是一个压缩树，包含了给定（通常很长）文本字符串T的所有后缀，长度为n个字符（n可以达到几十万个字符的数量级）。


文本字符串T中每个后缀的位置以整数索引的形式记录在后缀树的叶子节点上，而叶子节点的路径标签（从根开始的边标签的连接）描述了后缀。


后缀树为许多重要的（长）字符串操作提供了特别快的实现。


这种数据结构与后缀数组数据结构非常相关。这两种数据结构通常一起研究。

1-1. 字符串T的后缀

后缀 i（或第 i 个后缀）是一个（通常很长的）文本字符串 T 的一个'特殊情况'的子字符串，它从字符串的第 i 个字符开始，一直到它的最后一个字符。


例如，如果 T = "STEVEN$"，那么 T 的后缀 0 是 "STEVEN$"（0-based indexing），后缀 2 是 "EVEN$"，后缀 4 是 "EN$"，等等。

2. 后缀树可视化

字符串T的后缀树的可视化基本上是一个根树，其中从根到每个叶子的路径标签（边缘标签的连接）描述了T的一个后缀。每个叶子顶点都是一个后缀，叶子顶点内部写着的整数值（我们通过终止符号$确保这个属性）是后缀编号。


一个内部顶点将分支到多个子顶点，因此从根到叶子通过这个内部顶点有多个后缀。内部顶点的路径标签是那些后缀中的公共前缀。

2-1. 示例，T = "GATAGACA$"

上面的后缀树是从字符串 T = "GATAGACA$" 构建的，它有以下9个后缀：

i后缀
0GATAGACA$
1ATAGACA$
2TAGACA$
3AGACA$
4GACA$
5ACA$
6CA$
7A$
8$

现在验证后缀7/6/2的路径标签分别是"A$"/"CA$"/"TAGACA$"（还有6个其他的后缀）。带有路径标签"A"/"GA"的内部顶点分别分支到4个后缀 {7, 5, 3, 1}/2个后缀 {4, 0}（我们忽略了分支到所有9个后缀的平凡内部顶点 = 根顶点）。

2-2. 终止符号 $

为了确保输入字符串 T 的每个后缀都以叶子顶点结束，我们强制字符串 T 以一个特殊的终止符号 '$' 结束，这个符号在原始字符串 T 中没有使用，并且其ASCII值低于 T 中允许的最低字符（在这个可视化中是字符 'A'）。这样，边标签 '$' 总是出现在这个后缀树可视化的根顶点的最左边的边。


对于上面的后缀树示例（对于 T = "GATAGACA$"），如果我们没有终止符号 '$'，注意到后缀 7 "A"（没有 '$'）并没有在叶子顶点结束，这可能会使后续的一些操作变得复杂。

2-3. 后缀树有 O(n) 个顶点

由于我们确保所有后缀都以叶子顶点结束，因此在后缀树中最多有n个叶子/后缀。所有内部顶点（包括根顶点，如果它是内部顶点）总是分支，因此最多可以有n-1个这样的顶点，如右侧的极端测试案例所示。


因此，后缀树中顶点的最大数量 = n（叶子）+ (n-1) 内部顶点 = 2n-1 = O(n) 顶点。由于后缀树是一棵树，后缀树中边的最大数量也是 (2n-1)-1 = O(n) 边。

2-4. 更短的后缀树

当字符串T中的所有字符都是不同的（例如，T = "ABCDE$")，我们可以得到以下非常短的后缀树，其中恰好有n+1个顶点（+1是由于根顶点）。

3. 可执行的操作

此可视化中可用的所有后缀树操作如下：

  1. 构建后缀树（即时/详细信息省略） —— 从字符串T即时构建后缀树。
  2. 搜索 —— 在后缀树中找到路径标签包含（通常较短的）模式/搜索字符串P的（通常较长的）字符串T的顶点。
  3. 最长重复子串（LRS） —— 找到最深（路径标签最长）的内部顶点（因为该顶点在T的两个（或更多）后缀之间共享公共前缀）。
  4. 最长公共子串（LCS） —— 找到包含来自两个不同原始字符串的后缀的最深的内部顶点。

后缀树还有一些其他可能的操作，这些操作未包含在此可视化中。

3-1. 构建后缀树（即时）

在这个可视化中，我们只展示完全构建的后缀树而不描述 O(n) 后缀树构建算法的细节 —— 它有点复杂。感兴趣的读者可以浏览这个。


我们限制输入只接受25个（由于可用的绘图空间，不能太长 —— 但在后缀树的实际应用中，n可以是十万到百万个字符）ASCII（或甚至Unicode）字符。如果你没有在输入字符串的末尾写一个终止符 '$'，我们会自动这样做。如果你在输入字符串的中间放一个 '$'，它们将被忽略。如果你输入一个空的输入字符串，我们将使用默认的 "GATAGACA$"。


为了方便，我们提供了一些通常在后缀树/数组课程中找到的经典测试用例输入字符串，但为了展示这个可视化工具的强大，我们鼓励你输入任何你选择的25个字符的字符串（以字符 '$' 结尾）。你可以使用中文字符（在Unicode中），例如，"四是四十是十十四不是四十四十不是十四$"。

3-2. 搜索

假设已经构建了一个（通常较长的）字符串T（长度为n）的后缀树，我们想要找到模式/搜索字符串P（长度为m）的所有出现位置。


为了做到这一点，我们在T的后缀树中寻找顶点x，该顶点的路径标签（从根到x的边标签的连接）的前缀是P。一旦我们找到这个顶点x，在x为根的子树中的所有叶子都是出现的位置。


时间复杂度：O(m+k)，其中k是出现的总次数。


例如，在上面的T = "GATAGACA$"的后缀树中，尝试以下情况：

  1. P与顶点x的路径标签完全匹配：
    Search("A")，出现次数 = {7, 5, 3, 1} 或 Search("GA")，出现次数 = {4, 0}
  2. P与顶点x的路径标签部分匹配：
    Search("T")，出现次数 = {2} 或 Search("GAT")，出现次数 = {0}
  3. P在T中未找到：
    Search("WALDO")，出现次数 = {NIL}

3-3. 最长重复子串 (LRS)

假设已经构建了一个（通常较长的）字符串T（长度为n）的后缀树，我们可以通过简单地找到T的后缀树中最深的（路径标签最长的）内部顶点来找到T中的最长重复子字符串（LRS）。


这是因为T的后缀树的每个内部顶点至少分支到两个（或更多）后缀，即，路径标签（这些后缀的公共前缀）是重复的。


最深的（路径标签最长的）内部顶点就是所需的答案，可以通过简单的树遍历在O(n)中找到。


言归正传，试试 LRS("GATAGACA$")。我们有 LRS = "GA"。


有可能T包含多个 LRS，例如，试试 LRS("BANANABAN$")。
我们有 LRS = "ANA"（实际上重叠）或 "BAN"（无重叠）。

3-4. 最长公共子串 (LCS)

这次，我们需要两个以符号 '$'/'#' 结束的输入字符串 T1 和 T2。然后我们在 O(n) 时间内创建这两个字符串 T1+T2 的广义后缀树，其中 n = n1+n2（两个字符串长度的总和）。我们可以通过简单地找到 T1+T2 的广义后缀树中最深的且有效的内部顶点，来找到这两个字符串 T1 和 T2 的最长公共子串（LCS）。


要成为一个有效的内部顶点并被考虑为 LCS 候选者，一个内部顶点必须代表来自两个字符串的后缀，即，在 T1 和 T2 中都找到的公共子串。


然后，由于 T 的后缀树的内部顶点至少分支到两个（或更多）后缀，即，路径标签（这些后缀的公共前缀）是重复的。如果那个内部顶点也是一个有效的内部顶点，那么它就是一个重复的公共子串。


有效且最深（路径标签最长）的内部顶点就是我们需要的答案，可以通过简单的树遍历在 O(n) 时间内找到。


言归正传，尝试在字符串 T1 = "GATAGACA$" 和 T2 = "CATA#" 的广义后缀树上点击 LCS(T1,T2)（注意 UI 将切换到广义后缀树版本）。我们得到的 LCS = "ATA"。

4. 额外

我们可以使用后缀树做一些其他事情，如"找到最长的不重叠重复子字符串"，"找到≥ 2个字符串的最长公共子字符串"等，但我们将留到以后再讨论。


我们将继续讨论这个特定于字符串的数据结构，转向更通用的后缀数组数据结构。