乌科宁后缀树算法的通俗易懂解释

Question

乌科宁后缀树算法的通俗易懂解释

stringalgorithmdata-structureslanguage-agnosticsuffix-tree

1224

我感觉有点困难。我已经花了好几天时间来完全理解后缀树的构建，但由于我没有数学背景，许多解释对我来说是模糊的，因为它们开始过度使用数学符号。我找到的最好的解释是Fast String Searching With Suffix Trees，但他略过了一些要点，算法的某些方面仍然不清楚。

在Stack Overflow上提供这个算法的逐步解释对我和其他许多人都会非常有价值。

供参考，这是Ukkonen关于该算法的论文: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf 到目前为止，我的基本理解是：

我需要遍历给定字符串T的每个前缀P
我需要遍历前缀P中的每个后缀S并将其添加到树中
要将后缀S添加到树中，我需要遍历S中的每个字符，迭代包括沿着以字符C开头的现有分支向下行走，并在到达后缀中的不同字符时可能将边拆分为子节点，或者如果没有匹配的边可供行走。当找不到用于C的匹配边时，将为C创建一个新的叶边。

基本算法似乎是O(n²)，正如大多数解释所指出的那样，因为我们需要遍历所有前缀，然后我们需要遍历每个前缀的每个后缀。Ukkonen算法显然是独特的，因为他使用了后缀指针技术，尽管我认为我正在困扰理解它。

我还不理解：

“活动点”是何时以及如何被分配、使用和更改的
算法的规范化方面正在发生什么
我看到的实现为什么需要“修复”它们正在使用的边界变量

这是完成的C#源代码。它不仅能够正确运行，还支持自动规范化，并呈现出更美观的文本输出图形。源代码和示例输出位于：

https://gist.github.com/2373868

更新 2017-11-04

多年后，我发现了后缀树的新用途，并在JavaScript中实现了算法。如下是代码片段，应该没有bug。将其放入js文件中，从同一位置npm install chalk，然后使用node.js运行以查看一些彩色输出。在相同的Gist中有一个简化版本，没有任何调试代码。

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

- Nathan Ridley

4

你看过 Dan Gusfield 的书中的描述了吗？我发现那个对我很有帮助。 - jogojapan

6

要点未指明许可证 - 我能否在署名的情况下修改你的代码并以MIT许可证重新发布？ - Yuri Astrakhan

3

没问题，尽管使用。可以视为公共领域。正如本页另一个答案所提到的，还有一个需要修复的错误。 - Nathan Ridley

1

也许这个实现会帮助其他人，前往https://code.google.com/p/text-indexing/。 - cos

6

“考虑它为公有领域”可能会让人觉得这不是一个很有用的回答。原因是，你实际上无法将作品放入公有领域。因此，“考虑它...”的评论强调了许可证不清晰的事实，并给读者理由怀疑你是否真正清楚该作品的状态。如果你希望别人能够使用你的代码，请为其指定一个许可证，选择任何你喜欢的许可证（但是，除非你是一名律师，否则请选择预先存在的许可证！）。 - James Youngman

显示剩余6条评论

7个回答

138

我尝试按照 jogojapan 的答案给出的方法实现后缀树，但由于规则使用的措辞不当，在某些情况下它并没有起作用。此外，我已经提到过，没有人能够使用这种方法完全正确地实现后缀树。下面我将写一个“概述”jogojapan的答案，并对规则进行一些修改。我还将描述在我们忘记创建important后缀链接时的情况。

使用的其他变量

活动点 - 一个三元组（active_node; active_edge; active_length），显示我们必须从哪里开始插入新的后缀。
剩余 - 显示我们必须显式添加多少个后缀。例如，如果我们的单词是“abcaabca”，并且remainder = 3，则意味着我们必须处理最后3个后缀：bca、ca和a。

让我们使用内部节点的概念 - 所有节点（除了根节点和叶子节点）都是内部节点。

观察1

当发现要插入的最终后缀已经存在于树中时，树本身不会改变（我们只更新活动点和余数）。

Observation 2

如果在某一时刻，active_length大于或等于当前边的长度（edge_length），则将我们的active point向下移动，直到edge_length严格大于active_length为止。

现在，让我们重新定义规则：

规则1

如果在从活动节点（根节点）插入后，活动长度大于0，则：

活动节点不会改变

活动长度将被减少

活动边缘会向右移动（移到我们必须插入下一个后缀的第一个字符）

规则2：如果我们创建一个新的内部节点或从内部节点中插入，而这不是当前步骤中的第一个这样的内部节点，则我们通过后缀链接将前一个这样的节点与此节点连接起来。
这里定义的规则2与 jogojapan'不同，因为我们不仅考虑新创建的内部节点，还考虑从其中进行插入的内部节点。
规则3：在从不是根节点的活动节点插入后，我们必须遵循后缀链接并将活动节点设置为其指向的节点。如果没有后缀链接，请将活动节点设置为根节点。无论哪种方式，活动边缘和活动长度保持不变。
在此定义的规则3中，我们也考虑了叶子节点的插入（而不仅仅是分裂节点）。
最后，观察3：
当我们要添加到树中的符号已经在边缘时，根据 观察1 ，我们仅更新活动点和剩余部分，而不更改树。但是，如果有一个标记为需要后缀链接的内部节点，我们必须通过后缀链接将该节点与我们的当前活动节点连接起来。

