Ukkonen的后缀树算法在普通英语中
这一点我感觉有点厚。 我花了好几天的时间试图完全包裹后缀树构造，但因为我没有数学背景，所以很多解释在我开始过度使用数学符号学的时候就避而远之。 最接近我找到的一个很好的解释是使用后缀树的快速字符串搜索，但是他掩盖了各个点，并且该算法的某些方面仍然不清楚。
我相信，Stack Overflow对这个算法的逐步解释对于除了我之外的许多其他人是无价的。
作为参考，这里是Ukkonen关于算法的论文：http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
到目前为止，我的基本理解是：
基本算法似乎是O（n2），正如在大多数解释中指出的那样，因为我们需要遍历所有前缀，那么我们需要遍历每个前缀的每个后缀。 由于使用了后缀指针技术，Ukkonen的算法显然是独一无二的，但我认为这是我无法理解的。
我也无法理解：
这里是完整的C＃源代码。 它不仅工作正常，而且支持自动封装，并呈现出更好看的输出文本图形。 源代码和示例输出位于：
https://gist.github.com/2373868
更新2017-11-04
多年后，我发现了后缀树的新用法，并在JavaScript中实现了该算法。 Gist在下面。 它应该没有缺陷。 将它转储到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之后）。
所以我们有一个初始树，看起来像这样：
这意味着什么：
现在我们进入第2位（在b之后）。 我们在每一步中的目标是将所有后缀插入到当前位置 。 我们这样做
a -edge扩展到ab b插入一个新边 在我们的表示中，这看起来像
它的意思是：
我们观察两件事：
ab的边缘表示与初始树中的边缘表示相同 ： [0,#] 。 它的含义已经自动更改，因为我们将当前位置#从1更新为2。 接下来，我们再次增加位置并通过将c添加到每个现有边并为新后缀c插入一个新边来更新树。
在我们的表示中，这看起来像
它的意思是：
我们观察到：
#自动更新，并且可以在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,' x',0) ，即active_node是根节点， active_edge被指定为空字符' x' ，并且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到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步中 ， # = 8，我们追加了b ，如前所见，这只意味着我们更新活动点为(root,'a',2)并且增加remainder而不做其他任何事情，因为b已经存在。 但是，我们注意到（在O（1）时间）活动点现在处于边的末尾。 我们通过将其重新设置为(node1,' x',0)来反映这一点。 在这里，我使用node1来引用ab边缘结束的内部节点。
然后，在步骤# = 9中 ，我们需要插入'c'，这将帮助我们理解最后的技巧：
第二个扩展：使用后缀链接
与往常一样， #更新追加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设置为根。 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开头的根节点的一个输出边缘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的事实可以确保我们稍后处理剩余的后缀。
如果在算法结束remainder > 0？ 只要文本的结尾是之前某处发生的子字符串，就会出现这种情况。 在这种情况下，我们必须在字符串的末尾附加一个额外的字符，这个字符以前没有出现过。 在文献中，美元符号$通常被用作符号。 为什么这很重要？ - >如果以后我们使用完整的后缀树来搜索后缀，那么只有当它们结束于叶子时，我们才能接受匹配。 否则，我们会得到大量虚假匹配，因为树中隐含的许多字符串不是主字符串的实际后缀。 在最后强制remainder为0基本上是确保所有后缀在叶节点处结束的一种方式。 但是，如果我们想要使用树来搜索一般的子字符串，而不仅仅是主字符串的后缀，那么最后一步确实不是必需的，正如OP的下面的评论所建议的那样。
那么整个算法的复杂性是什么？ 如果文本长度为n个字符，显然有n个步骤（如果我们添加美元符号，则n + 1）。 在每一步中，我们或者什么都不做（除了更新变量），或者我们做remainder插入，每次都花费O（1）次。 因为remainder表示在前面的步骤中我们没有做任何事情，并且对于我们现在制作的每个插入次数递减，所以我们做某事的总次数恰好是n（或n + 1）。 因此，总的复杂度是O（n）。
但是，有一件事我没有正确解释：可能发生的情况是，我们遵循后缀链接，更新活动点，然后发现其active_length组件不适用于新的active_node 。 例如，考虑这样的情况：
（虚线表示树的其余部分，虚线表示后缀链接。）
现在让活动点成为(red,'d',3) ，因此它指向defg边缘的f后面的位置。 现在假定我们进行了必要的更新，现在按照规则3跟随后缀链接更新活动点。新的活动点是(green,'d',3) 。 但是，从绿色节点出来的d边是de ，所以它只有2个字符。 为了找到正确的激活点，我们显然需要沿着那条边到达蓝色节点并重置为(blue,'f',1) 。
在特别糟糕的情况下， active_length可能与remainder一样大，可能与n一样大。 为了找到正确的活动点，我们不仅需要跳过一个内部节点，而且可能还有很多，最坏的情况下最多为n个。 这是否意味着该算法具有隐藏的O（n2）复杂度，因为在每一步中， remainder通常是O（n），在跟随后缀链接后对主动节点的后期调整也可能是O（n）？
不可以。原因是如果确实需要调整活动点（例如，从上面的绿色到蓝色），那么我们就会得到一个具有自己的后缀链接的新节点，并且active_length将会减少。 当我们跟随后缀链接链时，我们做了其余的插入， active_length只能减少，并且在任何给定时间，我们可以在路上做的活动点调整的数量不能大于active_length 。 由于active_length永远不会大于余remainder ，并且remainder不仅在每一步中都是O（n），而且在整个过程中remainder的总增量也是O（n），因此，活动点调整也受到O（n）的限制。
我尝试使用jogojapan的答案中给出的方法来实现后缀树，但由于用于规则的措辞，在某些情况下它不起作用。 此外，我提到过，没有人设法使用这种方法来实现绝对正确的后缀树。 下面我将对jogojapan的答案进行“概述”，并对规则进行一些修改。 我还会介绍一些我们忘记创建重要后缀链接的情况。
使用其他变量
让我们使用内部节点的概念 - 除根和叶子之外的所有节点都是内部节点 。
观察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后缀树的例子，如果我们在这种情况下添加后缀链接，并且我们不：
如果我们不通过后缀链接连接节点：
如果我们通过一个后缀链路连接节点：
似乎没有显着差异：在第二种情况下，还有两个后缀链接。 但是这些后缀链接是正确的，其中的一个 - 从蓝色节点到红色节点 - 对于我们的积极点的方法非常重要 。 问题是，如果我们不在这里放置后缀链接，稍后当我们向树添加一些新的字母时，由于Rule 3 ，我们可能会省略向树添加一些节点，因为根据它，如果存在没有后缀链接，那么我们必须把active_node放到根目录下。
当我们将最后一个字母添加到树中时，红色节点已经存在，然后我们从蓝色节点（边标为'c' ）进行插入。 由于有蓝色节点的插入，我们将其标记为需要后缀链接。 然后，依靠主动点方法， active node被设置为红色节点。 但是我们不会从红色节点插入，因为字母'c'已经在边缘。 这是否意味着蓝色节点必须没有后缀链接？ 不，我们必须通过后缀链接连接蓝色节点和红色节点。 为什么它是正确的？ 因为积极点方法保证我们到达正确的地方，即到下一个我们必须处理插入一个较短后缀的地方。
最后，这里是我的后缀树的实现：
希望这个“概述”结合jogojapan的详细答案将有助于某人实施他自己的后缀树。
我的直觉如下：
在主循环的k次迭代之后，您已经构建了一个后缀树，其中包含从前k个字符开始的完整字符串的所有后缀。
在开始时，这意味着后缀树包含一个表示整个字符串的单个根节点（这是从0开始的唯一后缀）。
在len（字符串）迭代之后，您有一个包含所有后缀的后缀树。
在循环过程中，键是活动点。 我的猜测是，这代表了后缀树中最深的点，它对应于字符串前k个字符的正确后缀。 （我认为正确的意思是后缀不能是整个字符串。）
例如，假设你看过字符'abcabc'。 活动点将表示树中对应于后缀'abc'的点。
活动点由（起点，第一个，最后一个）表示。 这意味着您目前正处于树中从节点原点开始，然后输入字符串[first：last]中的字符的位置，
当你添加一个新角色时，你会发现活动点是否仍然在现有树中。 如果是，那么你就完成了。 否则，您需要在活动点的后缀树中添加新节点，并回退到下一个最短匹配，然后再次检查。
注1：后缀指针给出了每个节点下一个最短匹配的链接。
注2：添加新节点并回退时，为新节点添加新后缀指针。 该后缀指针的目的地将是缩短的活动点处的节点。 此节点将已存在，或者在此回退循环的下一次迭代中创建。
注3：标准化部分简单地节省检查活动点的时间。 例如，假设你总是使用origin = 0，并且只是首先和最后一次改变。 要检查活动点，每次沿着所有中间节点都必须遵循后缀树。 通过仅记录最后一个节点的距离来缓存跟随此路径的结果是有意义的。
你能给出一个代码示例来说明你的“修复”边界变量的含义吗？
健康警告：我也发现这个算法特别难以理解，所以请认识到这种直觉在所有重要细节中可能是不正确的......
链接地址: http://www.djcxy.com/p/1039.html