Ukkonen 的后缀树算法的清晰解释 已翻译 100%

基本原理

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

abc

这个算法工作的步骤，从左到右。字符串的每个字符都有一个步骤。每一步都可能涉及到多个个体的操作,但是我们将会看到(见结尾最后的观察)的总数量操作是O(n)。

所以我们从左开始，第一次插入单个字符“a“创建一个从根节点(在左边)到一个叶节点的边，和作为[0,#)的标签，这意味着边代表了子串在位置0开始，结束在当前的结尾。我使用符号#来表示当前末尾，这是在位置1(a之后的右边)。

因此，我们拥有一棵起始树，这棵树看起来如下：

而其意义如下：

•  扩展已存在边a为ab
•  插入一条新边b

我们看到了两点：

• ab边的图示与它在起始树:[0,#]边的图示是相同的。它的意义却已经自动更改了，因为我们把当前的位置#从1更改到2。

• 每条边使用的空间复杂度为O(1),因为无论边代表多少个字符 ，它都是由指向文本里的两个指针组成。

•   这棵树是经过上面的每个步骤后至当前位置的正确的后缀树。

•   步骤数目与文本中包含的字符一样多。

•   每个步骤的工作量是O(1)，因为所有已经存在的边都是增加#来自动更改的，而且为最后一个字符插入一条新边的时间复杂度为  O(1)。因此对一个长度为n的字符串来说，只需要O(n)时间复杂度。

第一次扩展：简单的重复

当然，后缀树表示的如此良好只是因为我们的字符串没有包含任何重复。现在我们看一个更真实的字符串：

abcabxabcd

步骤1到3：经过了前三个步骤后，我们拥有了前面例子的那棵树：

步骤4：我们移动#到位置4。这隐含地更改所有已经存在的边为如下：

•    活动点，它是一个三元组（活动节点，活动边，活动长度）

•    剩余后缀数，它是一个整数，来说明我们需要插入多少个新的后缀。

•  在简单的abc例子里，活动点总是(root,'0x',0),也就是说，活动节点是根节点，活动边是由空字符'0x'指定的边，活动长度是0。这么做的结果是我们在每一步骤里插入的一条新边是作为新创建的边插入到根节点。不久我们就会明白为什么需要三元组表示这条信息。
•  在每个步骤开始时剩余后缀数总是设置为1。它的意义是我们主动插入到每一步骤末尾的后缀数目是1（总是最后一个字符）。
  

• 我们不向根节点插入一条新边[4,#]。相反，我们只是注意到后缀a已经在我们的树里。它终止在更长的边的中间位置，不过这么做我们并不疑惑，我们还是保留它们原来的样子。
  

• 我们设置活动点为(root,'a',1)。这意味着活动点现在是在根节点的以a开始的向外的边的中间某个位置，具体地指这条边的位置1之后。我们注意到这条边只是由它的首个字符a来声明的。这就足够了，因为以一个特定的字符开始的只有一条边（通读整个文档之后可以确定这是真的）。
  

• 我们还增加了剩余后缀数， 那么在下一步骤开始的时候，剩余后缀数为2。

注意：当发现我们需要插入的最终后缀已经存在在这棵树里的时候，这棵树本身根本就没有改变（我们只是修改了活动节点和剩余后缀数）。那么这棵树就不再是能准确的表示至当前位置的后缀树了，不过它包含了所有的后缀（因为最终的后缀a隐含地包含了）。因此，除了修改变量外（所有这些变量都是定长的，因此空间复杂度是 O(1)），在这一步里没有做其他工作。

步骤5：我们修改当前的位置#为5。这将自动地如下更新这棵树：

• 前一步骤的a后缀从来都没有真正地插入。因此它保留下来，然而由于我们已经向前走了一步，它现在由a延长为ab。

•  还有，我们需要插入新的最终边b。

•  修改活动点为(root,'a',2)(是与前面相同的节点和边，只不过现在我们指向到b之后)

•  增加剩余后缀数为3 ，因为我们仍然不能插入前一个步骤的最终边，同时我们也不能插入当前的最终边

为了清晰地说明：我们需要在当前的步骤里插入ab和b，不过由于ab已经找到，所以我们修改了活动点，而且甚至不试图插入b。为什么？因为如果ab处于这棵树里，那么它的每个后缀（包括b)也一定在这棵树里。也许仅仅是隐含性的，不过它一定在这棵树里，因为这是我们迄今为止建立这棵树所采用的方法。

我们增加#而前进到步骤6。这棵树自动修改为：

由于剩余后缀数是3 ，我们不得不增加abx,bx和x。活动点告诉我们ab结束在哪儿，因此我们仅仅需要跳过这儿，然后插入x。x确实还不在这棵树里，因此我们分割abcabx边，插入一个内部节点：

这时我们处理了abx,并且把剩余后缀数减为2。现在我们需要插入下一个剩余后缀bx。但是在我们做这些之前，我们需要修改活动节点。分割并插入一条边遵循的规则称作规则1，如下，而且它适用于活动节点是根节点的情况（针对下面后续的其他情况，我们将要了解规则3）。规则1如下：

向根节点插入遵循：

• 活动节点保留为根节点
• 设置活动边为我们需要插入的新后缀的第一个字符，也就是b。
• 活动长度减1

因此，新的活动节点三元组(root,'b',1)表明要做的下一个插入在bcabx边，第一个字符之后，即b之后。我们可以确定插入点的时间复杂度为 O(1)，并且检查x是否已经出现在树里。如果它出现在这条边里，我们将结束当前的步骤，保持一切为原样。然而如果x没有出现在这条边里，那么我们分割这条边而插入它：

不过还有一件事情我们必须做。我们称它为规则2：

如果我们分割一条边并插入新的节点，而且如果它不是在当前步骤里创建的第一个节点
的话，我们通过特殊的指针，即后缀连接，把 以前插入的节点和新增的节点连接起来
。后面我们将明白为什么这么做是有用的。这儿我们要明白：后缀连接表示为虚线边：

正如你所能看到的，在当前的步骤里插入了所有剩余的后缀。

我们设置#=7而前进到步骤7，这将像往常一样自动添加下一个字符a到所有的叶子边上。然后我们试图插入新的最终字符到活动节点（根节点），然后发现它已经存在在这棵树里了。因此我们结束当前的步骤，不插入任何边，并且修改活动点位(root,'a',1)。

设置#=8进入步骤8,我们添加b,像以前所看到的，这仅仅意味着我们修改活动点位(root,'a',2) ,而且不需要做其他事情就增加剩余后缀数。因为b已经出现在这棵树里。然而我们（在 O(1)时间复杂度里）注意到活动节点现在是一条边的结尾。我们通过重置活动节点位(node1,'\0x',0)来体现这个。这儿，我们用node1来指ab边结束的哪个内部节点。

接着设置#=9进入步骤9，我们需要插入'c',这将有助于我们理解的最后一条技巧：