让我们以一个后缀树的例子来说明，该后缀树由字符串cdddcdc生成，如果我们在这种情况下添加后缀链接和不添加后缀链接：

如果我们不通过后缀链接连接节点：

在添加最后一个字母c之前：

在添加最后一个字母c之后：

如果我们通过后缀链接连接节点：

在添加最后一个字母c之前：

在添加最后一个字母c之后：

看起来没有太大的区别：在第二种情况下，有两个额外的后缀链接。但是这些后缀链接是“正确”的，其中之一-从蓝色节点到红色节点-对于我们使用的“活动点”方法非常重要。问题在于，如果我们不在这里放置一个后缀链接，那么以后，当我们向树中添加一些新字母时，由于“规则3”，我们可能会忽略向树中添加一些节点，因为根据该规则，如果没有后缀链接，那么我们必须将“活动节点”设置为根。

当我们向树添加最后一个字母时，红色节点已经存在了，在我们从蓝色节点（标记为“c”的边）进行插入之前就已经存在了。因为有一个来自蓝色节点的插入，所以我们将其标记为“需要后缀链接”。然后，依靠“活动点”方法，将“活动节点”设置为红色节点。但是我们不会从红色节点插入，因为字母'c'已经在边上了。这是否意味着蓝色节点必须没有后缀链接？不，我们必须通过后缀链接将蓝色节点连接到红色节点。为什么它是正确的？因为“活动点”方法保证我们到达正确的位置，即我们必须处理较短后缀插入的下一个位置。

最后，这是我的后缀树实现：

Java
C++
希望这个“概述”结合jogojapan的详细答案能帮助某人实现自己的后缀树。

- makagonov

3

非常感谢你的努力，并给你加上一个赞。我相信你是正确的，尽管我现在没有时间考虑细节问题。稍后我会检查并可能修改我的答案。 - jogojapan

4

对于规则3，一个聪明的方法是将根节点的后缀链接设置为其本身，并且（默认情况下）将每个节点的后缀链接设置为根节点。这样我们就可以避免条件判断，只需要按照后缀链接进行跟随即可。 - sqd

很好的解释！只有一件事我想补充。我仍在努力理解，但据我所知，这个解释跳过了一个边缘情况：“abca”。在该情况下，我们需要将一个结束字符附加到字符串中，例如'$'。请查看http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm中的第5段。 - elif

你确定吗？你说“由于规则3，我们可能会省略向树中添加一些节点”，但是你的示例并没有展示出来。即使没有你提供的新链接，我仍然可以得到正确的树，只是多了一步。你能想出另一个例子来展示吗？还有@jogojapan？ - Tony

1

"aabaacaad" 是其中一个案例，它表明添加额外的后缀链接可以减少三元组更新的次数。jogojapan 的帖子最后两段的结论是错误的。如果我们不添加该帖子提到的后缀链接，则平均时间复杂度应为 O(nlong(n)) 或更高。因为需要额外的时间来遍历树以找到正确的“active_node”。 - IvanaGyro

显示剩余5条评论

21

抱歉如果我的回答看起来有些冗余，但我最近实现了Ukkonen算法，并发现自己在这个算法上挣扎了几天；我不得不阅读多篇关于该算法的论文，以理解一些核心方面的原因和方法。

我发现之前回答中的“规则”方法对于理解底层原因没有帮助，因此我在下面的所有内容中仅关注实用性。如果你像我一样难以理解其他解释，请参考我的补充说明。

我在这里发布了我的C#实现: https://github.com/baratgabor/SuffixTree 请注意，我不是这个主题的专家，所以下面的部分可能包含不准确或更糟糕的错误。如果你遇到任何问题，请随意编辑。

先决条件

下面的解释假设你已经熟悉后缀树的内容和用法，以及Ukkonen算法的特点，例如如何逐个字符从开始到结束扩展后缀树。基本上，我假设你已经阅读了其他一些解释。

（然而，我确实不得不添加一些基本的叙述来流畅地讲述，所以开头可能会感觉冗余。）

最有趣的部分是关于使用后缀链接和从根重新扫描之间的区别的解释。这就是我在实现中遇到了很多错误和头痛的原因。

开放式叶节点及其限制

我相信你已经知道最基本的“技巧”是意识到我们可以将后缀的结尾“开放”，即引用字符串的当前长度而不是设置结尾为静态值。这样，当我们添加额外的字符时，这些字符将隐式地添加到所有后缀标签中，而无需访问和更新所有标签。

但是，由于明显的原因，后缀的开放结尾仅适用于表示字符串结尾的节点，即树结构中的叶节点。我们在树上执行的分支操作（添加新的分支节点和叶节点）不会自动传播到需要它们的所有位置。

