Ukkonen 的简明英语后缀树算法

此时我觉得有点厚。我花了几天时间试图完全用后缀树构建我的头，但由于我没有数学背景，因为他们开始过度使用数学符号系统时，许多解释都没有。最接近我发现的一个很好的解释是使用后缀树进行快速字符串搜索 ，但是他隐藏了各种点，并且算法的某些方面仍然不清楚。

在 Stack Overflow 中对此算法的逐步解释对于我以外的许多其他人来说都是非常宝贵的，我敢肯定。

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

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

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

基本算法似乎是 O（n ² ），正如我们在大多数解释中所指出的那样，因为我们需要遍历所有前缀，然后我们需要逐步遍历每个前缀的每个后缀。由于他使用的后缀指针技术，Ukkonen 的算法显然是独一无二的，尽管我认为这是我无法理解的。

我也很难理解：

确切地指定，使用和更改 “活动点” 的时间和方式
算法的典型化方面发生了什么
为什么我看到的实现需要 “修复” 他们正在使用的边界变量

这是完成的C＃源代码。它不仅工作正常，而且支持自动规范化，并提供更好看的输出文本图形。源代码和示例输出位于：

https://gist.github.com/2373868

更新 2017-11-04

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

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

答案

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

首先，一些初步的陈述。

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

基本原则

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

abc

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

所以，我们从左边开始，首先通过从根节点（左边）到叶子创建边缘，然后将其标记为[0,#]来插入单个字符a ，这意味着边表示子字符串从位置 0 开始到当前结束 。我使用符号#表示当前结束 ，它位于位置 1（紧跟在a之后）。

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

这意味着什么：

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

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

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

在此输入图像描述

它意味着：

我们观察到两件事：

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

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

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

它意味着：

我们观察到：

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

第一次扩展：简单重复

当然这很好用，因为我们的字符串不包含任何重复。我们现在看一个更现实的字符串：

abcabxabcd

它与前一个例子中的abc一样，然后重复ab ，然后是x ，然后重复abc ，接着是d 。

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

第 4 步：我们将#移到第 4位。这会隐式更新所有现有边缘：

我们需要在根目录下插入当前步骤的最后一个后缀a 。

在我们这样做之前，我们引入了另外两个变量 （除# ），当然这些变量一直存在，但到目前为止我们还没有使用它们：

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

这两者的确切含义很快就会清楚，但现在让我们说：

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

现在这将改变。当我们在根处插入当前的最后一个字符a时，我们注意到已经有一个以a开头的传出边，特别是： abca 。以下是我们在这种情况下所做的事情：

我们不在根节点插入新边[4,#] 。相反，我们只是注意到后缀a已经存在于我们的树中。它在较长边缘的中间结束，但我们并不为此烦恼。我们只是按照他们的方式离开。
我们将活动点设置为(root,'a',1) 。这意味着活动点现在位于根节点的出口边缘中间的某个位置，该边缘以a开头，特别是在该边缘上的位置 1 之后。我们注意到边缘仅由其第一个字符a指定。这就足够了，因为只有一个边缘以任何特定字符开头（在阅读整个描述后确认这是真的）。
我们也增加了remainder ，所以在下一步的开始它将是 2。

观察：当我们发现需要插入的最后一个后缀已经存在于树中时 ，树本身根本没有改变 （我们只更新活动点和remainder ）。树不再是后缀树的精确表示， 直到当前位置 ，但它包含所有后缀（因为最后的后缀a是隐式包含的）。因此，除了更新变量（全部是固定长度，因此这是 O（1））之外，在此步骤中没有完成任何工作 。

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

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

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

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

所以，我们再次不改变树。我们只是：

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

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

我们通过递增#继续第 6 步 。树自动更新为：

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

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

所以我们处理了abx并将remainder递减到 2. 现在我们需要插入下一个剩余的后缀bx 。但在我们这样做之前，我们需要更新活动点。在分割和插入边缘之后，此规则将在下面称为规则 1 ，并且只要active_node为 root，它就适用（我们将在下面的其他情况下学习规则 3）。这是规则 1：

从 root 插入后，
active_node仍然是 root
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'，这将有助于我们理解最后的技巧：

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

与往常一样， # update 会自动将c附加到叶子边缘，然后我们转到活动点以查看是否可以插入 “c”。事实证明，'c' 已存在于该边缘，因此我们将活动点设置为(node1,'c',1) ，增加remainder并且不执行任何其他操作。

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

尝试在活动点插入d会导致在 O（1）时间内进行边缘分割：

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

在从不是根节点的active_node分割边缘之后，我们遵循从该节点出来的后缀链接（如果有），并将active_node重置为它指向的节点。如果没有后缀链接，我们将active_node设置为 root。 active_edge和active_length保持不变。

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

由于abcd的插入已完成，我们将remainder减少到 3 并考虑当前步骤的下一个剩余后缀bcd 。规则 3 将活动点设置为正确的节点和边缘，因此插入bcd可以通过简单地在活动点插入其最终字符d来完成。

执行此操作会导致另一个边缘拆分，并且由于规则 2 ，我们必须创建从先前插入的节点到新节点的后缀链接：

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

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

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

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

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

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

这是最后一步，我们已经完成了。但是，有许多最终观察结果 ：

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

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

现在让活动点为(red,'d',3) ，因此它指向defg边缘上f后面的位置。现在假设我们进行了必要的更新，现在按照后缀链接更新活动点，根据规则 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 。由于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

如果从活动节点 = root插入后， 活动长度大于 0，则：
活动节点未更改
活动长度递减
活动边缘向右移动（到下一个后缀的第一个字符，我们必须插入）

规则 2

如果我们创建了一个新的内部节点 或 内部节点做出插入，这是不是在当前步骤的第一个这样的内部节点 ，然后我们通过一个后缀链接链接这一个以前的这种节点。

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

规则 3

从是不是根节点 活动节点插入之后，我们必须遵循的后缀链接和活动节点设置为它指向的节点。如果不存在一个链路后缀，设置活动节点到根节点 。无论哪种方式， 有效边沿和有效长度保持不变。

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

最后，观察 3：

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

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

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

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

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

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

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

感谢@jogojapan精心解释的教程，我在 Python 中实现了算法。

@jogojapan 提到的一些小问题比我预期的要复杂得多，需要非常小心对待。我花了几天的时间才能让我的实现足够强大 （我想）。问题和解决方案如下：

以Remainder > 0结束Remainder > 0结果发现这种情况也可能在展开步骤中发生，而不仅仅是整个算法的结束。当发生这种情况时，我们可以保持余数，actnode，actedge 和 actlength 不变，结束当前的展开步骤，并通过保持折叠或展开来开始另一步，具体取决于原始字符串中的下一个字符是否在当前路径上或不。
跳过节点：当我们遵循后缀链接时，更新活动点，然后发现其 active_length 组件与新的 active_node 不兼容。我们必须向前移动到正确的地方裂开，或插入叶。这个过程可能不是那么简单 ，因为移动 actlength 期间 actedge 不断变化一路，当你不得不搬回到根节点的actedge和actlength可能因为这些举动是错误的 。我们需要额外的变量来保存这些信息。

@managonov以某种方式指出了另外两个问题

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

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

蟒蛇

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