string - Ukkonen 的后缀树算法用简单的英语

Question

这个时候我觉得有点厚。我花了几天时间试图完全理解后缀树的构造，但由于我没有数学背景，许多解释都让我无法理解，因为他们开始过度使用数学符号。我找到的最接近好的解释是Fast String Searching With Suffix Trees，但他掩盖了各个点，算法的某些方面仍不清楚。

我敢肯定，在 Stack Overflow 上一步一步地解释这个算法对于除我之外的许多其他人来说都是无价的。

作为参考，这里是 Ukkonen 关于算法的论文：http ://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

到目前为止，我的基本理解：

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

正如大多数解释中所指出的，基本算法似乎是 O(n ^{2 )，因为我们需要遍历所有前缀，然后我们需要遍历每个前缀的每个后缀。}Ukkonen 的算法显然是独一无二的，因为他使用了后缀指针技术，尽管我认为这是我无法理解的。

我也很难理解：

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

这是完整的C#源代码。它不仅可以正常工作，而且支持自动规范化并呈现更好看的输出文本图。源代码和示例输出位于：

https://gist.github.com/2373868

2017-11-04 更新

多年后，我发现了后缀树的新用途，并在JavaScript中实现了该算法。要点如下。它应该没有错误。将其从同一位置转储到 js 文件中，npm install chalk然后使用 node.js 运行以查看一些彩色输出。在同一个 Gist 中有一个精简版本，没有任何调试代码。

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

score 2488 · Accepted Answer

下面尝试描述 Ukkonen 算法，首先显示字符串简单时（即不包含任何重复字符）时它的作用，然后将其扩展到完整算法。

首先，一些初步的陈述。

我们正在构建的基本上就像一个搜索尝试。所以有一个根节点，从它出来的边通向新节点，还有更多的边从这些节点出来，依此类推
但是：与搜索树不同，边缘标签不是单个字符。相反，每条边都使用一对整数进行标记 [from,to]。这些是指向文本的指针。从这个意义上说，每条边都带有一个任意长度的字符串标签，但只占用 O(1) 空间（两个指针）。

基本原则

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

abc

该算法按步骤工作，从左到右。字符串的每个字符都有一个步骤。每个步骤可能涉及不止一个单独的操作，但我们将看到（请参阅最后的观察结果）操作总数为 O(n)。