很可能是基础知识，并且不需要提及，重复子串不会在树中明确出现，因为树已经包含了这些子串，因为它们是重复的。然而，当重复的子串以遇到非重复字符结束时，我们需要在该点创建一个分支，以表示从该点开始的分歧。

例如，在字符串'ABCXABCY'的情况下（见下文），需要向三个不同的后缀ABC、BC和C添加到X和Y的分支；否则，它将不是有效的后缀树，我们将无法通过从根向下匹配字符来找到字符串的所有子串。

再次强调 - 我们在树上对后缀执行的任何操作都需要反映在其连续的后缀中（例如ABC>BC>C），否则它们就会停止成为有效的后缀。

但即使我们接受必须手动更新的事实，我们如何知道需要更新多少个后缀？因为当我们添加重复字符（以及后续的重复字符）时，我们还不知道何时/在哪里需要将后缀拆分为两个分支。只有在遇到第一个非重复字符时，即（而不是已存在于树中的）时，才确定需要拆分。

我们可以做的是匹配最长的重复字符串，并计算需要稍后更新其后缀的数量。这就是“remainder”的含义。

余数和重新扫描的概念

变量“remainder”告诉我们隐式添加了多少个重复字符，而没有分支；也就是说，我们需要访问多少个后缀才能重复分支操作，一旦找到无法匹配的第一个字符。从根节点开始，这本质上等于我们在树中有多少个“深度”。

因此，以字符串ABCXABCY为例，我们隐式匹配重复的ABC部分，每次增加remainder，结果为3。然后我们遇到非重复字符'Y'。在这里，我们将先前添加的ABCX拆分成ABC->X和ABC->Y。然后我们将remainder从3减少到2，因为我们已经处理了ABC分支。现在我们通过匹配最后2个字符- BC - 从根节点开始重复操作，直到达到需要拆分的点，并将BCX也拆分为BC->X和BC->Y。同样，我们将remainder减少到1，并重复操作，直到remainder为0。最后，我们还需要将当前字符（Y）本身添加到根中。

按照Ukkonen算法的方法，从根节点按顺序扫描后缀，直到需要执行操作的位置，这个操作就是所谓的'rescanning'，通常是算法的最耗时部分。想象一下，如果需要在许多节点（稍后我们将讨论这一点）之间“重新扫描”长子字符串，这可能会发生多达数千次。

作为解决方案，我们引入了所谓的“后缀链接”。

“后缀链接”基本上指向我们通常需要“重新扫描”的位置，因此，我们可以简单地跳转到链接的位置，进行操作，然后跳转到下一个链接的位置并重复执行，直到没有更多的位置需要更新。

当然，一个重要的问题是如何添加这些链接。现有的答案是，在插入新的分支节点时添加链接，利用这样一个事实：在树的每个扩展中，分支节点自然而然地按照我们需要链接它们的顺序依次创建。不过，我们需要从最后创建的分支节点（即最长的后缀）链接到先前创建的节点，因此我们需要缓存我们创建的最后一个节点，将其链接到下一个创建的节点，并缓存新创建的节点。

其中一个结果是，我们实际上经常没有可供跟随的后缀链接，因为给定的分支节点刚刚被创建。在这些情况下，我们仍然必须返回到根节点进行“重新扫描”。这就是为什么在插入后，您被要求使用后缀链接或跳转到根节点的原因。

（或者，如果您在节点中存储父指针，您可以尝试跟随父节点，检查它们是否有链接，并使用它们。我发现这很少被提到，但“后缀链接的使用并不是一成不变的。”有多种可能的方法，如果您理解了基本机制，可以实现最适合您需求的方法。）

“活动点”的概念

到目前为止，我们已经讨论了多种高效构建树的工具，并模糊地提到了遍历多个边和节点的方法，但还没有探讨相应的后果和复杂性。

先前解释的“余数”概念有助于跟踪我们在树中的位置，但我们必须意识到它并没有存储足够的信息。

首先，我们总是驻留在节点的特定边上，因此需要存储边信息。我们称之为“活动边”。

其次，即使添加了边信息，我们仍然无法识别一个在树中更远的位置，而且不直接连接到根节点。因此我们还需要存储节点。我们称之为“活动节点”。

最后，我们可以注意到，“余数”无法识别与根不直接连接的边上的位置，因为“余数”是整个路径的长度；我们可能不想费心记住并减去以前边的长度。因此，我们需要一种表示方式，它实质上是“当前边上的余数”。这就是我们所说的“活动长度”。

这导致了我们所谓的“活动点”——一个包含所有关于我们在树中位置的信息的三个变量的组合：

活动点 =（活动节点，活动边，活动长度）

你可以观察下面的图片，了解ABCABD的匹配路线由边缘AB上的2个字符（来自root），以及边缘CABDABCABD上的4个字符（来自节点4）组成，结果是剩余6个字符的'remainder'。因此，我们当前的位置可以被识别为Active Node 4、Active Edge C、Active Length 4。

