简单的英语中的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中实现了这个算法。 Gist在下面。它应该是无bug的。将其转储到一个js文件中， npm install chalk从相同位置npm install chalk ，然后使用node.js运行以查看一些丰富多彩的输出。在同一个Gist中有一个精简的版本，没有任何的调试代码。

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

以下是试图通过首先显示字符串简单（即不包含任何重复字符），然后将其扩展到完整算法的方式来描述Ukkonen算法的尝试。

首先是几个初步的陈述。

我们正在建设的东西基本上就像一个搜索引擎。所以有一个根节点，从它的边缘出来，导致新的节点，以及更远的边缘，等等
但是：与搜索特里不同，边缘标签不是单个字符。相反，每条边都使用一对整数来标记[from,to] 。这些是指向文本的指针。从这个意义上讲，每个边缘都带有一个任意长度的字符串标签，但只需要O（1）个空间（两个指针）。

基本原则

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

abc

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

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

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

这意味着什么：

现在我们进入第二个位置（在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来指定a 。这足够了，因为只有一个边缘从任何特定的字符开始（通过阅读整个描述后确认这是真的）。
我们也增加remainder ，所以在下一步开始的时候是2。

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

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

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

从前面的步骤后缀从来没有被正确插入。所以它一直存在，而且由于我们已经进步了一步，它现在已经从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是根（我们将在下面进一步学习其他情况，我们将学习规则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中 ，我们追加了b ，如前所述，这仅仅意味着我们更新活动点为(root,'a',2)并且增加remainder而不做其他任何事情，因为b已经存在。 但是，我们注意到（在O（1）时间）活动点现在在一个边的末尾。我们通过重新设置(node1,'\0x',0)来反映这一点。在这里，我使用node1来引用ab边缘结束的内部节点。

然后，在步骤# 9中 ，我们需要插入'c'，这将帮助我们理解最后的诀窍：

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

与往常一样， #更新将自动附加到叶边，我们到活动点看是否可以插入'c'。事实证明'c'已经存在于这个边缘，所以我们将活动点设置为(node1,'c',1) ，增加remainder ，不做任何事情。

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

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

active_node开始分割的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）的努力下完成下一个剩余的插入 。查看上面的图表，确认标签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 ，如果有的话跟随后缀链接。如果不是，我们就去根部（规则3）。如果我们已经在根目录，我们使用规则1来修改活动点。无论如何，它只需要O（1）次。
如果在其中一个插入过程中发现我们要插入的字符已经存在，那么即使remainder > 0，我们也不会做任何事情并结束当前步骤。原因是任何插入的东西都是我们试图做的后缀。因此它们都隐含在当前的树中。 remainder > 0的事实确保我们稍后处理剩下的后缀。
如果在算法的最后> 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边缘后面的位置。现在假设我们进行了必要的更新，现在按照规则3跟随后缀链接更新活动点。新的活动点是(green,'d',3) 。但是，从绿色节点出来的d边是de ，所以它只有2个字符。为了找到正确的活动点，我们显然需要沿着这个边缘到蓝色节点并重置为(blue,'f',1) 。

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

不。原因是，如果确实需要调整活动点（例如，从上面的绿色到蓝色），那么将带给我们一个具有自己的后缀链接的新节点，并且将减少active_length 。当我们跟随后缀链接，我们做剩下的插入， active_length只能减少，在任何时候我们可以做的active- 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

如果我们创建一个新的内部节点 或者从内部节点创建一个插入器，并且这不是当前步骤中的第一个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'已经在边缘。这是否意味着蓝色节点必须没有后缀链接？不，我们必须通过后缀链接连接蓝色节点和红色节点。为什么它是正确的？因为积极点的方法保证我们到一个正确的地方，即到下一个地方，我们必须处理一个较短的后缀插入。

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

Java的
C ++

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

我自己实现这个数据结构遇到了很多问题。最后我发现这篇文章，并设法实现它。一个很大的好处是，你有一个相当长的字符串一步一步的例子，所以你看看你应该做什么。请看看这篇文章，我会更乐意提供需要的提示。因为互联网上有好几个人，所以我很犹豫要不会再提出一个全面的解释。

我的直觉如下：

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

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

len（字符串）迭代之后，你有一个包含所有后缀的后缀树。

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

例如，假设你看过字符'abcabc'。活动点将代表树中对应于后缀“abc”的点。

活动点由（起点，第一，最后）表示。这意味着你现在正在树中，从节点原点开始，然后输入字符串[first：last]中的字符，

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

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

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

注3：标准化部分简单地节省检查活动点的时间。例如，假设你总是使用origin = 0，并且只是改变了第一个和最后一个。要检查活动点，您必须每次沿着所有中间节点后续跟随后缀树。通过记录最后一个节点的距离来缓存跟随这条路径的结果是有意义的。

你可以给你一个代码的例子，你是什么意思的“修复”边界变量？

健康警示：我也发现这个算法特别难以理解，所以请认识到这个直觉在所有重要的细节中可能是不正确的。

Thanks for the well explained tutorial by @jogojapan , I implemented the algorithm in Python.

A couple of minor problems mentioned by @jogojapan turns out to be more sophisticated than I have expected, and need to be treated very carefully. It cost me several days to get my implementation robust enough (I suppose). Problems and solutions are listed below:

End with Remainder > 0 It turns out this situation can also happen during the unfolding step , not just the end of the entire algorithm. When that happens, we can leave the remainder, actnode, actedge, and actlength unchanged , end the current unfolding step, and start another step by either keep folding or unfolding depending on if the next char in the original string is on the current path or not.
Leap Over Nodes: When we follow a suffix link, update the active point, and then find that its active_length component does not work well with the new active_node. We have to move forward to the right place to split, or insert a leaf. This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node , the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

The other two problems have somehow been pointed out by @managonov

Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly.
Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2 . Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

Finally, my implementation in Python is as follows:

蟒蛇

Tips: It includes a naive tree printing function in the code above, which is very important while debugging . It saved me a lot of time and is convenient for locating special cases.

Hi i have tried to implement the above explained implementation in ruby , please check it out. it seems to work fine.

the only difference in the implementation is that , i have tried to use the edge object instead of just using symbols.

its also present at 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 you brought awesome explanation and visualisation. But as @makagonov mentioned it's missing some rules regarding setting suffix links. It's visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word 'aabaaabb'. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

combining edges with nodes
using index pointers instead of references
breaks statements;
continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

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

简单的英语中的Ukkonen后缀树算法

基本原则

第一个扩展：简单的重复

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

在使用后缀树的string中最长的回文