因此，我们从左边a开始，首先通过创建从根节点（左侧）到叶子的边，并将其标记为，从而仅插入单个字符 [0,#]，这意味着边表示从位置 0 开始并结束的子字符串在当前结束。我用这个符号#来表示当前的 end，它位于位置 1 （就在之后a）。

所以我们有一个初始树，它看起来像这样：

这意味着：

现在我们前进到位置 2（就在之后b）。我们每一步的目标 是将所有后缀插入到当前位置。我们这样做是通过

将现有的a-edge 扩展到ab
插入一个新的边缘b

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

在此处输入图像描述

它的意思是：

我们观察两件事：

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

接下来，我们再次增加位置并通过将 a 附加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。

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

第 5 步：我们将当前位置更新#为 5。这会自动将树更新为：

并且因为remainder是 2，所以我们需要插入当前位置的两个最终后缀：ab和b。这基本上是因为：

上一步的a后缀从未正确插入。所以它一直存在，并且由于我们前进了一步，它现在已经从a到ab。
我们需要插入新的最终边缘b。

在实践中，这意味着我们转到活动点（指向a现在abcab边缘的后面），并插入当前的最终字符b。但是：同样，事实证明它b也已经存在于同一边缘。

所以，再一次，我们不改变树。我们简单地：

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

需要明确的是：我们必须在当前步骤中插入ab和，但因为已经找到，我们更新了活动点，甚至没有尝试插入。为什么？因为 if在树中，它的每个后缀（包括）也必须在树中。也许只是隐含的，但它必须在那里，因为到目前为止我们构建树的方式。babbabb

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

因为remainder是 3，我们必须插入abx,bx和 x。活动点告诉我们在哪里ab结束，所以我们只需要跳转到那里并插入x. 确实，x还没有，所以我们分割abcabx边缘并插入一个内部节点：

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

所以我们已经处理abx并递减remainder到2。现在我们需要插入下一个剩余的后缀，bx。但在我们这样做之前，我们需要更新活动点。这个规则，在分割和插入一条边之后，将在下面被称为规则 1，它适用于任何时候 active_node是根的（我们将在下面进一步学习规则 3）。这是规则 1：

从根插入后，

active_node仍然是根

active_edge设置为我们需要插入的新后缀的第一个字符，即b

active_length减 1

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

同样，这需要 O(1) 时间，我们更新remainder为 1，活动点(root,'x',0)为规则 1 状态。

但是我们还需要做一件事。我们称之为规则 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并且什么都不做。

现在在step #=10中，remainder是 4，所以我们首先需要通过在活动点插入来插入abcd（从 3 步前保留）。d

尝试d在活动点插入会在 O(1) 时间内导致边缘分裂：

开始拆分的active_node，在上面用红色标记。这是最终规则，规则 3：

active_node在从一个不是根节点的边缘分割出一条边之后，我们沿着从那个节点出来的后缀链接（如果有的话），并将重置active_node为它指向的节点。如果没有后缀链接，我们将其设置active_node为根。active_edge 并active_length保持不变。

所以活动点现在是(node2,'c',1)，并node2在下面用红色标记：

由于的插入abcd已完成，我们减remainder为 3 并考虑当前步骤的下一个剩余后缀 bcd。规则 3 已将活动点设置为恰好正确的节点和边，因此bcd只需将其最后一个字符插入 d活动点即可完成插入。

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

我们观察到：后缀链接使我们能够重置活动点，以便我们可以在 O(1) 的努力下进行下一个剩余的插入。查看上图，确认 label 处的节点确实ab链接到节点 at b（其后缀），并且节点 atabc链接到 bc.

当前步骤尚未完成。remainder现在是 2，我们需要按照规则 3 重新设置活动点。由于当前active_node（上图红色）没有后缀链接，我们重置为 root。活动点是现在(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。原因是剩下的任何插入都将是我们刚刚尝试制作的插入的后缀。因此，它们都隐含在当前树中。>0的事实remainder确保我们稍后处理剩余的后缀。
如果算法结束时remainder>0怎么办？只要文本的结尾是之前某处出现的子字符串，就会出现这种情况。在这种情况下，我们必须在字符串末尾附加一个以前没有出现过的字符。在文献中，通常使用美元符号$作为其符号。为什么这很重要？--> 如果稍后我们使用完整的后缀树来搜索后缀，我们必须只接受以叶子结尾的匹配。否则我们会得到很多虚假匹配，因为树中隐含的许多字符串不是主字符串的实际后缀。强迫remainder结尾为 0 本质上是一种确保所有后缀都以叶节点结尾的方法。但是，如果我们想使用树来搜索一般子字符串，而不仅仅是主字符串的后缀，这最后一步确实不是必需的，正如下面 OP 的评论所建议的那样。
那么整个算法的复杂度是多少呢？如果文本长度为 n 个字符，则显然有 n 个步骤（如果我们添加美元符号，则为 n+1）。在每一步中，我们要么什么都不做（除了更新变量），要么进行remainder插入，每个都花费 O(1) 时间。因为remainder表示我们在前面的步骤中有多少次什么都没做，并且对于我们现在进行的每一次插入都会递减，所以我们做某事的总次数正好是 n（或 n+1）。因此，总复杂度为 O(n)。
但是，有一件小事我没有正确解释：可能会发生我们跟随后缀链接，更新活动点，然后发现其active_length组件与新的active_node. 例如，考虑这样的情况：

（虚线表示树的其余部分。虚线是后缀链接。）

现在让活动点为(red,'d',3)，因此它指向边缘后面f的位置。defg现在假设我们进行了必要的更新，现在按照后缀链接根据规则 3 更新活动点。新的活动点是(green,'d',3)。但是，d从绿色节点出来的 -edge 是de，所以它只有 2 个字符。为了找到正确的活动点，我们显然需要沿着那条边到达蓝色节点并重置为(blue,'f',1)。

在一个特别糟糕的情况下，active_length可能与一样大 remainder，也可能与 n 一样大。并且很可能会发生这样的情况，即要找到正确的活动点，我们不仅需要跳过一个内部节点，而且可能需要跳过很多，在最坏的情况下最多可达 n 个。这是否意味着该算法具有隐藏的 O(n ² ) 复杂度，因为在每个步骤remainder中通常是 O(n)，并且在遵循后缀链接之后对活动节点的后调整也可能是 O(n)？

不。原因是如果我们确实必须调整活动点（例如从绿色到蓝色），这会将我们带到一个拥有自己后缀链接的新节点，并且active_length会减少。随着我们沿着后缀链接链进行剩余的插入，active_length我们只能减少，并且我们可以在途中进行的活动点调整的数量不能大于active_length任何给定时间。由于 active_length永远不能大于remainder, 并且不仅在每一步都是 O(n)，而且在整个过程中remainder 所做的增量总和也是 O(n)，因此活动点调整的数量是remainder也以 O(n) 为界。

score 137 · Accepted Answer

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

使用的附加变量

活动点- 三元组 (active_node; active_edge; active_length)，显示我们必须从哪里开始插入新后缀。
余数- 显示我们必须显式添加的后缀数。例如，如果我们的单词是 'abcaabca'，并且余数 = 3，这意味着我们必须处理 3 个最后的后缀：bca、ca和a。

让我们使用一个内部节点的概念——除了根和叶子之外的所有节点都是内部节点。

观察 1

当我们需要插入的最后一个后缀被发现已经存在于树中时，树本身根本没有改变（我们只更新active pointand remainder）。

观察 2

如果在某个点active_length大于或等于当前边的长度 ( edge_length)，我们active point向下移动直到edge_length严格大于active_length。

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

规则1

如果从活动节点= root插入后，活动长度大于 0，则：

活动节点未更改

活动长度递减

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

规则 2

如果我们创建一个新的内部节点 或从一个内部节点创建一个插入器，并且这不是当前步骤中的第一个SUCH 内部节点，那么我们通过后缀链接将前一个SUCH节点与这个节点链接。

这个定义与Rule 2jogojapan' 不同，因为这里我们不仅考虑新创建的内部节点，还考虑我们从中进行插入的内部节点。

规则 3

从非根节点的活动节点插入后，我们必须按照后缀链接，将活动节点设置为它指向的节点。如果没有后缀链接，则将活动节点设置为根节点。无论哪种方式，有效边沿和有效长度都保持不变。

在这个定义中，Rule 3我们还考虑了叶节点的插入（不仅是分裂节点）。

最后，观察 3：

当我们要添加到树的符号已经在边缘时，我们根据Observation 1仅更新active point和remainder，使树保持不变。但是如果有一个内部节点被标记为需要后缀链接，我们必须通过后缀链接将该节点与我们的当前节点连接active node起来。

让我们看看cdddcdc的后缀树示例，如果我们在这种情况下添加后缀链接，如果我们不添加：

如果我们不通过后缀链接连接节点：
- 在添加最后一个字母c之前：
- 添加最后一个字母c后：
如果我们确实通过后缀链接连接节点：
- 在添加最后一个字母c之前：
- 添加最后一个字母c后：

似乎没有显着差异：在第二种情况下，还有两个后缀链接。但是这些后缀链接是正确的，其中之一——从蓝色节点到红色节点——对于我们的活动点方法非常重要。问题是，如果我们不在这里放一个后缀链接，以后当我们向树中添加一些新字母时，我们可能会因为省略向树中添加一些节点，因为根据它，如果没有 a后缀链接，那么一定要放到根目录下。Rule 3active_node

当我们将最后一个字母添加到树中时，红色节点在我们从蓝色节点插入之前已经存在（边缘标记为'c'）。由于蓝色节点有插入，我们将其标记为需要后缀链接。然后，依靠活动点方法，将active node其设置为红色节点。但是我们不会从红色节点插入，因为字母“c”已经在边缘。是不是说蓝色的节点一定要留不带后缀链接？不，我们必须通过后缀链接将蓝色节点与红色节点连接起来。为什么是正确的？因为活动点方法保证我们到达正确的位置，即到下一个我们必须处理较短后缀的插入的位置。

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

爪哇
C++

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

score 15 · Accepted Answer

抱歉，如果我的回答似乎多余，但我最近实现了 Ukkonen 的算法，发现自己为此苦苦挣扎了好几天；我必须通读有关该主题的多篇论文，以了解该算法某些核心方面的原因和方式。

我发现以前答案的“规则”方法对理解根本原因没有帮助，所以我在下面写的所有内容都只关注语用学。如果您像我一样难以遵循其他解释，也许我的补充解释会让您“点击”。

我在这里发布了我的 C# 实现：https ://github.com/baratgabor/SuffixTree

请注意，我不是该主题的专家，因此以下部分可能包含不准确之处（或更糟）。如果您遇到任何问题，请随时编辑。

先决条件

以下解释的起点假设您熟悉后缀树的内容和使用，以及 Ukkonen 算法的特征，例如您如何从头到尾逐个字符地扩展后缀树。基本上，我假设您已经阅读了其他一些解释。

（但是，我确实必须为流程添加一些基本的叙述，所以开始可能确实感觉多余。）

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

开放式叶节点及其局限性

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

但是这种后缀的开放式结尾——出于显而易见的原因——仅适用于表示字符串结尾的节点，即树结构中的叶节点。我们在树上执行的分支操作（添加新的分支节点和叶节点）不会自动传播到它们需要的任何地方。

这可能是基本的，并且不需要提及，重复的子字符串不会显式出现在树中，因为树已经包含这些，因为它们是重复的；但是，当重复子字符串以遇到非重复字符结束时，我们需要在该点创建一个分支来表示从该点开始的分歧。

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

再次强调——我们对树中的后缀执行的任何操作也需要通过其连续的后缀来反映（例如 ABC > BC > C），否则它们将不再是有效的后缀。

但是即使我们接受我们必须进行这些手动更新，我们怎么知道有多少后缀需要更新呢？因为，当我们添加重复的字符A（以及连续的其他重复字符）时，我们还不知道何时/何处需要将后缀分成两个分支。只有当我们遇到第一个非重复字符时，才确定需要拆分，在这种情况下是 Y（而不是树中已经存在的X ）。

我们能做的就是匹配最长的重复字符串，并计算我们以后需要更新多少个后缀。这就是“余数”的含义。

“剩余”和“重新扫描”的概念

该变量remainder告诉我们隐式添加了多少重复字符，没有分支；即一旦我们发现第一个无法匹配的字符，我们需要访问多少个后缀来重复分支操作。这基本上等于我们从树根开始在树中“深”了多少个字符。

因此，继续前面的字符串ABCXABCY 示例，我们“隐式”匹配重复的ABCremainder部分，每次递增，结果为余数 3。然后我们遇到非重复字符'Y'。这里我们将之前添加的ABCX 拆分为ABC -> X和ABC -> Y。然后我们remainder从 3 减少到 2，因为我们已经处理了ABC分支。现在我们通过匹配最后 2 个字符 - BC - 从根到我们需要拆分的点来重复操作，我们也将BCX拆分为BC-> X和BC -> Y。同样，我们递减remainder到 1，并重复操作；直到remainder为 0。最后，我们还需要将当前字符 ( Y ) 本身添加到根。

这个操作，从根开始跟随连续的后缀，只是为了到达我们需要进行操作的点，这就是 Ukkonen 算法中所谓的“重新扫描”，通常这是算法中最昂贵的部分。想象一个较长的字符串，您需要在其中“重新扫描”长子字符串，跨越数十个节点（我们将在稍后讨论），可能数千次。

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

“后缀链接”的概念

后缀链接基本上指向我们通常必须“重新扫描”到的位置，因此我们可以简单地跳转到链接位置，做我们的工作，跳转到下一个链接位置，然后重复 - 直到那里没有更多职位要更新。

当然，一个大问题是如何添加这些链接。现有的答案是，当我们插入新的分支节点时，我们可以添加链接，利用这一事实，在树的每个扩展中，分支节点自然地按照我们需要将它们链接在一起的确切顺序一个接一个地创建. 但是，我们必须从最后创建的分支节点（最长的后缀）链接到之前创建的分支节点，所以我们需要缓存我们创建的最后一个，将其链接到我们创建的下一个，并缓存新创建的。

一个后果是我们实际上通常没有后缀链接可遵循，因为给定的分支节点刚刚创建。在这些情况下，我们仍然必须从根目录退回到前面提到的“重新扫描” 。这就是为什么在插入之后，系统会指示您使用后缀链接或跳转到根目录。

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

“活动点”的概念

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

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

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

其次，即使添加了边信息，我们仍然无法识别在树中更靠下的位置，并且没有直接连接到根节点。所以我们也需要存储节点。我们称之为“活动节点”。

最后，我们可以注意到“剩余”不足以识别不直接连接到根的边上的位置，因为“剩余”是整个路线的长度；我们可能不想费心记住和减去前面边的长度。所以我们需要一个本质上是当前边上的余数的表示。这就是我们所说的“有效长度”。

这导致了我们所说的“活动点” ——一个包含三个变量的包，其中包含我们需要维护的关于我们在树中的位置的所有信息：

Active Point = (Active Node, Active Edge, Active Length)

您可以在下图中观察到ABCABD的匹配路线如何由边缘AB上的 2 个字符（来自root）加上边缘CABDABCABD上的 4 个字符（来自节点 4） - 导致 6 个字符的“剩余”。因此，我们当前的位置可以被识别为Active Node 4, Active Edge C, Active Length 4。

“活动点”的另一个重要作用是它为我们的算法提供了一个抽象层，这意味着我们的算法的某些部分可以在“活动点”上完成它们的工作，而不管该活动点是在根中还是在其他任何地方. 这使得在我们的算法中以简洁直接的方式实现后缀链接的使用变得容易。

重新扫描与使用后缀链接的区别

现在，根据我的经验，棘手的部分可能会导致大量错误和令人头疼的问题，并且在大多数来源中都没有得到很好的解释，那就是处理后缀链接案例与重新扫描案例的区别。

考虑下面的字符串'AAAABAAAABAAC'示例：

您可以在上面观察到 7 的“余数”如何对应于来自根的字符的总和，而4的“活动长度”对应于来自活动节点的活动边缘的匹配字符的总和。

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

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

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

带和不带后缀链接的处理示例比较

考虑上面示例的下一步会发生什么。让我们比较一下如何获得相同的结果——即移动到下一个要处理的后缀——有和没有后缀链接。

使用“后缀链接”

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

在上面的例子中，由于“活动长度”是 4，我们正在使用后缀“ ABAA”，从链接的节点 4 开始。但是在找到与后缀的第一个字符相对应的边之后（“A” )，我们注意到我们的“活动长度”超出了这条边 3 个字符。所以我们跳过整个边缘，到下一个节点，并通过我们在跳跃中消耗的字符来减少“活动长度” 。

然后，在我们找到下一条边'B'后，对应于递减的后缀'BAA '，我们终于注意到这条边的长度大于剩余的 'active length' 3，这意味着我们找到了正确的位置。

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

使用“重新扫描”

请注意，如果我们使用传统的“重新扫描”操作（假设我们没有后缀链接），我们从树的顶部开始，从根开始，我们必须再次向下工作到正确的位置，沿着当前后缀的整个长度。

这个后缀的长度就是我们之前讨论过的“余数” 。我们必须消耗掉这个剩余的全部，直到它达到零。这可能（并且经常这样做）包括跳过多个节点，在每次跳转时将剩余部分减少我们跳过的边的长度。最后，我们到达一个比我们剩余的“剩余”更长的边；在这里，我们将活动边缘设置为给定的边缘，将“活动长度”设置为剩余的“剩余”，我们就完成了。

但是请注意，实际的“剩余”变量需要保留，并且仅在每次插入节点后递减。所以我上面描述的假设使用一个单独的变量初始化为'remainder'。

关于后缀链接和重新扫描的说明

1) 请注意，这两种方法都会导致相同的结果。然而，在大多数情况下，后缀链接跳转要快得多。这就是后缀链接背后的全部原理。