另一个“活动点”的重要作用是为我们的算法提供抽象层，这意味着我们的算法的某些部分可以在“活动点”上工作，而不管该活动点是否在根或其他任何地方。这使得我们的算法易于以干净和直接的方式实现后缀链接的使用。

重新扫描与使用后缀链接的差异

现在，棘手的部分是处理后缀链接情况与重新扫描情况的差异，这在我的经验中可能会导致大量错误和头痛，并且在大多数来源中解释不清。

考虑以下字符串“AAAABAAAABAAC”的示例：

你可以看到上面的例子中，数字7对应于从根节点开始所有字符总数的余数，而数字4对应于从活动边缘匹配的字符总数。

现在，在活动点执行分支操作后，我们的活动节点可能包含或不包含后缀链接。

如果存在后缀链接：我们只需要处理“活动长度”部分。余数是无关紧要的，因为通过后缀链接跳转到的节点已经隐式地编码了正确的“余数”，仅仅因为它在树中。

如果不存在后缀链接：我们需要从零/根节点重新扫描，这意味着从开头处理整个后缀。为此，我们必须使用整个“余数”作为重新扫描的基础。

示例比较处理是否具有后缀链接

考虑以上例子的下一步会发生什么。让我们比较如何使用和不使用后缀链接来实现相同的结果-即移动到下一个要处理的后缀。

请注意，如果我们使用后缀链接，我们会自动“到达正确位置”。但由于“活动长度”可能与新位置不兼容，这通常并不严格正确。

在上面的情况下，由于“活动长度”为4，我们正在使用后缀“ABAA”，从链接的节点4开始。但是，在找到与后缀的第一个字符（'A'）对应的边之后，我们注意到我们的“活动长度”超出了3个字符。因此，我们跳过整个边缘，到达下一个节点，并通过跳跃消耗的字符减少“活动长度”。

然后，在我们找到下一个边缘'B'，对应于缩短的后缀'BAA'后，我们最终注意到边缘长度大于剩余的“活动长度”3，这意味着我们找到了正确的位置。

请注意，尽管对我来说似乎这个操作通常不被称为“重新扫描”，但它似乎是重新扫描的直接等价物，只是长度更短，起始点不是根。

使用“重新扫描”

请注意，如果我们使用传统的“重新扫描”操作（这里假装我们没有后缀链接），我们将从树的顶部，即根开始，然后再次向下工作，直到到达正确的位置，沿着当前后缀的整个长度进行跟随。

这个后缀的长度是我们之前讨论过的“剩余部分”。我们必须消耗这个剩余部分的全部内容，直到它变为零。这可能会（并经常会）包括通过多个节点跳跃，在每个跳跃中减少我们穿过的边的长度。然后最终，我们到达了一条比我们剩余的“剩余部分”更长的边；在这里，我们将活动边设置为给定的边，将“活动长度”设置为剩余的“剩余部分”，然后完成。

但是，请注意实际的“剩余部分”变量需要被保留，在每个节点插入之后才能递减。因此，我上面描述的假设使用一个单独的变量初始化为“剩余”。

关于后缀链接和重新扫描的注释

1）请注意，两种方法都会导致相同的结果。然而，在大多数情况下，后缀链接跳跃要快得多；这就是后缀链接背后的整个理念。

2）实际的算法实现不需要有所不同。正如我上面提到的，在使用后缀链接的情况下，即使是“活动长度”通常也与链接位置不兼容，因为该树的该分支可能包含其他分支。因此，您只需使用“活动长度”而不是“剩余部分”，并执行相同的重新扫描逻辑，直到找到一条较短的边为止。

3) 关于性能的一个重要说明是，在重新扫描期间没有必要检查每个字符。由于有效后缀树的构建方式，我们可以安全地假设字符匹配。因此，您主要是计算长度，并且仅在跳转到新边缘时需要进行字符等价性检查，因为边缘是通过它们的第一个字符（在给定节点的上下文中始终唯一）来标识的。这意味着“重新扫描”逻辑与完整的字符串匹配逻辑（即在树中搜索子字符串）不同。

4) 这里描述的原始后缀链接只是可能的方法之一。例如NJ Larsson et al.将此方法称为面向节点的自顶向下，并将其与面向节点的自底向上和两种面向边缘进行比较。不同的方法具有不同的典型和最坏情况性能、要求、限制等，但通常似乎面向边缘的方法是对原始方法的总体改进。

- Leaky

10

感谢@jogojapan提供的详细教程，我已经在Python中实现了该算法。

@jogojapan提到的几个小问题竟然比我预想的更加复杂，并且需要非常仔细地处理。花费了我数天时间才让我的实现足够稳健（我想）。以下列出了问题和解决方案：

