Ukkonen 的后缀树算法用简单的英语
这个时候我觉得有点厚。我花了几天时间试图完全理解后缀树的构造，但由于我没有数学背景，许多解释都让我无法理解，因为他们开始过度使用数学符号。 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(n2)，因为我们需要遍历所有前缀，然后我们需要遍历每个前缀的每个后缀。 Ukkonen 的算法显然是独一无二的，因为他使用了后缀指针技术，尽管我认为这是我无法理解的。
我也很难理解：
究竟何时以及如何分配、使用和更改“活动点”
算法的规范化方面发生了什么
为什么我看到的实现需要“修复”他们正在使用的边界变量
这是完整的 C# 源代码。它不仅可以正常工作，而且支持自动规范化并呈现更好看的输出文本图。源代码和示例输出位于：
https://gist.github.com/2373868
2017-11-04 更新
多年后，我发现了后缀树的新用途，并在 JavaScript 中实现了该算法。要点如下。它应该没有错误。将其转储到 js 文件中，npm install chalk 从同一位置，然后使用 node.js 运行以查看一些彩色输出。在同一个 Gist 中有一个精简版本，没有任何调试代码。
https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6
下面尝试描述 Ukkonen 算法，首先显示字符串简单时（即不包含任何重复字符）时它的作用，然后将其扩展到完整算法。
首先，一些初步的陈述。
我们正在构建的基本上就像一个搜索尝试。所以有一个根节点，从它出来的边通向新节点，还有更多的边从这些节点出来，等等 但是：与搜索树不同，边标签不是单个字符。相反，每条边都使用一对整数 [from,to] 进行标记。这些是指向文本的指针。从这个意义上说，每条边都带有一个任意长度的字符串标签，但只占用 O(1) 空间（两个指针）。
基本原则
我想先演示一下如何创建一个特别简单的字符串的后缀树，一个没有重复字符的字符串：
abc
该算法从左到右逐步工作。字符串的每个字符都有一个步骤。每个步骤可能涉及不止一个单独的操作，但我们将看到（请参阅最后的观察结果）操作总数为 O(n)。
因此，我们从 left 开始，首先通过创建从根节点（左侧）到叶节点的边并将其标记为 [0,#]，从而仅插入单个字符 a，这意味着边缘表示从位置 0 开始并在 当前结束 结束的子字符串。我使用符号 # 来表示 当前结束，它位于位置 1（就在 a 之后）。
所以我们有一个初始树，它看起来像这样：
https://i.stack.imgur.com/aOwIL.png
这意味着：
https://i.stack.imgur.com/SZH4k.png
现在我们前进到位置 2（就在 b 之后）。 我们每一步的目标是插入所有后缀直到当前位置。我们这样做是通过
将现有的 a-edge 扩展到 ab
为 b 插入一条新边
在我们的代表中，这看起来像
https://i.stack.imgur.com/onmqt.png
它的意思是：
https://i.stack.imgur.com/tchAx.png
我们观察两件事：
ab 的边表示与它在初始树中的表示相同：[0,#]。它的含义已经自动改变，因为我们将当前位置 # 从 1 更新为 2。
每条边消耗 O(1) 空间，因为它只包含两个指向文本的指针，无论它代表多少个字符。
接下来，我们再次增加位置并通过将 c 附加到每个现有边并为新后缀 c 插入一条新边来更新树。
在我们的代表中，这看起来像
https://i.stack.imgur.com/wCEdI.png
它的意思是：
https://i.stack.imgur.com/UpUFw.png
我们观察到：
树是每一步之后直到当前位置的正确后缀树
文本中有多少个字符就有多少个步骤
每一步的工作量是 O(1)，因为所有现有边都会通过递增 # 自动更新，并且为最后一个字符插入一条新边可以在 O(1) 时间内完成。因此，对于长度为 n 的字符串，只需要 O(n) 时间。
第一次扩展：简单的重复
当然，这很好用只是因为我们的字符串不包含任何重复。我们现在看一个更真实的字符串：
abcabxabcd
它与前面的示例一样以 abc 开头，然后重复 ab，然后是 x，然后重复 abc，然后是 d。
第 1 步到第 3 步：在前 3 步之后，我们得到了上一个示例中的树：
https://i.stack.imgur.com/AclCh.png
第 4 步：我们将 # 移动到位置 4。这隐式地将所有现有边更新为：
https://i.stack.imgur.com/xhVMY.png
我们需要在根处插入当前步骤的最后一个后缀 a。
在我们这样做之前，我们引入了另外两个变量（除了 #），它们当然一直存在，但到目前为止我们还没有使用它们：
活动点，它是一个三元组 (active_node,active_edge,active_length)
余数，它是一个整数，表示我们需要插入多少个新后缀
这两个的确切含义很快就会变得清晰，但现在让我们说：
在简单的 abc 示例中，活动点始终为 (root,'\0x',0)，即 active_node 为根节点，active_edge 指定为空字符 '\0x'，active_length 为零。这样做的效果是，我们在每一步中插入的一条新边作为新创建的边插入根节点。我们很快就会看到为什么需要一个三元组来表示这个信息。
在每一步开始时，余数总是设置为 1。这意味着我们必须在每一步结束时主动插入的后缀数量为 1（始终只是最后一个字符）。
现在这将改变。当我们在根处插入当前最后一个字符 a 时，我们注意到已经有一个以 a 开头的出边，具体来说：abca。这是我们在这种情况下所做的：
我们不在根节点插入新边 [4,#]。相反，我们只是注意到后缀 a 已经在我们的树中。它在较长边缘的中间结束，但我们并不为此烦恼。我们只是让事情保持原样。
我们将活动点设置为 (root,'a',1)。这意味着活动点现在位于以 a 开头的根节点的出边中间的某个位置，特别是在该边上的位置 1 之后。我们注意到边仅由它的第一个字符 a 指定。这已经足够了，因为只能有一个以任何特定字符开头的边（在阅读整个描述后确认这是真的）。
我们还增加了余数，所以在下一步开始时它将是 2。
观察：当发现最后一个我们需要插入的后缀已经存在于树中时，树本身就没有改变（我们只更新活动点和remainder）。该树不再是后缀树到当前位置的准确表示，但它包含所有后缀（因为包含最终后缀 a em>隐式）。因此，除了更新变量（都是固定长度的，所以这是 O(1)）之外，在这一步中没有工作。
第 5 步：我们将当前位置 # 更新为 5。这会自动将树更新为：
https://i.stack.imgur.com/XL6bg.png
而因为remainder是2，我们需要插入当前位置的两个最终后缀：ab和b。这基本上是因为：
上一步中的 a 后缀从未正确插入。所以它一直存在，并且由于我们已经前进了一步，它现在已经从 a 增长到 ab。
我们需要插入新的最终边 b。
在实践中，这意味着我们转到活动点（它指向现在 abcab 边上的 a 后面），并插入当前的最终字符 b。 但是：再次证明，b 也已经出现在同一边缘上。
所以，再一次，我们不改变树。我们简单地：
将活动点更新为 (root,'a',2) （与之前相同的节点和边，但现在我们指向 b 后面）
将余数增加到 3，因为我们仍然没有正确插入上一步的最终边，而且我们也没有插入当前的最终边。
需要明确的是：我们必须在当前步骤中插入 ab 和 b，但因为已经找到 ab，我们更新了活动点，甚至没有尝试插入 b。为什么？因为如果 ab 在树中，它的每个后缀（包括 b）也必须在树中。也许只是隐式地，但它必须在那里，因为到目前为止我们构建树的方式。
我们通过递增 # 继续第 6 步。树会自动更新为：
https://i.stack.imgur.com/bLLT9.png
因为 remainder 是 3，我们必须插入 abx、bx 和 x。活动点告诉我们 ab 在哪里结束，所以我们只需要跳转到那里并插入 x。实际上，x 还不存在，所以我们分割 abcabx 边并插入一个内部节点：
https://i.stack.imgur.com/6HYtR.png
边缘表示仍然是指向文本的指针，因此可以在 O(1) 时间内完成拆分和插入内部节点。
所以我们已经处理了 abx 并将 remainder 减为 2。现在我们需要插入下一个剩余的后缀 bx。但在我们这样做之前，我们需要更新活动点。这个规则，在分割和插入一条边之后，将在下面称为 Rule 1，并且只要 active_node 是根就适用（我们将在下面进一步了解规则 3）。这是规则 1：
从root插入后，active_node保持root active_edge设置为我们需要插入的新后缀的第一个字符，即b active_length减1
因此，新的活动点三元组(root,'b',1) 表示下一个插入必须在bcabx 边缘进行，在1 个字符之后，即在b 之后。我们可以在 O(1) 时间内识别插入点并检查 x 是否已经存在。如果它存在，我们将结束当前步骤并保持一切原状。但是 x 不存在，所以我们通过分割边缘来插入它：
https://i.stack.imgur.com/YVvbJ.png
同样，这花费了 O(1) 时间，我们将 remainder 更新为 1，并将活动点更新为 (root,'x',0)，如规则 1 所述。
但是我们还需要做一件事。我们称之为规则 2：
如果我们分割一条边并插入一个新节点，并且如果这不是在当前步骤中创建的第一个节点，我们将通过一个特殊的指针连接先前插入的节点和新节点，一个后缀链接。我们稍后会看到为什么这很有用。这是我们得到的，后缀链接表示为虚线边缘：
https://i.stack.imgur.com/zL9yl.png
我们仍然需要插入当前步骤的最后一个后缀，x。由于活动节点的active_length分量已经下降到0，所以最后的插入直接在根节点进行。由于从 x 开始的根节点没有出边，我们插入一条新边：
https://i.stack.imgur.com/992gV.png
正如我们所看到的，在当前步骤中，所有剩余的插入都已完成。
我们通过设置 #=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) 时间内导致边缘分裂：
https://i.stack.imgur.com/Rkdzd.png
从中启动拆分的 active_node 在上面用红色标记。这是最终规则，规则 3：
在从不是根节点的 active_node 分割一条边后，我们沿着从该节点出来的后缀链接（如果有），并将 active_node 重置为它指向的节点。如果没有后缀链接，我们将active_node设置为root。 active_edge 和 active_length 保持不变。
所以活动点现在是 (node2,'c',1)，而 node2 在下面用红色标记：
https://i.stack.imgur.com/0IS5C.png
由于 abcd 的插入完成，我们将 remainder 减为 3，并考虑当前步骤的下一个剩余后缀 bcd。规则 3 已将活动点设置为恰好正确的节点和边，因此只需在活动点插入其最后一个字符 d 即可插入 bcd。
这样做会导致另一个边分裂，并且由于规则 2，我们必须创建一个从先前插入的节点到新节点的后缀链接：
https://i.stack.imgur.com/DNVQO.png
我们观察到：后缀链接使我们能够重置活动点，以便我们可以在 O(1) 的努力下进行下一个剩余的插入。查看上图以确认标签 ab 处的节点确实链接到 b 处的节点（其后缀），并且 abc 处的节点链接到 bc。
当前步骤尚未完成。 remainder 现在是 2，我们需要按照规则 3 再次重置活动点。由于当前的 active_node（上图红色）没有后缀链接，我们重置为 root。活动点现在是 (root,'c',1)。
因此，下一次插入发生在标签以c 开头的根节点的一个输出边上：cabxabcd，在第一个字符之后，即在c 之后。这会导致另一个分裂：
https://i.stack.imgur.com/wZ7Bj.png
由于这涉及到创建一个新的内部节点，我们遵循规则 2 并从先前创建的内部节点设置一个新的后缀链接：
https://i.stack.imgur.com/urgol.png
（我对这些小图使用 Graphviz Dot。新的后缀链接导致 dot 重新排列现有边，因此请仔细检查以确认上面插入的唯一内容是新的后缀链接。）
这样，remainder 可以设置为 1，并且由于 active_node 是根，我们使用规则 1 将活动点更新为 (root,'d',0)。这意味着当前步骤的最后插入是在根处插入一个 d：
https://i.stack.imgur.com/TPxLe.png
这是最后一步，我们完成了。不过，有一些最终的观察结果：
在每一步中，我们将 # 向前移动 1 个位置。这会在 O(1) 时间内自动更新所有叶节点。
但它不处理 a) 先前步骤中剩余的任何后缀，以及 b) 当前步骤的最后一个字符。
余数告诉我们需要做多少额外的插入。这些插入与在当前位置 # 结束的字符串的最终后缀一一对应。我们一个接一个地考虑并进行插入。重要提示：每次插入都在 O(1) 时间内完成，因为活动点会告诉我们确切的去向，我们只需要在活动点添加一个字符。为什么？因为其他字符被隐式包含（否则活动点不会在它所在的位置）。
在每个这样的插入之后，我们减少余数并按照后缀链接（如果有的话）。如果不是，我们就进入根目录（规则 3）。如果我们已经在根节点，我们使用规则 1 修改活动点。无论如何，它只需要 O(1) 时间。
如果在其中一次插入过程中，我们发现要插入的字符已经存在，我们什么也不做，结束当前步骤，即使余数>0。原因是剩下的任何插入都将是我们刚刚尝试制作的插入的后缀。因此，它们都隐含在当前树中。余数>0 的事实确保我们稍后处理剩余的后缀。
如果在算法结束时余数>0怎么办？只要文本的结尾是之前某处出现的子字符串，就会出现这种情况。在这种情况下，我们必须在字符串末尾附加一个以前没有出现过的字符。在文献中，通常使用美元符号 $ 作为其符号。为什么这很重要？ --> 如果稍后我们使用完整的后缀树来搜索后缀，我们必须只接受以叶子结尾的匹配。否则我们会得到很多虚假匹配，因为树中隐含的许多字符串不是主字符串的实际后缀。在末尾强制余数为 0 本质上是一种确保所有后缀在叶节点处结束的方法。但是，如果我们想使用树来搜索一般子字符串，而不仅仅是主字符串的后缀，那么这最后一步确实不是必需的，正如下面 OP 的评论所建议的那样。
那么整个算法的复杂度是多少呢？如果文本长度为 n 个字符，则显然有 n 个步骤（如果我们添加美元符号，则为 n+1）。在每个步骤中，我们要么什么都不做（除了更新变量），要么进行余数插入，每次都花费 O(1) 时间。由于余数表示我们在前面的步骤中什么都不做的次数，并且对于我们现在进行的每一次插入都会递减，所以我们做某事的总次数正好是 n（或 n+1）。因此，总复杂度为 O(n)。
但是，有一件小事我没有正确解释：可能会发生我们跟随后缀链接，更新活动点，然后发现它的 active_length 组件与新的 active_node 无法正常工作。例如，考虑这样的情况：
https://i.stack.imgur.com/7t0dg.png
（虚线表示树的其余部分。虚线是后缀链接。）
现在让活动点为 (red,'d',3)，因此它指向 defg 边上 f 后面的位置。现在假设我们进行了必要的更新，现在按照后缀链接按照规则 3 更新活动点。新的活动点是 (green,'d',3)。但是，从绿色节点出来的d-边是de，所以它只有2个字符。为了找到正确的活动点，我们显然需要沿着该边到达蓝色节点并重置为 (blue,'f',1)。
在特别糟糕的情况下，active_length 可能与 remainder 一样大，而 remainder 可能与 n 一样大。并且很可能会发生这样的情况，即要找到正确的活动点，我们不仅需要跳过一个内部节点，而且可能需要跳过很多，在最坏的情况下最多可达 n 个。这是否意味着该算法具有隐藏的 O(n2) 复杂度，因为在每个步骤中 remainder 通常为 O(n)，并且在跟随后缀链接后对活动节点的后调整也可能是 O(n)？
不。原因是如果我们确实必须调整活动点（例如从绿色到蓝色），这会将我们带到一个拥有自己后缀链接的新节点，并且 active_length 将被减少。当我们沿着后缀链接链进行剩余插入时，active_length 只能减少，并且在任何给定时间我们可以在途中进行的活动点调整的数量不能大于 active_length。因为 active_length 永远不会大于 remainder，而且 remainder 不仅在每一步都是 O(n)，而且在整个过程中对 remainder 所做的增量总和是 O (n) 同样，活动点调整的数量也受 O(n) 的限制。
我尝试使用 jogojapan 的答案中给出的方法来实现后缀树，但由于用于规则的措辞，它在某些情况下不起作用。此外，我已经提到没有人能够使用这种方法实现绝对正确的后缀树。下面我将写一个 jogojapan 答案的“概述”，并对规则进行一些修改。我还将描述我们忘记创建重要后缀链接的情况。
使用的附加变量
活动点 - 三元组 (active_node; active_edge; active_length)，显示我们必须从哪里开始插入新后缀。余数 - 显示我们必须明确添加的后缀数。例如，如果我们的单词是“abcaabca”，并且余数 = 3，这意味着我们必须处理 3 个最后的后缀：bca、ca 和 a。
让我们使用内部节点的概念——除了根和叶子之外的所有节点都是内部节点。
观察 1
当发现我们需要插入的最后一个后缀已经存在于树中时，树本身并没有改变（我们只更新了active point和remainder）。
观察 2
如果在某个点 active_length 大于或等于当前边的长度 (edge_length)，我们将 active point 向下移动，直到 edge_length 严格大于 active_length。
现在，让我们重新定义规则：
规则1
如果从活动节点 = 根插入后，活动长度大于 0，则： 活动节点不变 活动长度递减 活动边缘右移（必须插入下一个后缀的第一个字符）
规则 2
如果我们创建一个新的内部节点或从一个内部节点创建一个插入器，并且这不是当前步骤中的第一个 SUCH 内部节点，那么我们通过后缀链接将前一个 SUCH 节点与这个节点链接。
Rule 2 的这个定义与 jogojapan' 不同，因为这里我们不仅考虑了新创建的 内部节点，还考虑了我们从中进行插入的内部节点。
规则 3
从非根节点的活动节点插入后，我们必须按照后缀链接，将活动节点设置为它指向的节点。如果没有后缀链接，则将活动节点设置为根节点。无论哪种方式，有效边沿和有效长度都保持不变。
在 Rule 3 的这个定义中，我们还考虑了叶节点的插入（不仅是分裂节点）。
最后，观察 3：
当我们要添加到树的符号已经在边缘时，我们根据 Observation 1 只更新 active point 和 remainder，保持树不变。 但是如果有一个内部节点标记为需要后缀链接，我们必须通过后缀链接将该节点与我们当前的active node连接起来。
让我们看看 cdddcdc 的后缀树示例，如果我们在这种情况下添加后缀链接，如果我们不添加：
如果我们不通过后缀链接连接节点：在添加最后一个字母之前 c：在添加最后一个字母之后 c：如果我们通过后缀链接连接节点：在添加最后一个字母之前 c：在添加最后一个字母之后C：
似乎没有显着差异：在第二种情况下，还有两个后缀链接。但是这些后缀链接是正确的，其中一个 - 从蓝色节点到红色节点 - 对于我们的 活动点 方法非常重要 >。问题是，如果我们不在这里放一个后缀链接，那么当我们在树中添加一些新字母时，我们可能会因为 Rule 3 而忽略向树中添加一些节点，因为根据它，如果没有后缀链接，那么我们必须把 active_node 放到根。
当我们将最后一个字母添加到树中时，在我们从蓝色节点（标记为 'c' 的边）插入之前，红色节点已经已经存在。由于有来自蓝色节点的插入，我们将其标记为需要后缀链接。然后，依靠 活动点 方法，将 active node 设置为红色节点。但是我们不会从红色节点插入，因为字母 'c' 已经在边缘了。是不是说蓝色的节点一定要留不带后缀链接？不，我们必须通过后缀链接将蓝色节点与红色节点连接起来。为什么是正确的？因为active point 方法保证我们到达正确的位置，即到下一个我们必须处理插入shorter 后缀的位置。
最后，这是我对后缀树的实现：
Java C++
希望这个“概述”结合 jogojapan 的详细答案将帮助某人实现他自己的后缀树。
aabaacaad 是显示添加额外后缀链接可以减少更新三元组次数的案例之一。 jogojapan帖子最后两段的结论是错误的。如果我们不添加这篇文章提到的后缀链接，平均时间复杂度应该是 O(nlong(n)) 或更多。因为遍历树以找到正确的 active_node 需要额外的时间。
抱歉，如果我的回答似乎多余，但我最近实现了 Ukkonen 的算法，发现自己为此苦苦挣扎了好几天；我必须通读有关该主题的多篇论文，以了解该算法某些核心方面的原因和方式。
我发现以前答案的“规则”方法对理解根本原因没有帮助，所以我在下面写的所有内容都只关注语用学。如果您像我一样难以遵循其他解释，也许我的补充解释会让您“点击”。
我在这里发布了我的 C# 实现：https://github.com/baratgabor/SuffixTree
请注意，我不是该主题的专家，因此以下部分可能包含不准确之处（或更糟）。如果您遇到任何问题，请随时编辑。
先决条件
以下解释的起点假设您熟悉后缀树的内容和使用，以及 Ukkonen 算法的特征，例如您如何从头到尾逐个字符地扩展后缀树。基本上，我假设您已经阅读了其他一些解释。
（但是，我确实必须为流程添加一些基本的叙述，所以开始可能确实感觉多余。）
最有趣的部分是对使用后缀链接和从根重新扫描之间的区别的解释。这就是在我的实现中给我带来很多错误和头痛的原因。
开放式叶节点及其局限性
我相信你已经知道最基本的“技巧”是意识到我们可以让后缀的结尾保持“开放”，即引用字符串的当前长度而不是将结尾设置为静态值。这样，当我们添加额外的字符时，这些字符将被隐式添加到所有后缀标签中，而无需访问和更新所有它们。
但是这种后缀的开放式结尾——出于显而易见的原因——仅适用于表示字符串结尾的节点，即树结构中的叶节点。我们在树上执行的分支操作（添加新的分支节点和叶节点）不会自动传播到它们需要的任何地方。
这可能是基本的，并且不需要提及，重复的子字符串不会显式出现在树中，因为树已经包含这些，因为它们是重复的；但是，当重复子字符串以遇到非重复字符结束时，我们需要在该点创建一个分支来表示从该点开始的分歧。
例如，对于字符串 'ABCXABCY'（见下文），需要将到 X 和 Y 的分支添加到三个不同的后缀，ABC、BC 和 C；否则它将不是一个有效的后缀树，并且我们无法通过从根向下匹配字符来找到字符串的所有子字符串。
再次强调——我们对树中的后缀执行的任何操作也需要通过其连续的后缀来反映（例如 ABC > BC > C），否则它们将不再是有效的后缀。
https://i.stack.imgur.com/pyaNY.png
但是即使我们接受我们必须进行这些手动更新，我们怎么知道有多少后缀需要更新呢？因为，当我们添加重复的字符 A（以及连续的其他重复字符）时，我们还不知道何时/何处需要将后缀分成两个分支。只有当我们遇到第一个非重复字符时，才确定需要拆分，在这种情况下是 Y（而不是树中已经存在的 X）。
我们能做的就是匹配最长的重复字符串，并计算我们以后需要更新多少个后缀。这就是“余数”的含义。
“剩余”和“重新扫描”的概念
变量 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 算法中所谓的“重新扫描”，通常这是算法中最昂贵的部分。想象一个较长的字符串，您需要在其中“重新扫描”长子字符串，跨越数十个节点（我们将在稍后讨论），可能数千次。
作为一种解决方案，我们引入了我们所说的“后缀链接”。
“后缀链接”的概念
后缀链接基本上指向我们通常必须“重新扫描”到的位置，因此我们可以简单地跳转到链接位置，做我们的工作，跳转到下一个链接位置，然后重复 - 直到那里没有更多职位要更新。
当然，一个大问题是如何添加这些链接。现有的答案是，我们可以在插入新的分支节点时添加链接，利用这样一个事实，即在树的每个扩展中，分支节点自然会按照我们需要将它们链接在一起的确切顺序一个接一个地创建.但是，我们必须从最后创建的分支节点（最长的后缀）链接到之前创建的分支节点，因此我们需要缓存我们创建的最后一个，将其链接到我们创建的下一个，并缓存新创建的。
一个后果是我们实际上通常没有后缀链接可遵循，因为给定的分支节点刚刚创建。在这些情况下，我们仍然必须从根目录退回到前面提到的“重新扫描”。这就是为什么在插入之后，系统会指示您使用后缀链接或跳转到根目录。
（或者，如果您将父指针存储在节点中，您可以尝试跟随父节点，检查它们是否有链接，然后使用它。我发现这很少被提及，但后缀链接的用法不是一成不变。有多种可能的方法，如果您了解底层机制，您可以实施最适合您需求的一种。）
“活动点”的概念
到目前为止，我们讨论了多种构建树的有效工具，并模糊地提到了遍历多个边和节点，但还没有探索相应的后果和复杂性。
前面解释的“剩余”概念对于跟踪我们在树中的位置很有用，但我们必须意识到它没有存储足够的信息。
首先，我们总是驻留在节点的特定边上，因此我们需要存储边信息。我们称之为“主动边缘”。
其次，即使添加了边信息，我们仍然无法识别在树中更靠下的位置，并且没有直接连接到根节点。所以我们也需要存储节点。我们称之为“活动节点”。
最后，我们可以注意到“剩余”不足以识别不直接连接到根的边上的位置，因为“剩余”是整个路线的长度；我们可能不想费心记住和减去前面边的长度。所以我们需要一个本质上是当前边上的余数的表示。这就是我们所说的“有效长度”。
这导致了我们所说的“活动点”——一个包含三个变量的包，其中包含我们需要维护的关于我们在树中的位置的所有信息：
Active Point = (Active Node, Active Edge, Active Length)
您可以在下图中观察到 ABCABD 的匹配路线如何由边缘 AB 上的 2 个字符（从根）和边缘 CABDABCABD 上的 4 个字符（从节点 4）组成 - 导致 6 个字符的“剩余”。所以，我们当前的位置可以标识为Active Node 4，Active Edge C，Active Length 4。
https://i.stack.imgur.com/FdbDQ.png
“活动点”的另一个重要作用是它为我们的算法提供了一个抽象层，这意味着我们的算法的一部分可以在“活动点”上完成它们的工作，而不管该活动点是在根中还是在其他任何地方.这使得在我们的算法中以简洁直接的方式实现后缀链接的使用变得容易。
重新扫描与使用后缀链接的区别
现在，根据我的经验，棘手的部分可能会导致大量错误和令人头疼的问题，并且在大多数来源中都没有得到很好的解释，那就是处理后缀链接案例与重新扫描案例的区别。
考虑以下字符串 'AAAABAAAAABAAC' 的示例：
https://i.stack.imgur.com/YdSPZ.png
您可以在上面观察到 7 的“余数”如何对应于来自根的字符的总和，而 4 的“活动长度”对应于来自活动节点的活动边缘的匹配字符的总和。
现在，在活动点执行分支操作后，我们的活动节点可能包含也可能不包含后缀链接。
如果存在后缀链接：我们只需要处理“活动长度”部分。 “余数”是无关紧要的，因为我们通过后缀链接跳转到的节点已经隐含地编码了正确的“余数”，这仅仅是因为它位于它所在的树中。
如果后缀链接不存在：我们需要从零/根“重新扫描”，这意味着从头开始处理整个后缀。为此，我们必须使用整个“剩余”作为重新扫描的基础。
带和不带后缀链接的处理示例比较
考虑上面示例的下一步会发生什么。让我们比较一下如何获得相同的结果——即移动到下一个要处理的后缀——有和没有后缀链接。
使用“后缀链接”
https://i.stack.imgur.com/OXxrn.png
请注意，如果我们使用后缀链接，我们会自动“在正确的位置”。由于“有效长度”可能与新位置“不兼容”，因此这通常并不严格。
在上面的例子中，由于“活动长度”是 4，我们正在使用后缀“ABAA”，从链接的节点 4 开始。但是在找到与后缀的第一个字符（“A”）相对应的边之后)，我们注意到我们的“活动长度”超出了这条边 3 个字符。所以我们跳过整个边缘，到下一个节点，并通过我们在跳跃中消耗的字符来减少“活动长度”。
然后，在我们找到下一条边“B”后，对应于递减的后缀“BAA”，我们终于注意到边长大于剩余的“活动长度”3，这意味着我们找到了正确的位置。
请注意，这个操作似乎通常不被称为“重新扫描”，尽管对我来说它似乎是重新扫描的直接等价物，只是长度缩短了，起点没有根。
使用“重新扫描”
https://i.stack.imgur.com/2L6U1.png
请注意，如果我们使用传统的“重新扫描”操作（这里假设我们没有后缀链接），我们从树的顶部开始，从根开始，我们必须再次向下工作到正确的位置，沿着当前后缀的整个长度。
这个后缀的长度就是我们之前讨论过的“余数”。我们必须消耗掉这个剩余的全部，直到它达到零。这可能（并且经常这样做）包括跳过多个节点，在每次跳转时将剩余部分减少我们跳过的边的长度。最后，我们到达一个比我们剩余的“剩余”更长的边；在这里，我们将活动边设置为给定的边，将“活动长度”设置为剩余的“剩余”，我们就完成了。
但是请注意，实际的“剩余”变量需要保留，并且仅在每次插入节点后递减。所以我上面描述的假设使用一个单独的变量初始化为“余数”。
关于后缀链接和重新扫描的说明
1) 请注意，这两种方法都会导致相同的结果。然而，在大多数情况下，后缀链接跳转要快得多。这就是后缀链接背后的全部原理。
2）实际的算法实现不需要不同。正如我上面提到的，即使在使用后缀链接的情况下，“活动长度”通常与链接位置不兼容，因为树的那个分支可能包含额外的分支。所以本质上你只需要使用“活动长度”而不是“剩余”，并执行相同的重新扫描逻辑，直到找到比剩余后缀长度短的边。
3) 关于性能的一个重要说明是在重新扫描期间无需检查每个字符。由于构建有效后缀树的方式，我们可以安全地假设字符匹配。所以你主要计算长度，当我们跳转到新边时，唯一需要进行字符等价检查，因为边由它们的第一个字符标识（在给定节点的上下文中总是唯一的）。这意味着“重新扫描”逻辑不同于完整的字符串匹配逻辑（即在树中搜索子字符串）。
4) 这里描述的原始后缀链接只是一种可能的方法。例如 NJ Larsson et al. 将此方法命名为 Node-Oriented Top-Down，并将其与 Node-Oriented Bottom-Up 和两个 Edge-Oriented 进行比较em>品种。不同的方法具有不同的典型和最差情况性能、要求、限制等，但通常Edge-Oriented 方法似乎是对原始方法的整体改进。
@jogojapan 你带来了很棒的解释和可视化。但正如@makagonov 提到的，它缺少一些关于设置后缀链接的规则。当通过单词'aabaaabb'一步一步地在http://brenden.github.io/ukkonen-animation/上进行时，它以很好的方式可见。当您从第 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);
}
});
}
}
感谢@jogojapan 精心解释的教程，我在 Python 中实现了算法。
@jogojapan 提到的几个小问题比我预期的要复杂得多，需要非常小心地处理。我花了几天时间才让我的实现足够健壮（我想）。问题及解决方法如下：
End with Remainder > 0 事实证明，这种情况也可能发生在展开步骤期间，而不仅仅是整个算法的结束。发生这种情况时，我们可以保持余数、actnode、actedge 和 actlength 不变，结束当前展开步骤，然后根据原始字符串中的下一个字符是否在当前路径上或继续折叠或展开来开始另一个步骤不是。 Leap Over Nodes：当我们跟随一个后缀链接，更新活动点，然后发现它的 active_length 组件与新的 active_node 不能很好地协同工作。我们必须向前移动到正确的位置进行分裂，或者插入一片叶子。这个过程可能不是那么简单，因为在移动过程中，actlength 和 actedge 一直在变化，当您必须移回根节点时，由于这些移动，actedge 和 actlength 可能是错误的。我们需要额外的变量来保存这些信息。
@managonov 以某种方式指出了其他两个问题
拆分可能退化当尝试拆分一条边时，有时您会发现拆分操作正好在一个节点上。这种情况我们只需要在那个节点上添加一个新的叶子，把它当作一个标准的边分裂操作，这意味着如果有后缀链接，应该相应地维护。隐藏后缀链接问题1和问题2还有一种特殊情况。有时我们需要跳过几个节点到正确的点进行拆分，如果我们通过比较剩余字符串和路径移动可能会超过正确的点标签。这种情况下，后缀链接将被无意中忽略，如果有的话。这可以通过在前进时记住正确的点来避免。如果拆分节点已经存在，或者甚至问题 1 在展开步骤中发生，则应维护后缀链接。
最后，我在 Python 中的实现如下：
Python
Tips：在上面的代码中包含了一个朴素的树打印功能，这在调试时非常重要。它为我节省了很多时间，并且便于查找特殊情况。
我的直觉如下：
在主循环的 k 次迭代之后，您构建了一个后缀树，其中包含从前 k 个字符开始的完整字符串的所有后缀。
一开始，这意味着后缀树包含一个代表整个字符串的根节点（这是唯一从 0 开始的后缀）。
在 len(string) 迭代之后，您有一个包含所有后缀的后缀树。
在循环期间，关键是活动点。我的猜测是，这代表了后缀树中的最深点，它对应于字符串的前 k 个字符的正确后缀。 （我认为正确的意思是后缀不能是整个字符串。）
例如，假设您看到了字符“abcabc”。活动点将表示树中对应于后缀“abc”的点。
活动点由 (origin,first,last) 表示。这意味着您当前位于通过从节点原点开始然后输入 string[first:last] 中的字符来到达的树中的点
添加新角色时，您会查看活动点是否仍在现有树中。如果是，那么你就完成了。否则你需要在活动点的后缀树中添加一个新节点，回退到下一个最短匹配，然后再次检查。
注 1：后缀指针给出了每个节点下一个最短匹配的链接。
注意 2：当您添加一个新节点并回退时，您会为新节点添加一个新的后缀指针。此后缀指针的目的地将是缩短的活动点处的节点。该节点要么已经存在，要么在此回退循环的下一次迭代中创建。
注3：规范化部分只是节省了检查活动点的时间。例如，假设您始终使用 origin=0，并且只更改了 first 和 last。要检查活动点，您每次都必须沿着所有中间节点遵循后缀树。通过仅记录与最后一个节点的距离来缓存遵循此路径的结果是有意义的。
您能否举一个代码示例来说明“修复”边界变量的含义？
健康警告：我还发现这个算法特别难以理解，所以请意识到这种直觉可能在所有重要细节上都不正确......
嗨，我已尝试在 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
关注公众号
不定期副业成功案例分享
abcdefabxybcdmnabcdex。abcd的初始部分在abxy中重复（这在ab之后创建了一个内部节点）并在abcdex中再次重复，并以bcd结束，它不仅出现在bcdex上下文中，但也在bcdmn上下文中。插入abcdex后，我们按照后缀链接插入bcdex，然后canonicize就会启动。