2）实际的算法实现不需要不同。正如我上面提到的，即使在使用后缀链接的情况下，“活动长度”通常与链接位置不兼容，因为树的那个分支可能包含额外的分支。所以基本上你只需要使用'active length'而不是'remainder'，并执行相同的重新扫描逻辑，直到找到比剩余后缀长度短的边。

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

4）这里描述的原始后缀链接只是可能的方法之一。例如NJ Larsson 等人。将此方法命名为Node-Oriented Top-Down，并将其与Node-Oriented Bottom-Up和两个Edge-Oriented变体进行比较。不同的方法具有不同的典型和最坏情况性能、要求、限制等，但通常看来，面向边缘的方法是对原始方法的整体改进。

score 10 · Accepted Answer

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

@jogojapan 提到的几个小问题比我预期的要复杂得多，需要非常小心地处理。我花了几天时间才让我的实现足够健壮（我想）。问题及解决方法如下：

End withRemainder > 0事实证明，这种情况也可能发生在展开步骤期间，而不仅仅是整个算法的结束。发生这种情况时，我们可以保持剩余部分、actnode、actedge 和 actlength不变，结束当前展开步骤，然后根据原始字符串中的下一个字符是否在当前路径上或继续折叠或展开来开始另一个步骤不是。
Leap Over Nodes：当我们跟随一个后缀链接，更新活动点，然后发现它的 active_length 组件与新的 active_node 不能很好地协同工作。我们必须向前移动到正确的位置进行分裂，或者插入一片叶子。这个过程可能不是那么简单，因为在移动过程中 actlength 和 actedge 一直在变化，当您必须移回根节点时，由于这些移动，actedge和actlength可能是错误的。我们需要额外的变量来保存这些信息。