剩余>0事实证明，在展开步骤中，这种情况也可能发生，而不仅仅是整个算法的结尾处。当发生这种情况时，我们可以保持余数、活动节点、活动边缘和活动长度不变，结束当前的展开步骤，并通过保持折叠或展开来开始另一个步骤，具体取决于原始字符串中的下一个字符是否在当前路径上。
跨越节点：当我们遵循后缀链接、更新活动点，然后发现其活动长度组件与新活动节点不匹配时。我们必须向前移动到正确的位置进行拆分或插入叶子。这个过程可能并不那么直接，因为在移动过程中，活动长度和活动边缘一直在变化，当您必须移回根节点时，由于这些移动，活动边缘和活动长度可能会出错。我们需要额外的变量来保持那个信息。

其他两个问题已经被@managonov指出了。

划分可能会恶化：在尝试划分一个边时，有时会发现划分操作就在一个节点上。这种情况下，我们只需要向该节点添加一个新的叶子，并将其视为标准的边划分操作，这意味着如果有任何后缀链接，应相应地维护它们。
隐藏的后缀链接：还有另一种特殊情况是由于问题1和问题2而引起的。有时我们需要跨越多个节点才能到达划分点，如果通过比较剩余字符串和路径标签进行移动，我们可能会超过划分点。在这种情况下，如果应该有任何后缀链接，则后缀链接将无意中被忽略。可以通过记住正确的位置来避免这种情况。如果划分节点已经存在，甚至在展开步骤中出现问题1，则应维护后缀链接。

最后，我的Python实现如下：

Python

提示： 它包括上面代码中的一个简单的树打印函数，这在调试时非常重要。它为我节省了很多时间，并方便了定位特殊情况。

- mutux

10

@jogojapan，你提供了很棒的解释和可视化。但正如@makagonov所提到的，缺少一些关于设置后缀链接的规则。当你在http://brenden.github.io/ukkonen-animation/中逐步查看单词 'aabaaabb' 时，这种情况表现得非常明显。当你从第10步到第11步时，节点5到节点2没有后缀链接，但活动点突然移动到那里。

@makagonov，由于我生活在Java世界中，我也尝试着跟随你的实现来掌握ST构建工作流程，但由于以下原因，对我来说非常困难：

将边缘与节点组合
使用索引指针而不是引用
打破语句；
继续语句；

因此，我最终采用了Java的这种实现方式，希望能以更清晰的方式反映所有步骤，并减少其他Java开发人员的学习时间：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

- Kamil

6

我的直觉是：

在主循环的k次迭代后，您构建了一个包含所有以前k个字符开头的完整字符串后缀的后缀树。

一开始，这意味着后缀树包含一个表示整个字符串的根节点（这是唯一以0开头的后缀）。

在len(string)次迭代后，您将拥有一个包含所有后缀的后缀树。

在循环过程中，关键是活动点。我猜这代表了后缀树中对应于字符串前k个字符的真后缀的最深点。（我认为真后缀指的是后缀不能是整个字符串。）

例如，假设您已经看到了字符“abcabc”。活动点将表示与后缀“abc”相对应的树中的点。

活动点由（origin，first，last）表示。这意味着您当前正在树中的该点，该点通过从节点起始处开始并输入string[first：last]中的字符来获取。

当您添加新字符时，查看活动点是否仍在现有树中。如果是，则完成。否则，您需要在活动点处向后缀树添加一个新节点，回退到下一个最短匹配，并再次检查。

注意1：后缀指针为每个节点提供了到下一个最短匹配的链接。

注意2：当您添加新节点并回退时，为新节点添加新的后缀指针。此后缀指针的目标将是缩短后的活动点处的节点。该节点要么已经存在，要么在此回退循环的下一次迭代中创建。

注意3：规范化部分仅仅为了节省检查活动点的时间。例如，假设您始终使用origin = 0，并更改first和last。要检查活动点，每次都必须沿着所有中间节点遵循后缀树。通过记录距离最后一个节点的距离来缓存沿此路径的结果是有意义的。

您能否举个代码示例来说明“固定”边界变量的含义？

健康警告：我也发现这个算法特别难以理解，因此请注意这种直觉可能在所有重要细节上都不正确...

- Peter de Rivaz

其中一篇学术论文将“proper”定义为意味着一个字符串的“proper suffix”不包含它的第一个字符。有时你会称整个子串为“suffix”，但在定义算法时，“string”、“substring”和“suffix”这些术语被随意使用，有时你需要非常清楚地说明你所说的“suffix”的含义，因此“proper suffix”这个术语排除了将整个东西称为后缀。因此，一个字符串的后缀子串可以是任何合法的子串，并且可以具有不同于相同后缀的proper suffix。因为逻辑如此。 - Blair Houghton

3

您好，我尝试在Ruby中实现了上面解释的实现，请查看。看起来它运行良好。

在实现中唯一的区别是，我尝试使用边缘对象而不仅仅是使用符号。

它也可以在https://gist.github.com/suchitpuri/9304856找到。

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

- Suchit Puri

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jogojapan · Accepted Answer

以下是尝试描述Ukkonen算法的内容，首先展示了在字符串简单（即不包含任何重复字符）时它的工作原理，然后扩展到完整算法。

首先，需要说明几点：

