Ukkonen 的后缀树算法（简体中文）

我的直觉如下：

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

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

在 len（string） 迭代之后，您将拥有一个包含所有后缀的后缀树。

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

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

活动点用 （origin，first，last） 表示。 这意味着您当前位于树中的点，您从节点原点开始，然后输入字符串[first：last]中的字符

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

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

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

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

你能给出一个代码示例来说明你所说的“修复”边界变量是什么意思吗？

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

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

首先，一些初步陈述。

1. 我们正在构建的东西，基本上就像一个搜索尝试。所以那里 是一个根节点，从它出来的边通向新节点，并且 从这些中走出的进一步边缘，依此类推

2. 但是：与搜索尝试不同，边缘标签不是单一的 字符。取而代之的是，每条边都使用一对整数进行标记。这些是指向文本的指针。从这个意义上说，每个 edge 带有任意长度的字符串标签，但只取 O（1） 空格（两个指针）。[from,to]

基本原理

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

abc

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

因此，我们从左边开始，首先通过创建从根节点（左侧）到叶子的边缘，只插入单个字符， 并将其标记为 ，这意味着边代表 子字符串从位置 0 开始，到当前结束。我 使用符号表示当前端，即位置 1 （紧接着）。a[0,#]#a

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

它的意思是这样的：

现在我们前进到位置 2（紧接着）。我们在每个步骤中的目标是将所有后缀插入到当前位置。我们这样做 由b

• 将现有的 -edge 扩展到aab
• 插入一条新边b

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

这意味着：

我们观察到两件事：

• 的边表示与以前相同 在初始树中：。它的含义已自动更改 因为我们将当前位置从 1 更新为 2。ab[0,#]#
• 每条边占用 O（1） 空间，因为它只包含两条边 指向文本的指针，无论它有多少个字符 代表。

接下来，我们再次增加位置，并通过附加 a 添加到每个现有边，并为新边插入一条新边 后缀。cc

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

这意味着：

我们观察到：

• 树是正确的后缀树，直到每一步后的当前位置
• 步骤与文本中的字符一样多
• 每个步骤的工作量为 O（1），因为所有现有边 通过递增 自动更新，然后插入 最终字符的一条新边可以在 O（1） 中完成 时间。因此，对于长度为 n 的字符串，只需要 O（n） 时间。#

第一个扩展：简单的重复

当然，这之所以如此有效，只是因为我们的字符串没有 包含任何重复项。现在，我们来看一个更现实的字符串：

abcabxabcd

它以前面的示例开头，然后重复 后跟 ，然后重复后跟 。abcabxabcd

第 1 步到第 3 步：在前 3 个步骤之后，我们得到了上一个示例中的树：

步骤4：我们移动到位置 4。这会隐式更新所有现有的 边缘：#

我们需要插入当前步骤的最后一个后缀 ， ， 根。a

在我们这样做之前，我们再介绍两个变量（除了 ），当然它们一直存在，但我们没有使用 到目前为止，他们：#

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

这两者的确切含义很快就会变得清晰，但就目前而言 让我们说：

• 在简单的例子中，活动点始终是 ，即 是根节点，被指定为 null 字符，并且为零。这样做的效果是，一个新的边缘 我们插入的每个步骤都作为根节点插入 新创建的边缘。我们很快就会看到为什么需要三重奏 表示此信息。abc(root,'\0x',0)active_nodeactive_edge'\0x'active_length
• 在每个开头始终设置为 1 步。这句话的意思是，我们必须 在每个步骤结束时主动插入是 1（总是只是 最终字符）。remainder

现在这种情况将会改变。当我们插入当前final时 字符，我们注意到已经有一个传出 边缘以 开头，具体而言：。以下是我们在以下方面所做的 这种情况：aaabca

• 我们不会在根节点上插入新边。相反，我们 只需注意后缀已经在我们的 树。它结束于较长边缘的中间，但我们不是 为此感到困扰。我们只是让事情保持原样。[4,#]a
• 我们将活动点设置为 。这意味着活跃的 点现在位于根节点的传出边缘中间的某个位置，该根节点以 开头，具体来说，在该边缘上的位置 1 之后。我们 请注意，边仅由其第一个指定 字符。这就足够了，因为只能有一条边 从任何特定字符开始（在阅读整个描述后确认这是真的）。(root,'a',1)aa
• 我们也递增，所以在下一步的开始 这将是 2。remainder

观察：当我们找到需要插入的最终后缀时 已经存在于树中，树本身根本没有改变（我们只更新活动点和）。树 那么后缀树就不是精确表示到 当前位置，但它包含所有后缀（因为最后的 后缀是隐式包含的）。因此，除了更新 变量（都是固定长度的，所以这是 O（1）），这一步没有做任何工作。remaindera

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

因为余数是 2，我们需要插入两个 final 当前位置的后缀：和 。这主要是因为：abb

• 上一步中的后缀从未正确过 插入。所以它一直存在，自从我们取得进展以来 步，它现在已经从 .aaab
• 我们需要插入新的最终边缘 .b

在实践中，这意味着我们去活动点（它指向 在现在的边缘后面），然后插入 当前最后一个字符。但：再一次，事实证明是 也已经存在于同一边缘上。aabcabbb

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

• 将活动点更新为（相同的节点和边缘 和以前一样，但现在我们指向后面(root,'a',2)b)
• 将 递增到 3，因为我们仍然没有正确 插入了上一步的最后一条边，我们不插入 当前的最后一边。remainder

需要明确的是：我们必须在当前步骤中插入 和，但是 因为已经找到了，所以我们更新了活动点并做了 甚至没有尝试插入.为什么？因为if is in the tree，它的每个后缀（包括）都必须在树中， 太。也许只是隐含的，但它必须存在，因为 到目前为止，我们已经建造了这棵树。abbabbabb

我们通过递增 .这棵树是 自动更新为：#

因为余数是 3，所以我们必须插入 和 。活动点告诉我们在哪里结束，所以我们只需要 跳转到那里并插入 .确实，还没有，所以我们 拆分边并插入内部节点：abxbxxabxxabcabx

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

因此，我们处理并减少到 2。现在我们 需要插入下一个剩余的后缀 .但在我们这样做之前 我们需要更新活动点。拆分后的规则 并插入一条边，在下面称为规则 1，它适用于根（我们将进一步学习其他情况的规则 3 下文）。这是规则 1：abxremainderbxactive_node

从根插入后，

• active_node保持根
• active_edge设置为新后缀 we 的第一个字符 需要插入，即b
• active_length减少 1

因此，新的有效点三元组表示 下一个插入必须在边缘进行，在 1 个字符后面， 即在后面.我们可以在 O（1） 时间内确定插入点，并且 检查是否已经存在。如果它存在，我们 将结束当前步骤并保持一切原样。但是不存在，所以我们通过拆分边缘来插入它：(root,'b',1)bcabxbxx

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

但我们还有一件事需要做。我们称之为规则 2：

如果我们拆分一条边并插入一个新节点，如果这不是 在当前步骤中创建的第一个节点，我们连接之前 插入的节点和新节点通过一个特殊的指针，一个后缀 链接。我们稍后会看到为什么这是有用的。这是我们得到的， 后缀链接表示为虚线边：

我们仍然需要插入当前步骤的最后一个后缀。由于活动节点的组件已下降 到 0，则直接在根部进行最终插入。由于没有 根节点的传出边以 开头，我们插入一个新的 边缘：xactive_lengthx

正如我们所看到的，在当前步骤中，所有剩余的插入物都已完成。

我们通过设置 =7 继续执行步骤 7，该设置会像往常一样自动将下一个字符 ， 附加到所有叶子边缘。然后我们尝试插入新的final。 字符到活动点（根），并发现它在那里 已经。因此，我们在不插入任何内容的情况下结束当前步骤，并且 将活动点更新为 。#a(root,'a',1)

在步骤 8 中，=8，我们附加 ，如前所述，这仅 意味着我们将活动点更新为并增量而不做 其他任何东西，因为已经存在。但是，我们注意到（在 O（1） 时间内）活动点 现在位于边缘的末尾。我们通过将它重新设置为 来反映这一点。在这里，我用来指代 Edge 结束的内部节点。#b(root,'a',2)remainderb(node1,'\0x',0)node1ab

然后，在步骤 #=9 中，我们需要插入“c”，这将有助于我们 了解最后的诀窍：

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

与往常一样，更新会自动追加到叶边缘 然后我们转到活动点，看看是否可以插入“C”。它转过来 out 'c' 已经存在于该边上，因此我们将活动点设置为 ，increment 并且不执行任何其他操作。#c(node1,'c',1)remainder

现在在步骤 #=10 中，是 4，因此我们首先需要通过插入在活动位置插入（保留在 3 步前） 点。remainderabcdd

尝试在活动点插入会导致边分裂 O（1） 时间：d

从中启动拆分的 ，标记为 上面是红色的。这是最终规则，规则 3：active_node

从非根边中分割边后 节点，如果有 any，并将 重置为它指向的节点。如果有 没有后缀链接，我们将 设置为根目录。 并保持不变。active_nodeactive_nodeactive_nodeactive_edgeactive_length

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

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

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

我们观察到：后缀链接使我们能够重置活动点，因此我们 可以在 O（1） 努力处进行下一个剩余的插入。看 上图，以确认标签处的 Indeed 节点链接到 节点 at（其后缀），节点 at 链接到 。abbabcbc

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

因此，下一次插入发生在根节点的一个传出边缘 其标签以 开头 ： ，在第一个字符后面， 即在后面.这会导致另一个分裂：ccabxabcdc

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

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

有了这个，可以设置为 1，并且由于 根，我们使用规则 1 将活动点更新为 .这 表示当前步骤的最终插入是在根目录下插入单个：remainderactive_node(root,'d',0)d

这是最后一步，我们完成了。有最终的编号 不过，观察结果如下：

• 在每一步中，我们前进 1 个位置。这会自动 在 O（1） 时间内更新所有叶节点。#

• 但它不涉及 a） 以前剩余的任何后缀 步骤，以及 b） 当前步骤的最后一个字符。

• remainder告诉我们需要多少额外的插入物 做。这些插入物与最终后缀一一对应 在当前位置结束的字符串。我们考虑一个 在另一个之后进行插入。重要：每个插件都是 在 O（1） 时间内完成，因为活动点告诉我们确切的位置 go，我们只需要在活动状态处添加一个字符 点。为什么？因为其他字符是隐式包含的（否则活动点将不在它所在的位置）。#

• 在每次这样的插入之后，我们递减并遵循 后缀链接（如果有）。如果没有，我们去root（规则3）。如果我们 已经在根上，我们使用规则 1 修改活动点。在 无论如何，它只需要 O（1） 时间。remainder

• 如果在其中一个插入过程中，我们发现我们想要的字符 插入已经存在，我们什么都不做，结束 当前步骤，即使 >0。原因是任何 剩下的插入部分将是我们刚刚尝试插入的插入的后缀 做。因此，它们都隐含在当前树中。事实 >0 确保我们处理剩余的后缀 后。remainderremainder

• 如果算法末尾为 >0 怎么办？这将是 每当文本的末尾是发生的子字符串时，情况就 之前的某个地方。在这种情况下，我们必须附加一个额外的字符 在以前未发生过的字符串末尾。在 文学，通常美元符号用作符号 那。为什么这很重要？--> 如果稍后我们使用完成的后缀树来搜索后缀，则只有当匹配项以叶子结尾时，我们才必须接受匹配项。否则，我们会得到很多虚假匹配，因为树中隐式包含许多字符串，这些字符串不是主字符串的实际后缀。强制末尾为 0 实质上是确保所有后缀都以叶节点结尾的一种方式。但是，如果我们想使用树来搜索一般的子字符串，而不仅仅是主字符串的后缀，那么这最后一步确实不是必需的，正如下面 OP 的评论所建议的那样。remainder$remainder

• 那么整个算法的复杂度是多少呢？如果文本为 n 字符的长度，显然有 n 个步骤（如果我们添加 n+1 美元符号）。在每一步中，我们要么什么都不做（除了 更新变量），或者我们进行插入，每个插入取 O（1） 时间。Since 表示我们有多少次什么也没做 在前面的步骤中，并且对于我们制作的每个插入物都会递减 现在，我们做某事的总次数正好是 n（或 n+1）。因此，总复杂度为 O（n）。remainderremainder

• 但是，有一件小事我没有正确解释： 我们可能会遵循后缀链接，更新活动的 点，然后发现它的组件没有 与新的 .例如，考虑一种情况 喜欢这个：active_lengthactive_node

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

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

在特别糟糕的情况下，可能大到 ，也可以大到 n。这很可能会发生 要找到正确的活动点，我们不仅需要跳过一个 内部节点，但可能很多，在最坏的情况下最多 n。这样做 表示算法具有隐藏的 O（n²） 复杂度，因为 在每一步中一般为O（n），后调整 到活动节点后，后缀链接也可以是 O（n） 吗？active_lengthremainderremainder

不。原因是，如果确实我们必须调整活动点 （例如，如上所述，从绿色到蓝色），这将我们带到一个新节点， 有自己的后缀链接，并且会减少。如 我们沿着后缀链接链向下，我们制作剩余的插入物，只能 减少，以及我们可以进行的主动点调整次数 这条路不能比任何给定时间都大。由于 永远不能大于 ，并且 O（n） 不仅在每一步中，而且是增量的总和 在整个过程中所做的是 O（n） 同样，活动点调整的数量也受以下限制 O（n）。active_lengthactive_lengthactive_lengthactive_lengthremainderremainderremainder

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

使用的其他变量

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

让我们使用内部节点的概念 - 除根和叶之外的所有节点都是内部节点。

观察 1

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

观察2

如果在某个点大于或等于当前边 （） 的长度，则我们向下移动，直到严格大于 。active_lengthedge_lengthactive pointedge_lengthactive_length

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

第 1 条

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

1. 主动节点未更改
2. 有效长度递减
3. 活动边向右移动（到我们必须插入的下一个后缀的第一个字符）

第 2 条

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

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

第 3 条

从不是根节点的活动节点插入后，我们必须遵循后缀链接并将活动节点设置为它指向的节点。如果没有后缀链接，请将主动节点设置为根节点。无论哪种方式，活动边沿和活动长度保持不变。

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

最后，观察 3：

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

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

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

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

   

   • 添加最后一个字母 C 后：

   

2. 如果我们确实通过后缀链接连接节点：

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

   

   • 添加最后一个字母 C 后：

   

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

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

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

1. 爪哇岛
2. C++

希望这个“概述”与jogojapan的详细回答相结合，可以帮助某人实现自己的后缀树。

嗨，我已尝试在 ruby 中实现上述解释的实现，请查看。 它似乎工作正常。

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

它也出现在 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

@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提到的几个小问题比我预期的要复杂得多，需要非常小心地对待。我花了几天时间才让我的实现足够强大（我想）。问题和解决方案如下：

1. 以余数 > 0 结尾事实证明，这种情况也可能发生在展开步骤中，而不仅仅是整个算法的结束。发生这种情况时，我们可以保持余数、actnode、actedge 和 actlength 不变，结束当前的展开步骤，并通过继续折叠或展开来开始另一个步骤，具体取决于原始字符串中的下一个字符是否在当前路径上。

2. 跨越节点：当我们点击后缀链接时，更新活动点，然后发现其active_length组件不能很好地与新active_node配合使用。我们必须前进到正确的位置进行拆分或插入叶子。这个过程可能不是那么简单，因为在移动过程中，actlength 和 actedge 会一直变化，当您必须移回根节点时，actedge 和 actlength 可能会因为这些移动而出错。我们需要额外的变量来保留这些信息。

   

另外两个问题不知何故被@managonov指出了

3. 分裂可能会退化尝试拆分边时，有时您会发现拆分操作就在节点上。在这种情况下，我们只需要向该节点添加一个新叶子，将其视为标准的边拆分操作，这意味着后缀链接（如果有的话）应该相应地维护。

4. 隐藏的后缀链接还有另一种特殊情况，由问题 1 和问题 2 引起。有时我们需要跳过几个节点到正确的点进行拆分，如果我们通过比较剩余的字符串和路径标签来移动，我们可能会超过正确的点。在这种情况下，后缀链接将被无意中忽略（如果有的话）。这可以通过在前进时记住正确的点来避免。如果拆分节点已经存在，或者甚至在展开步骤中发生问题 1，则应保留后缀链接。

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

• 蟒

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

如果我的答案看起来多余，我深表歉意，但我最近实施了 Ukkonen 的算法，发现自己为此苦苦挣扎了好几天;我不得不通读有关该主题的多篇论文，以了解该算法某些核心方面的原因和方式。

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

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

请注意，我不是这方面的专家，因此以下部分可能包含不准确（或更糟）。如果您遇到任何情况，请随时编辑。

先决条件

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

（但是，我确实必须为流程添加一些基本叙述，因此开头可能确实感觉多余。

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

开放式叶节点及其局限性

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

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

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

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

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

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

我们能做的就是匹配我们能匹配的最长重复字符串，并计算它后面需要更新的后缀数量。这就是“余数”所代表的。

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

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

因此，继续使用前面的字符串 ABCXABCY 示例，我们“隐式”匹配重复的 ABC 部分，每次递增，这会导致余数为 3。然后我们遇到不重复的字符“Y”。在这里，我们将之前添加的 ABCX 拆分为 ABC->X 和 ABC->Y。然后我们从 3 递减到 2，因为我们已经处理了 ABC 分支。现在我们重复该操作，从根开始匹配最后 2 个字符 – BC – 以到达我们需要拆分的点，并且我们将 BCX 也拆分为 BC->X 和 BC->Y。 再次，我们递减到 1，然后重复该操作;直到 0.最后，我们还需要将当前字符 （Y） 本身添加到根目录。remainderremainderremainderremainder

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

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

“后缀链接”的概念

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

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

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

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

“活动点”的概念

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

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

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

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

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

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

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

您可以在下图中观察到 ABCABD 的匹配路由如何由边 AB 上的 2 个字符（从根）和边 CABDABCABD（从节点 4）上的 4 个字符组成，从而产生 6 个字符的“余数”。因此，我们当前的位置可以标识为活动节点 4、活动边缘 C、活动长度 4。

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

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

现在，棘手的部分，根据我的经验，可能会导致很多错误和头痛，并且在大多数来源中解释得很差，是处理后缀链接案例与重新扫描案例的区别。

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

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

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

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

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

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

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

使用“后缀链接”

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

在上面的例子中，由于“有效长度”是 4，所以我们使用后缀“ABAA”，从链接的节点 4 开始。但是在找到与后缀的第一个字符（“A”）相对应的边缘后，我们注意到我们的“有效长度”溢出了该边缘 3 个字符。因此，我们跳过整个边缘，跳到下一个节点，并按跳转消耗的字符递减“活动长度”。

然后，在我们找到下一个边“B”（对应于递减的后缀“BAA”）后，我们终于注意到边长大于剩余的“有效长度”3，这意味着我们找到了正确的位置。

请注意，此操作通常不称为“重新扫描”，尽管在我看来，它似乎直接等同于重新扫描，只是长度缩短且起点非根。

使用“重新扫描”

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

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

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

关于后缀链接和重新扫描的注意事项

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

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

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

4）这里描述的原始后缀链接只是可能的方法之一。例如，NJ Larsson等人将这种方法命名为面向节点的自上而下，并将其与面向节点的自下而上和两个面向边缘的变体进行了比较。不同的方法具有不同的典型和最坏情况的性能、要求、限制等，但总的来说，面向边缘的方法似乎是对原始方法的整体改进。