@managonov以某种方式指出了其他两个问题

拆分可能退化当尝试拆分一条边时，有时您会发现拆分操作正好在一个节点上。这种情况我们只需要给那个节点增加一个新的叶子，把它当作一个标准的边分裂操作，这意味着如果有后缀链接，应该相应地维护。
隐藏的后缀链接问题 1和问题 2引发了另一种特殊情况。有时我们需要跳过几个节点到正确的点进行分割，如果我们通过比较剩余字符串和路径标签来移动，我们可能会超过正确的点。这种情况下，后缀链接将被无意中忽略，如果有的话。这可以通过在前进时记住正确的点来避免。如果拆分节点已经存在，或者甚至问题 1在展开步骤中发生，则应维护后缀链接。

最后，我在Python中的实现如下：

Python

Tips：在上面的代码中 包含了一个朴素的树打印功能，这在调试时非常重要。它为我节省了很多时间，并且便于查找特殊情况。

score 9 · Accepted Answer

@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);
        }
    });
  }
}

score 6 · Accepted Answer

我的直觉如下：

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

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

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

在循环期间，关键是活动点。我的猜测是，这代表了后缀树中的最深点，它对应于字符串的前 k 个字符的正确后缀。（我认为正确的意思是后缀不能是整个字符串。）

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

活动点由 (origin,first,last) 表示。这意味着您当前位于通过从节点原点开始然后输入 string[first:last] 中的字符来到达的树中的点

添加新角色时，您会查看活动点是否仍在现有树中。如果是，那么你就完成了。否则你需要在活动点的后缀树中添加一个新节点，回退到下一个最短匹配，然后再次检查。

注 1：后缀指针给出了每个节点下一个最短匹配的链接。

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

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

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

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

score 3 · Accepted Answer

嗨，我已尝试在 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