1. 我们正在构建的基本上像搜索trie。因此有一个根节点，从中出发的边通向新节点，以及从那些节点出发的更多边等等。

2. 但是：与搜索trie不同，边标签不是单个字符。相反，每个边都使用一对整数[from，to]进行标记。这些是指针指向文本。从这个意义上讲，每个边都携带任意长度的字符串标签，但只占用O(1)空间（两个指针）。

基本原则：

我想先演示如何创建一个后缀树，它是一个特别简单的字符串，没有重复的字符。

abc

这个算法从左到右逐步执行。对于字符串中的每个字符，都有一个步骤。每个步骤可能涉及多个操作，但我们将看到（请参见最后的观察结果），总操作数为O(n)。

所以，我们从左边开始，首先只插入单个字符a，通过从根节点（在左侧）到叶子节点创建一条边，并将其标记为[0，#]，表示该边代表以位置0开始并以当前结尾结束的子字符串。我使用符号#表示当前结尾，它位于位置1（紧接着a）的右侧。

因此，我们有了一个初始树，看起来像这样：

它的意思是这样的：

现在我们进入第二个位置（紧接着b后面）。我们每一步的目标是插入到当前位置为止的所有后缀。我们通过以下方式实现：

将现有的a边扩展为ab
插入一个新的b边

在我们的表示中，它看起来像这样：

enter image description here

它的意思是：

我们观察到两件事情：

ab的边缘表示与初始树中的相同：[0,#]。由于我们将当前位置#从1更新为2，因此其含义已自动更改。
每个边缘消耗O(1)的空间，因为它只包含两个指向文本的指针，无论它代表多少个字符。

接下来，我们再次增加位置，并通过将c附加到每个现有边缘并为新后缀c插入一个新边缘来更新树。

在我们的表示中，这看起来像：

它的意思是：

我们观察到：

每一步后，树是正确的后缀树，直到当前位置
步骤数与文本中字符数相同
每个步骤中的工作量为O(1)，因为通过递增#自动更新所有现有边，并且可以在O(1)时间内插入最后一个字符的新边。因此，对于长度为n的字符串，仅需要O(n)的时间。

第一个扩展：简单重复

当然，这只适用于我们的字符串不包含任何重复的情况。现在我们看一个更加真实的字符串：

abcabxabcd

开始于先前示例中的abc，然后重复ab并跟随x，然后重复abc并跟随d。 步骤1到3：在前面3个步骤之后，我们得到了先前示例中的树形结构。

步骤4：我们将#移动到第4个位置。这将隐式更新所有现有的边缘为此内容：

我们需要在根节点插入当前步骤的最终后缀a。

在这之前，除了#，我们还引入了另外两个变量，虽然它们一直存在但我们还没有使用过：

活动点，是一个三元组(active_node, active_edge, active_length)
remainder，是一个整数，表示我们需要插入多少个新的后缀

这两个变量的确切含义很快就会变得清晰，但现在让我们暂且说：

在简单的abc示例中，活动点始终为(root,'\0x',0)，即active_node为根节点，active_edge指定为空字符'\0x'，active_length为零。这样做的效果是，在每一步中插入的一个新边作为全新创建的边插入到根节点。我们很快就会看到为什么需要三元组来表示这个信息。
remainder总是在每个步骤开始时设置为1。这意味着我们必须主动插入的后缀数量是1（始终只有最后一个字符）。

现在这将会改变。当我们在根节点插入当前的最后一个字符a时，我们注意到已经有一条以a开头的出边，具体来说是：abca。在这种情况下，我们要做以下操作：

我们不会在根节点插入一个新的边[4，＃]。相反，我们只是注意到后缀a已经存在于我们的树中。它以较长的边的中间结束，但我们并不介意。我们只是让事情保持原样。
我们设置活动点为（root，'a'，1）。这意味着活动点现在位于以a开头的根节点的出边的中间，具体来说，在该边上的位置1之后。我们注意到该边仅由其第一个字符a指定。这足够了，因为只能有一个以任何特定字符开头的边（阅读整个描述后确认此内容是否正确）。
我们还增加了remainder，因此在下一步开始时它将为2。

Observation: 当发现需要插入的最终后缀已经存在于树中时，树本身不会发生任何变化（我们只更新活动点和remainder）。因此，当前位置之前的后缀树不再是一个准确的表示，但它包含所有后缀（因为最终后缀a被隐式包含在内）。因此，在这一步中除了更新变量（这些变量都是固定长度的，因此是O(1)），没有进行任何工作。

Step 5：我们将当前位置#更新为5。这会自动将树更新为以下内容：

由于remainder为2，因此我们需要在当前位置插入两个最终后缀：ab和b。这基本上是因为：

来自前一步骤的a后缀从未被正确插入。因此它保留了下来，并且由于我们前进了一步，现在它从a变成了ab。
我们需要插入新的最终边缘b。

实际上，这意味着我们转到活动点（它指向现在是abcab边缘上的a之后），并插入当前的最终字符b。但是：同样地，发现b也已经出现在同一条边上。

因此，我们不改变树。我们只需：

将活动点更新为(root,'a',2)（与之前相同的节点和边，但现在我们指向b后面）
将remainder增加到3，因为我们仍未正确插入上一步中的最终边缘，并且我们也不插入当前最终边缘。

明确一下：我们必须在当前步骤中插入ab和b，但是因为已经找到了ab，所以我们更新了活动点，甚至没有尝试插入b。为什么？因为如果树中有ab，它的每个后缀（包括b）也必须在树中。也许只是隐含地存在，但是由于我们迄今为止构建树的方式，它必须存在。

我们通过递增#进行第6步。树会自动更新为：

因为余数是3，我们需要插入abx，bx和x。活动点告诉我们ab的结束位置，所以我们只需要跳到那里并插入x。确实，x还没有在那里，所以我们要分裂abcabx边缘并插入一个内部节点：

"The edge representations are still pointers into the text, so splitting and inserting an internal node can be done in O(1) time."

"边缘表示仍然是指向文本的指针，因此在O(1)时间内可以拆分和插入内部节点。"

"So we have dealt with abx and decrement remainder to 2. Now we need to insert the next remaining suffix, bx. But before we do that we need to update the active point. The rule for this, after splitting and inserting an edge, will be called Rule 1 below, and it applies whenever the active_node is root (we will learn rule 3 for other cases further below). Here is rule 1:"

"所以我们已经处理了abx并将remainder减少到2。现在我们需要插入下一个剩余的后缀bx。但在此之前，我们需要更新活动点。在拆分和插入边缘后，这个规则被称为下面的规则1，并且适用于active_node是root的情况（我们将在下面进一步学习其他情况的规则3）。以下是规则1："

"After an insertion from root, - active_node remains root - active_edge is set to the first character of the new suffix we need to insert, i.e. b - active_length is reduced by 1"

“从根插入后， - active_node仍然是root - active_edge设置为我们需要插入的新后缀的第一个字符，即b - active_length减少1”

因此，新的活动点三元组(root,'b',1)表示下一个插入操作必须在bcabx边缘进行，向后移动1个字符，即在b之后。我们可以在O(1)时间内确定插入点并检查x是否已经存在。如果存在，我们将结束当前步骤并保持一切不变。但是x不存在，因此我们通过分割边来插入它：

再次说明，这需要O(1)的时间，我们更新remainder为1，根据规则1将活动点更新为(root,'x',0)。

但是还有一件事情要做。我们将其称为规则2：

如果我们分割一个边并插入一个新节点，并且如果这不是在当前步骤中创建的第一个节点，则通过一个特殊指针——后缀链接连接先前插入的节点和新节点。稍后我们将看到它的用处。这里是我们得到的结果，后缀链接表示为虚线边:

我们仍然需要插入当前步骤的最终后缀x。由于活动节点的active_length组件已经降为0，因此最终插入是直接在根节点进行的。由于根节点没有以x开头的出边，因此我们需要插入一条新的边：

根据当前步骤，所有剩余的插入操作均已完成。

我们将通过设置#=7进入第7步，这自动将下一个字符a附加到所有叶子边缘，如常。然后，我们尝试将新的最终字符插入到活动点（根节点）中，并发现它已经存在。因此，我们在不添加任何内容的情况下结束当前步骤，并将活动点更新为(root，'a'，1)。

在第8步中，#=8，我们附加b，并像之前一样只更新活动点为(root, 'a', 2)并增加remainder而没有做其他事情，因为b已经存在。 然而，我们注意到（在O（1）时间内）活动点现在位于一条边的末端。我们通过重新设置为(node1，'\0x'，0)来反映这一点。在这里，我使用node1来引用ab边结束的内部节点。

然后，在第#=9步中，我们需要插入'c'，这将帮助我们理解最终的技巧：

第二个扩展：使用后缀链接

像往常一样，#更新自动将c附加到叶边，并且我们转到活动点以查看是否可以插入'c'。结果发现该边已经存在'c'，因此我们将活动点设置为(node1,'c',1)，增加remainder并且什么也不做。

现在，在第#=10步中，remainder是4，因此我们首先需要通过在活动点插入d来插入abcd（从3步之前剩下的）。

尝试在活动点插入d会导致边界分裂，时间复杂度为O(1)：

上面标为红色的是发起分裂的active_node。这里是最终的规则Rule 3：

从一个不是根节点的active_node分裂一条边后，如果有后缀链接，则跟随该节点指向的后缀链接，并将active_node重置为该节点。如果没有后缀链接，则将active_node设置为根节点。 active_edge和active_length保持不变。

因此，现在的活动点是(node2,'c',1)，下面的node2被标记为红色:

自从插入abcd完成后，我们将remainder减少到3，并考虑当前步骤的下一个剩余后缀bcd。规则3已将活动点设置为刚好在右侧节点和边上，因此可以通过在活动点插入其最后一个字符d来插入bcd。

这样做会导致另一个边分裂，并且由于规则2的缘故，我们必须从先前插入的节点创建一个后缀链接到新节点：

我们观察到：后缀链接使我们能够重置活动点，以便我们可以在O(1)的时间内进行下一个剩余插入。查看上面的图表以确认标签为ab的节点确实链接到标签为b的节点（它的后缀），标签为abc的节点链接到bc。

当前步骤还未完成。remainder现在是2，我们需要按照规则3再次重置活动点。由于当前的活动节点（上面的红色）没有后缀链接，我们将其重置为根节点。现在活动点是(root,'c',1)。

因此，下一个插入发生在根节点的一个出边上，其标签以c开头：cabxabcd，在第一个字符之后，即在c之后。这导致另一个分裂。

由于这涉及到创建一个新的内部节点，我们遵循规则2并从先前创建的内部节点设置一个新的后缀链接：

我正在使用Graphviz Dot来绘制这些小图。新的后缀链接导致dot重新排列现有的边，因此请仔细检查以确认上面插入的唯一内容是一个新的后缀链接。

有了这个，remainder可以设置为1，由于active_node是根节点，我们使用规则1来更新活动点为(root,'d',0)。这意味着当前步骤的最终插入是在根节点插入一个单独的d：

这是最后一步，我们完成了。然而还有一些最终的观察：

在每一步中，我们将#向前移动1个位置。这会自动更新所有叶节点，时间复杂度为O(1)。
但它无法处理a) 任何先前步骤中剩余的后缀和b) 当前步骤的最后一个字符。
remainder告诉我们需要进行多少次额外的插入操作。这些插入操作一一对应于以当前位置#结尾的字符串的最终后缀。我们依次考虑并进行插入。 重要提示：每次插入都需要O(1)时间，因为活动点告诉我们确切的插入位置，我们只需要在活动点添加一个单一字符即可。为什么？因为其他字符是隐含的(否则活动点就不会在那里)。
在每次这样的插入之后，我们减少remainder并遵循后缀链接(如果有的话)。如果没有，我们就回到根节点(规则3)。如果我们已经在根节点，我们使用规则1修改活动点。在任何情况下，这只需要O(1)时间。
如果在这些插入之一期间，我们发现要插入的字符已经存在，即使remainder>0，我们也不会做任何事情并结束当前步骤。原因是剩余的所有插入操作都将是我们刚刚尝试进行的插入操作的后缀。因此，它们都是当前树中隐含的。remainder>0确保我们稍后处理剩余的后缀。
如果在算法结束时remainder>0怎么办？每当文本结尾是在某个地方出现过的子字符串时，就会出现这种情况。在这种情况下，我们必须在字符串末尾附加一个以前未出现过的额外字符。在文献中，通常使用美元符号$作为该符号。 为什么这很重要？ --> 如果以后我们使用完整的后缀树搜索后缀，我们必须只接受在叶节点结束的匹配。否则，我们将得到许多虚假的匹配，因为有许多在树中隐含的字符串不是主字符串的实际后缀。强制remainder在最后为0本质上是一种确保所有后缀都以叶节点结束的方式。 然而，如果我们想要使用树来搜索一般子字符串，而不仅仅是主字符串的后缀，则确实不需要进行此最终步骤，正如下面的OP评论所建议的那样。
那么整个算法的复杂度是多少？如果文本长度为n个字符，则显然有n个步骤(或者如果我们添加美元符号，则为n+1)。在每个步骤中，我们要么什么也不做(除了更新变量)，要么进行remainder次插入操作，每次操作都需要O(1)时间。由于remainder指示我们在以前的步骤中有多少次什

