Ukkonen's suffix tree algori

Ukkonen's suffix tree algorithm in plain English原文地址(最高票答案)
下文将尝试描述Ukkonen算法，我们首先会展示在字符串比较简单的情况下（即：字符串中没有重复字符时）Ukkonen算法会做些什么，然后扩展到完整的算法。

首先，一点初步的陈述。

我们正在构造的数据结构，跟搜索Trie有点类似，所以它将会有一个根节点，有边从根节点出发，指向根节点的子节点，然后也有边从这些子节点出发指向这些根节点子节点的子节点，如此一层层的下去直到叶节点。
但是：根搜索Trie不同的是，这里不再使用单个的字符来标记一条边，而是使用一对整数[from, to].它们是指向文本的指针。在这样的一个场景下，一条边携带了一个任意长度的字符串，但是只使用了O(1) 的空间（两根指针）。

基本原理

我将先展示如何给一个特别简单的字符串构造后缀树，一个没有重复字符的字符串：

abc

该算法从左到右一步一步的运行工作。字符串中的每一个字符都有一个步骤。每一个步骤可能涉及到多个单独的操作，但是我们会看到（最终观察结果）操作总数为O（n）。
所以，我们从左侧开始，并且首先通过创建一条从根节点root(在左边)到一个叶节点的边插入一个单独的字符a，并且将这条边标记为[0, #]. [0, #]这个标记所表达的意思是这条边被用来表示当前字符串从0位置开始到当前位置结束的子串。其中#表示的就是当前位置。在这一步，当前位置是1(即a的后面)。
所以我们有了一颗初始状态的树，它看起来长这样：

aOwIL.png

而它的意义是这样的：

SZH4k.png

现在我们前进到位置2（b的后面）。我们在算法的每一步的目标是：将到当前位置为止的所有后缀都插入到后缀树中。我们通过一下方式达到这一目的：
将当前a边扩展成为ab。
为后缀b插入一条新的边。
在我们当前的表示中看起来像这样：

onmqt.png

它的意义是这样的：

tchAx.png

我们观察到两件事：
现在表示ab的边跟它之前在初始树中的表示是一样的：[0, #]。 它所表达的意思被自动更新了因为我们将#的值从1更新到了2 。
每一条边占用的空间都是固定的，因为它们只包含两个指向文本的指针，不论它们所表示的子串有多长。
接下来我们再次更新当前位置，更新我们的树结构，给每一条已存在的边连接字符串c并且为新的后缀c插入一条新的边。
在我们的表示中看起来是这样的：

wCEdI.png

而它的意义是这样的：

UpUFw.png

我们可以观察到：
在每一个步骤完成的时候，我们的树都是正确包含所有后缀的的后缀树。
文本中有多少个字符串，就有多少个步骤。
在每一步中我们所要进行的步骤数量都是固定的，因为每一个已经存在的节点所表示的后缀都在#的值增加的时候被自动更新了，并且为最后的单字符后缀插入一条新边可以在O(1)的时间复杂度内完成。因此对于一个长度为n的字符串，我们只需要花费O(n)的时间。

第一次扩展：简单的重复

当然这个简化版的算法能够如此完美的运行仅仅是因为我们的字符串不包含任何重复字符，我们现在来看一个更真实的字符串：

abcabxabcd

这个字符串以前例中abc为开头，然后ab重复出现，后面跟随不重复的x, 然后abc重复出现，最后以d结尾。
步骤1到3: 在进行了前面三步之后我们从前例中获得了这样的一颗后缀树：

AclCh.png

步骤4: 我们将#移动到位置4，这将会把所有已经存在的节点隐式的更新成这样：

xhVMY.png

然后我们需要在根节点处插入当前节点的最后一个后缀a。
在此之前，我们先介绍两个新的变量（除#外的），它们当然一直都在我们的程序上下文中但是直到现在我们还没有用过它们：

active point, 这是一个三元组 (active_node, active_edge, active_length).
remainder, 一个用来表示我们还剩下多少个后缀需要插入的整数。
这两个变量的含义将会很快的变得清晰起来，但是现在我们仅需要了解：

在这个简单的abc示例里面，active point一直都是(root, null, 0), 即：active_node一直都是根节点，active_edge一直都是null, active_length一直都是0。这样造成的影响是我们每一步中我们插入的新边都是直接插在根节点上的新边。我们将会很快看到为什么我们需要这样的一个元组来表示这个信息。
在每一步开始之前remainder都总是被设置成1。这代表我们在每一步中需要插入的后缀数量都是1（总是最后那个字符）。
现在情况开始不一样了。当我们尝试将现在需要插入的最后那个字符a插入到根节点的时候，我们会发现现在已经有一条从节点出来的以a开头的边，具体来说：abca这条边。当遇到这种情况的时候我们这样做：
我们不在根节点插入新边[4,#]。相反，我们发现后缀a已经在树里面了。它在一条更长的边的中间结束，但我们不去管它，直接让它保持它现在的样子就行了。
我们将active point的值更新为(root, ‘a’, 1) 。这代表我们现在的活动点更新为了从根节点出发的一个以a开头的边的某处。根据active_length, 我们知道是在这条边开始的一个位置之后。我们发现具体的边是由其首个字符指定的。这样就足够了因为在某个节点处以某一个特定字符开始的边只可能有一条(通过完整的阅读本文你会发现这是正确的)。
我们还会将remainder的值增加一，所以在下一个步骤开始的时候remainder的值将会为2 。
观察：当我们需要插入的最后那个后缀已经出现在树里面的时候，树本身并没有被改变(我们只更新active point和remainder)。现在这棵树已经不再是到当前位置为止的后缀树的准确表示了，但是它的确包含了所有的后缀(因为最后需要插入的那个后缀a已经被隐式包含了)。因此，除了更新我们的变量之外（所有的这些变量都是固定长度的，时间复杂度是O(1)）， 我们在这一步没有做其他任何事情。
步骤5: 我们把代表当前位置的#更新为5，这将会自动把树结构更新为这样：

XL6bg.png

并且因为remainder是2，在当前位置我们需要插入两个后缀ab和b, 这是因为：
来源于上一个步骤的后缀a并没有被合适的插入. 所以它被留了下来，并且由于我们已经前进了一步，这个后缀已经由a扩展成了ab。
我们在这一步还需要插入新的后缀b。
在实践中这代表我们需要到active point(此时它指向现在是abcab的边的字符a后面)，插入当前需要插入的后缀b。但是：再一次，事实证明，b也已经在这条边上出现了。
所以，再一次，我们不去改变树的结构，我们仅仅：
把活动点的值更新为(root, ‘a’, 2)（跟之前同一个节点同一条边，但是我们现在指向了b的后面）。
将remainder的值更新为3因为来自前一步的边我们还没有插入，这一步的边也同样没有插入。
为了让解释更清楚一点：在这一步我们需要插入后缀ab和b, 但是因为ab已经在树里面了，所以我们只是更新了活动点并且连b都没有尝试去插入。为什么？因为如果ab在树里面，那么ab的所有后缀(包含b)肯定都已经在树里面了，或许它只是被隐式的包含在里面，但是它肯定在里面，这是由我们当前构造树的方式所决定的特性。
通过增加#的值我们前进到步骤6，现在树被自动更新成了这样：

bLLT9.png

因为当前remainder的值是3，我们需要插入abx, bx, x。活动点告诉了我们ab在哪里结束，所以我们只需要跳到那个位置插入x就行了。事实上，x并没有在那里，所以我们把边abcabx分裂开来并且插入一个中间节点：

6HYtR.png

这些边依然是用两个指针来指代所代表的后缀，所以分裂和插入一个中间节点可以在O(1)时间内完成。
所以我们现在已经处理完了abx而且将remainder的值减少到了2。现在我们需要插入下一个被遗留下来的后缀，bx。但是在此之前我们我们需要更新活动点。在这种情况下，即分裂一条边并插入一个新节点的情况下，更新活动点的规则，在下面被称作规则1，这条规则在任意活动点的active_node是root的时候都适用(我们在下面将讨论适用于其他情况的rule3)，这是规则1：
在根节点完插入一个新节点后：
active_node 依然还是root。
active_edge 被设置成了我们需要插入的下一个后缀的首个字符, 即 b
active_length 的值减一
因此，新的 活动点元组(root, ‘b’, 1)表示我们的下一次节点插入需要在边bcabx的一个位置之后。即b的后面。我们可以在O(1)的时间复杂度里面确定下一次插入的位置并且确认x是否已经存在。如果x已经存在了，我们需要停止当前的步骤并且让一切都保持现状。但是x并不存在，所以我们通过分裂边来将其插入：

YVvbJ.png

同样，这将花费O(1)的时间，然后我们将remainder更新为1并且根据规则1把active point更新为(root, ‘x’, 0)。
但是在这里我们还有一件事情需要做，我们将其称为规则2:
如果我们分裂了一条边并且插入了一个新的节点，并且这个节点不是在这个步骤中插入的第一个节点，我们将用一个特别的指针将前一个插入的节点与这个新节点连接起来，我们将这个连接称为Suffix link。
在接下来我们将会看到为什么我们要这么做。我们现在的树结构如下所示，Suffix link使用虚线表示：

zL9yl.png

我们还需要插入在这这一步骤中需要插入的最后一个后缀，x。因为活动点的active_length属性已经变成了0，新边的插入将直接在根节点进行。因为当前从根节点出发的边中没有以x开头的，我们将插入一条新边：

992gV.png

正如我们能够在图中看到的，在当前步骤中需要插入的所有节点都已经被正确放入了。
通过将#设置为7我们进行到步骤7，像往常一样，这将会自动在所有的叶节点的末尾添加字符新字符a。然后我们尝试在活动点插入最后需要插入的那个后缀a(在根节点), 然后会发现a已经被包含了。所以我们结束当前步骤，不插入任何新的边或者是节点，将active point 更新为(root, ‘a’, 1)。
在步骤8，#=8，我们连接了新字符b, 并且跟我们在前面看到的一样， 这代表我们会更新活动点为(root, ‘a’, 2)并将remainder增加一，因为b已经被包含了。但是，我们发现（在O(1)的时间复杂度内）现在活动点已经在这条边的结尾了。我们通过将活动点更新为(node1,’\0x’,0)来反映这一变化。在这里，我是用node1来表示边ab结束的那个节点。
然后，在步骤#=9, 我们需要插入字符c, 这将会帮助我们理解最后一个技巧：

第二次扩展：使用suffix links

跟以前一样，对#的更新自动在所有叶节点连接了字符c并且我们到活动点去判断是否能插入c。结果我们发现c已经存在了，所以我们除了将活动点设置为(node1, ‘c’, 1)，增加reaminder之外其他什么操作都不做。
现在我们到了第十步，remainder的值为4，所以我们首先需要通过在活动点插入d来插入后缀abcd(这可是在三个步骤之前遗留下来的)。
尝试在活动点插入d会导致一次O(1)时间复杂度的边分裂：

Rkdzd.png

active_node, 被分裂的边开始的节点，在上图中被标记成了红色。一下是最后的一条规则，规则3:
在一个非根节点的 active_node上完成了一次边的分裂后，如果存在一条从这个节点开始的suffix link, 我们将会跟随这条suffix link将active_node设置成suffix link指向的节点。如果没有suffix link, 那我们将active_node设置成根节点，active_edge和active_length保持不变。
所以现在活动点变成了(node2, ‘c’, 1), node2在下文中被标记成了红色。

0IS5C.png

既然abcd的插入已经完成了，我们将remainder减少为3并且开始考虑下一个需要被插入的后缀，bcd。Rule3已经将活动节点和活动边设置成了正确的值所以我们现在只需要简单的在活动点插入字符d就能完成bcd的插入。
这将导致一次边的分裂，并且由于规则2，我们必须创建一个从前一个插入的节点指向这个节点的suffix link：

DNVQO.png

我们观察到：suffix link能帮助我们更新活动点的值让我们能够在O(1)的时间内完成新边的插入。通过上图，我们可以确认ab的结尾被正确的链接到了它的后缀b, 并且节点abc被链接到了bc。
当前的步骤到现在并没有结束。remainder现在的值是2，并且我们需要跟随规则3去再次重置活动点。由于当前的active_node没有suffix link, 我们将active_node设置为root。现在活动点变成了(root, ‘c’, 1)。
因此，下一次插入出现在从根节点出发的一条label以c开头的边：cabxabcd上，在其第一个字符之后，即c的后面。这将导致下一次分裂：

wZ7Bj.png

并且由于这包含了新建一个中间节点，我们根据规则2设置一条来自上一个新中间节点的suffix link：

urgol.png

(我使用 Graphviz Dot来制图.新的suffix link导致了所有已存在的边的位置被改变了，所以请详细的确认上面只是添加了一个新的suffix link.)。
有了这个，remainder可以设置为1，并且由于active_node是root，我们使用规则1将活动点更新为（root，'d'，0）。 这意味着当前步骤的最终插入是在根处插入一个d：

TPxLe.png

这就是最后的一个步骤现在我们已经完成了。尽管如此，还是有很多最终观察：
在每一步中我们将#向前移动一个位置，这将会在O(1)的时间内更新所有的叶节点。
但这并不能处理由之前步骤遗留下来的后缀，也不能处理当前步骤的那个新的单字符后缀。
reaminder告诉了我们我们还需要插入多少后缀。这些插入与以当前位置＃结尾的字符串的最终后缀一一对应。我们一个接一个地考虑并进行插入。重要提示：每次插入都在O（1）时间内完成，因为活动点告诉我们确切的路线，我们只需要在活动点添加一个单独的字符。为什么？ 因为其他字符是隐式包含的（否则活动点不会在它所在的位置）。
在每一次插入完成后，我们减少remainder的值，如果有suffix link的话，跟随suffix link更新active_node,如果没有的话就回到根节点。如果我们已经在根节点了，就根据规则1来修改actiev_point的值。在任何情况下，这都只需要花费O(1)的时间。
如果在其中一个插入过程中发现我们要插入的字符已经存在，那么即使remainder> 0，我们也不会做任何事情并结束当前步骤。这是因为任何其他我们还需要插入的后缀都当会是这个被包含了的后缀的后缀。因此它们都被隐式包含了。remainder > 0的事实可以确保我们稍后处理剩余的后缀。
如果在所有的操作都已经完成之后reaminder>0会怎么样？只要文本的结尾是之前某处出现过的子字符串，就会出现这种情况。在这种情况下，我们必须在字符串的末尾附加一个额外的没有出现过的字符。在文献中，美元符号$通常被用来达到这个目的。为什么这很重要？ - >如果以后我们使用完整的后缀树来搜索后缀，那么只有当它们结束于叶子时，我们才能接受匹配。否则，我们会得到大量虚假匹配，因为树中隐含的许多字符串不是主字符串的实际后缀。在最后强制余数为0基本上是确保所有后缀在叶节点处结束的一种方式。但是，如果我们想要使用树来搜索一般的子字符串，而不仅仅是主字符串的后缀，那么最后一步确实不是必需的，正如OP的下面的评论所建议的那样。
那么整个算法的复杂度是多少？如果文本长度为n个字符，显然有n个步骤（如果我们添加美元符号，则n + 1）。在每一步中，我们或者什么都不做（除了更新变量），或者我们做余数插入，每次都花费O（1）时间。因为remainder表示了我们有多少次在一个步骤中什么都没有做，并且每一次插入新的字符的时候都会递减，我们做一些操作的总次数是n(n + 1)。因此，总的时间复杂度是O(n)。
然而，有一件事我没有正确解释：可能发生的情况是，我们遵循后缀链接，更新活动点，然后发现其active_length组件不适用于新的活动节点。 例如，考虑这样的情况：

7t0dg.png

（虚线表示树的其余部分，点线表示后缀链接。）
现在让活动点成为（红色，’d'，3），因此它指向defg边的f后面的位置。现在假设我们进行了必要的更新，现在按照规则3跟随后缀链接更新活动点。新的活动点是（绿色，'d'，3）。但是，从绿色节点出来的d边是de，所以它只有2个字符。为了找到正确的活动点，我们显然需要沿着那条边到达蓝色节点并重置为（蓝色，'f'，1）。
在特别糟糕的情况下，active_length可能与remainder一样大，而remainder可能会有n那么大。为了找到正确的活动点，我们可能不仅需要跳过一个内部节点，最坏的情况下甚至可以达到n个。在每一步中，remainder通常是O(n)，在跟随后缀链接后对主动节点的后期调整也可能是O(n), 这是否意味着该算法具有隐藏的O(n^2)复杂度？
不，原因是如果我们必须调整活动点（例如，如上所述从绿色变为蓝色），那么我们将会被带到具有其自己的后缀链接的新节点，并且active_length将减小。当我们跟随后缀链接链更新活动点时，我们做了插入，所以active_length只能减少，并且在任何给定时间，我们可以在路径上做的活动点调整的数量不能大于active_length。由于active_length永远不会大于remainder，并且remainder不仅在每一步中都是O(n)，而且在整个过程中remainder的增量的总和也是O(n)，因此， 活动点调整也受到O（n）的限制。