后缀树

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. PT中未找到:
    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)

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


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


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


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


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

4. 额外

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


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