虚线表示整个树的其余部分。点状线是后缀链接。

现在让活动点为(红色，'d'，3)，因此它指向defg边上f后面的位置。现在假设我们进行了必要的更新，然后按照规则3跟随后缀链接更新活动点。新的活动点是(绿色，'d'，3)。但是，从绿色节点出发的d边是de，因此它只有2个字符。为了找到正确的活动点，我们显然需要沿着该边到达蓝色节点并重置为(蓝色，'f'，1)。

在一个特别糟糕的情况下，active_length 可能会很大，甚至和 remainder 一样大，而后者可能达到 n。并且，为了找到正确的活动点，我们可能需要跳过不止一个内部节点，而是最坏情况下多达 n 个节点。这是否意味着该算法具有隐藏的 O(n²) 复杂度，因为每一步中 remainder 通常是 O(n)，在遵循后缀链接后对活动节点进行的后续调整也可能是 O(n)？
不行。原因是如果我们必须调整活动点（例如从绿色到蓝色），那么我们会到达一个新的节点，该节点具有自己的后缀链接，并且active_length将减少。随着我们沿后缀链接链向下进行剩余插入操作，active_length只能减少，并且我们在途中可以进行的活动点调整次数不能大于任何给定时间的active_length。由于active_length永远不可能大于remainder，而且remainder在每一步都是O(n)，而且在整个过程中对remainder进行的所有增量的总和也是O(n)，因此活动点调整的数量也受到O(n)的限制。