普通英语的 Ukkonen 后缀树算法

在这一点上我感觉有点浓。我花了几天的时间试图完全围绕后缀树的构造,但是由于我没有数学背景,因此许多解释使我难以理解,因为它们开始过度使用数学符号系统。我发现的最接近很好的解释是带有后缀树的快速字符串搜索 ,但是他掩盖了各个要点,并且算法的某些方面仍然不清楚。

我敢肯定,在堆栈溢出上对此算法的分步说明对我以外的其他许多人来说都是无价的。

作为参考,这里是有关算法的 Ukkonen 论文: http : //www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

到目前为止,我的基本了解:

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

正如大多数解释中所指出的那样,基本算法似乎是 O(n 2 ),因为我们需要逐步处理所有前缀,然后需要逐步处理每个前缀的每个后缀。 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 算法的尝试,首先显示字符串简单时(即不包含任何重复字符),然后将其扩展到完整算法。

首先,一些初步陈述。

  1. 我们正在构建的基本上就像一个搜索树。因此,存在一个根节点,边缘向外延伸到新节点,进一步的边缘向外延伸,依此类推

  2. 但是 :与搜索 Trie 不同,边缘标签不是单个字符。而是使用一对整数[from,to]标记每个边缘。这些是文本的指针。从这个意义上讲,每个边都带有任意长度的字符串标签,但仅占用 O(1)空间(两个指针)。

基本原则

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

abc

该算法从左到右逐步执行字符串的每个字符都有一个步骤 。每个步骤可能涉及多个操作,但是我们将看到(请参阅最后的最终观察结果)操作总数为 O(n)。

因此,我们从左侧开始,首先通过创建从根节点(在左侧)到叶的边来插入单个字符a ,并将其标记为[0,#] ,这意味着该边代表子字符串从位置 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 ,我们需要插入当前位置的两个后缀: abb 。这主要是因为:

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

实际上,这意味着我们转到活动点(在当前abcab边上指向a后面),并插入当前的最终字符b但是:同样,事实证明b也已经存在于同一边缘上。

因此,再次,我们不更改树。我们简单地:

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

需要明确的是:我们必须在当前步骤中插入abb ,但是因为已经找到ab ,所以我们更新了活动点,甚至没有尝试插入b 。为什么?因为如果ab在树中,则它的每个后缀 (包括b )也必须在树中。也许只是隐式地存在 ,但是必须存在,因为到目前为止我们构建树的方式。

我们通过增加#进入步骤 6 。该树将自动更新为:

因为remainder是 3 ,所以我们必须插入abxbxx 。活动点告诉我们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,'\0x',0)来反映这一点。在这里,我使用node1来指代ab边缘结束的内部节点。

然后,在步骤# = 9 中 ,我们需要插入 “c”,这将帮助我们理解最终的技巧:

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

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

现在,在步骤# = 10 中remainder为 4,因此我们首先需要通过在活动点插入d来插入abcd (从 3 个步骤之前保留)。

尝试在活动点插入d会导致 O(1)时间的边裂:

从上方开始拆分的active_node上面用红色标记。这是最终规则, 规则 3:

从不是根节点的active_node拆分一条边后,我们跟随从该节点出来的后缀链接(如果有的话),然后将active_node重置为active_node指向的节点。如果没有后缀链接,我们将active_node设置为根。 active_edgeactive_length保持不变。

因此,活动点现在是(node2,'c',1) ,并且node2在下面用红色标记:

由于完成了abcd的插入,因此我们将remainder减为 3 并考虑当前步骤的下一个剩余后缀bcd 。规则 3 已将活动点设置为恰好位于正确的节点和边缘,因此只需在活动点插入其最终字符d即可插入bcd

这样做会导致另一个边缘分裂,并且由于规则 2 ,我们必须创建一个从先前插入的节点到新节点的后缀链接:

我们观察到:后缀链接使我们能够重置活动点,因此我们可以以 O(1)的努力进行下一个剩余的插入 。查看上图以确认标签ab上的节点确实链接到b上的节点(后缀),并且abc上的节点链接到bc

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

因此,下一次插入发生在根节点的标签以ccabxabcd开头的根节点的一个输出边缘上,在第一个字符之后,即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 怎么办?每当文本的结尾是之前某个位置出现的子字符串时,情况就是如此。在这种情况下,我们必须在之前未出现过的字符串的末尾附加一个额外的字符。在文献中,通常使用美元符号$来表示。 为什么这么重要? -> 如果以后我们使用完整的后缀树搜索后缀,则仅当它们以 leaf 结尾时 ,我们才必须接受它们。否则,我们将得到很多虚假匹配,因为树中隐含了 许多字符串, 这些字符串不是主字符串的实际后缀。将remainder强制为结尾实际上是一种确保所有后缀都在叶节点结尾的方法。 但是,如果我们要使用树来搜索常规子字符串 ,而不仅仅是主字符串的后缀 ,则实际上并不需要最后一步,如以下 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(n 2 )复杂性,因为在每一步中, 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_node; active_edge; active_length),显示我们必须从哪里开始插入新的后缀。
  2. 剩余数 - 显示必须显式添加的后缀数。例如,如果我们的单词是 “abcaabca”,而 remainder = 3,则意味着我们必须处理 3 个后缀: bcacaa

让我们使用内部节点的概念 - 除了叶子都是内部节点之外的所有节点

观察 1

当发现我们需要插入的最后一个后缀已经存在于树中时,树本身根本不会改变(我们只更新active pointremainder )。

观察 2

如果在某个点上active_length大于或等于当前 edge 的长度( edge_length ), edge_length active point向下移动,直到edge_length严格大于active_length

现在,让我们重新定义规则:

规则 1

如果从活动节点 = root插入后, 活动长度大于 0,则:

  1. 活动节点未更改
  2. 有效长度递减
  3. 活动边右移(到我们必须插入的下一个后缀的第一个字符)

规则二

如果我们创建一个新的内部节点 从一个内部节点插入一个插入器,而这不是当前步骤中的第一个SUCH 内部节点 ,则可以通过后缀链接将先前的SUCH节点与THIS 链接起来

Rule 2定义不同于 jogojapan',因为这里我们不仅考虑了新创建的内部节点,而且还考虑了从中插入的内部节点。

规则三

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

Rule 3此定义中,我们还考虑了叶节点(不仅是分割节点)的插入。

最后,观察 3:

当我们要添加到树上的符号已经在边缘上时,根据Observation 1 ,我们仅更新active pointremainder ,而使树保持不变。 但是,如果有一个内部节点标记为需要后缀链接 ,则必须通过后缀链接将该节点与当前active node连接。

让我们看一下cdddcdc的后缀树的示例,如果我们在这种情况下添加了后缀链接,而没有这样做的话:

  1. 如果我们通过后缀链接连接节点:

    • 在添加最后一个字母c 之前

    • 添加最后一个字母c 后

  2. 如果我们确实通过后缀链接连接节点:

    • 在添加最后一个字母c 之前

    • 添加最后一个字母c 后

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

当我们将最后一个字母添加到树中时,红色节点已经存在,然后再从蓝色节点进行插入(边缘标记为'c' )。由于蓝色节点有插入物,因此我们将其标记为需要后缀链接 。然后,依靠活动点方法,将active node设置为红色节点。但是,由于字母'c'已经在边缘,因此我们不会从红色节点插入。这是否意味着蓝色节点必须不带后缀链接?不,我们必须通过后缀链接将蓝色节点与红色节点相连。为什么正确?因为主动点方法保证了我们可以到达一个正确的位置,即到达必须处理较短后缀的下一个位置。

最后,这是我对后缀树的实现:

  1. 爪哇
  2. C ++

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

感谢@jogojapan精心解释的教程,我用 Python 实现了该算法。

@jogojapan 提到的几个小问题比我预期的要复杂得多,需要非常仔细地对待。我花了几天的时间才能使我的实现足够强大 (我想)。问题和解决方案如下:

  1. Remainder > 0结尾事实证明,这种情况也可能在展开步骤中发生,而不仅仅是整个算法的结束。发生这种情况时,我们可以使其余部分,actnode,actedge 和 actlength 保持不变 ,结束当前的展开步骤,并根据原始字符串中的下一个 char 是否在当前路径上,通过继续折叠还是展开来开始下一步。不。

  2. 跨越节点:当我们跟随一个后缀链接时,更新活动点,然后发现其 active_length 组件不能与新的 active_node 很好地配合。我们必须向前移动到正确的位置才能拆分或插入叶子。这个过程可能不是那么简单,因为在移动过程中,actlength 和 actedge 一直在变化,当您不得不移回根节点时 ,由于这些移动, actedgeactlength可能是错误的。我们需要其他变量来保留该信息。

    在此处输入图片说明

@managonov指出了其他两个问题

  1. 拆分可能会退化当尝试拆分边缘时,有时您会发现拆分操作正好在节点上。在这种情况下,我们只需要向该节点添加一个新叶子,将其作为标准的边缘拆分操作即可,这意味着后缀链接(如果有的话)应进行相应维护。

  2. 隐藏的后缀链接 问题 1问题 2还有另一种特殊情况。有时我们需要跳过几个节点到正确的点进行拆分,如果我们通过比较其余字符串和路径标签来移动,则可能会超过正确的点。在这种情况下,后缀链接将被无意忽略,如果有的话。通过记住前进时的正确点可以避免这种情况。如果拆分节点已经存在,或者即使问题 1在展开步骤中发生,则应保留后缀链接。

最后,我在Python 中的实现如下:

提示: 上面的代码中包含朴素树打印功能,这在调试时非常重要 。它为我节省了很多时间,并且方便查找特殊情况。

道歉,如果我的回答似乎多余,但我最近实施了 Ukkonen 的算法,发现自己已经为此苦苦挣扎了好几天。我必须通读有关该主题的多篇论文,以了解该算法某些核心方面的原因和方式。

我发现先前答案的 “规则” 方法无助于理解其根本原因 ,因此,我在下文中仅着重于语用学方面的内容。如果您像我一样努力遵循其他说明,也许我的补充说明会为您 “点击”。

我在这里发布了 C#实现: https//github.com/baratgabor/SuffixTree

请注意,我不是该主题的专家,因此以下各节可能包含错误(或更糟)。如果遇到任何问题,请随时进行编辑。

先决条件

以下说明的起点假定您熟悉后缀树的内容和用法,以及 Ukkonen 算法的特征,例如,如何从头到尾逐个字符地扩展后缀树。基本上,我假设您已经阅读了其他一些说明。

(但是,我确实必须为流程添加一些基本的叙述,因此开始时确实可能感觉很多余。)

最有趣的部分是对使用后缀链接和从根目录重新扫描之间的区别解释 。这就是我在实施过程中遇到的许多错误和头痛的原因。

开放式叶节点及其局限性

我确定您已经知道最基本的 “技巧” 是意识到我们可以只保留后缀 “open” 的结尾,即引用字符串的当前长度,而不是将结尾设置为静态值。这样,当我们添加其他字符时,这些字符将隐式添加到所有后缀标签中,而无需访问和更新所有后缀。

但是,由于明显的原因,后缀的这种开放结尾仅适用于表示字符串结尾的节点,即树结构中的叶节点。我们在树上执行的分支操作(添加新的分支节点和叶节点)不会自动传播到所需的任何地方。

重复的子字符串不会显式地出现在树中,这很可能是基本的,因此无需赘述,因为由于树是重复的,所以树中已经包含了这些子字符串。但是,当重复子字符串由于遇到非重复字符而结束时,我们需要在该点创建一个分支以表示从该点开始的分支。

例如,对于字符串“ABCXABCY” (请参见下文),需要将XY的分支添加到三个不同的后缀ABCBCC 中 ;否则,它将不是有效的后缀树,并且通过从根向下匹配字符,我们无法找到字符串的所有子字符串。

再次强调一下–我们对树中后缀执行的任何操作也必须由其连续后缀(例如,ABC> BC> C)反映出来,否则它们不再是有效的后缀。

在后缀中重复分支

但是,即使我们接受必须进行这些手动更新,我们如何知道需要更新多少个后缀?因为,当我们添加重复字符A (以及连续的其余重复字符)时,我们还不知道何时何地需要将后缀分成两个分支。仅当我们遇到第一个非重复字符时才确定需要拆分,在这种情况下为Y (而不是树中已经存在的X )。

我们可以做的是匹配最长的重复字符串,并计算以后需要更新的后缀个数。这就是“剩余”的意思。

“剩余” 和 “重新扫描” 的概念

变量remainder告诉我们隐式添加了多少个重复字符,没有分支;也就是说,一旦发现无法匹配的第一个字符,我们需要访问多少个后缀以重复分支操作。这实质上等于从树的根开始我们在树中有多少个 “深” 字符。

因此,与字符串ABCXABCY的前面的示例相同 ,我们 “隐式” 匹配重复的ABC部分,每次增加remainder ,结果是余数 3。然后我们遇到了非重复字符“Y” 。在这里,我们将先前添加的ABCX分为ABC- > XABC- > Y。然后,将remainder从 3 减少到 2,因为我们已经处理了ABC分支。现在,我们通过从根开始匹配最后两个字符BC到需要拆分的点来重复该操作,然后将BCX也拆分为BC- > XBC- > Y。再次,我们将remainder减为 1,然后重复该操作;直到remainder为 0。最后,我们还需要将当前字符( Y )本身也添加到根中。

该操作从根开始连续跟随后缀,直到我们需要进行操作的点,这在 Ukkonen 的算法中称为“重新扫描” ,通常这是算法中最昂贵的部分。想象一个更长的字符串,您可能需要跨数十个节点(我们将在后面讨论)在多个节点上 “重新扫描” 长子字符串。

作为解决方案,我们介绍了所谓的“后缀链接”

“后缀链接” 的概念

后缀链接基本上指向我们通常必须“重新扫描”的位置,因此,代替昂贵的重新扫描操作,我们可以简单地跳至链接位置,进行工作,跳至下一个链接位置,然后重复–直到出现没有更多职位可更新。

当然,一个大问题是如何添加这些链接。现有的答案是,我们可以在插入新的分支节点时添加链接,这利用了以下事实:在树的每个扩展中,自然需要按照确切的顺序一个接一个地创建分支节点,我们需要将它们链接在一起。虽然,我们必须从最后创建的分支节点(最长的后缀)链接到先前创建的分支节点,所以我们需要缓存我们创建的最后一个分支节点,将其链接到我们创建的下一个分支节点,并缓存新创建的分支节点。

结果是实际上我们通常没有后缀链接,因为给定的分支节点是刚刚创建的。在这些情况下,我们必须从根本上退回到前述的“重新扫描” 。这就是为什么在插入后会提示您使用后缀链接或跳转到根目录的原因。

(或者,如果您将父指针存储在节点中,则可以尝试跟随父节点,检查它们是否具有链接,并使用该链接。我发现很少提及该链接 ,但是后缀链接用法并未提及在石集,有多种可能的方法,如果你了解底层机制可以实现一个适合您的需求是最好的。)

“活跃点” 的概念

到目前为止,我们讨论了用于构建树的多种有效工具,并且模糊地涉及遍历多个边缘和节点,但是尚未探讨相应的后果和复杂性。

前面解释的“剩余”概念对于跟踪我们在树中的位置很有用,但是我们必须意识到它没有存储足够的信息。

首先,我们总是驻留在节点的特定边缘上,因此我们需要存储边缘信息。我们称其为“主动边缘”

其次,即使添加了边缘信息后,我们仍然没有办法确定一个位置,在树越往下,而不是直接连接到根节点 。因此,我们还需要存储该节点。我们将此称为“活动节点”

最后,我们可以注意到, “余数”不足以标识未直接连接到根的边上的位置,因为“余数”是整条路线的长度。而且我们可能不想打扰记住和减去前一条边的长度。因此,我们需要一种表示形式,基本上是当前边缘上的其余部分 。这就是我们所说的“活动长度”

这导致了我们所谓的“活动点” –三个变量的包,其中包含我们需要维护的有关树中位置的所有信息:

Active Point = (Active Node, Active Edge, Active Length)

您可以在下图上观察到, ABCABD的匹配路由如何由边缘AB上的 2 个字符(来自root ),以及边缘CABDABCABD上的 4 个字符(来自节点 4)组成 - 导致“剩余”为 6 个字符。因此,我们当前的位置可以标识为活动节点 4,活动边缘 C,活动长度 4

剩余点和活动点

“活动点” 的另一个重要作用是,它为我们的算法提供了一个抽象层,这意味着我们算法的各个部分都可以在“活动点” 上进行工作 ,而不管该活动点是在根中还是在其他任何地方。这使得在我们的算法中以简洁明了的方式轻松实现后缀链接的使用。

重新扫描与使用后缀链接的区别

现在,棘手的部分(根据我的经验)会导致大量的错误和头痛,并且在大多数来源中都没有很好地解释,这是处理后缀链接案例与重新扫描案例的区别。

考虑以下字符串'AAAABAAAABAAC' 的示例:

剩余在多个边缘

您可以在上面观察到“余数” 7 对应于来自根的字符总和,而“活动长度” 4 对应于来自活动节点的活动边缘的匹配字符之和。

现在,在活动点执行分支操作之后,活动节点可能包含后缀链接,也可能不包含后缀链接。

如果存在后缀链接:我们只需要处理“活动长度”部分。 “余数”是无关紧要的,因为我们通过后缀链接跳转到的节点已经隐式编码了正确的 “余数” ,这仅仅是因为它位于所在的树中。

如果不存在后缀链接:我们需要从零 / 根开始“重新扫描” ,这意味着从头开始处理整个后缀。为此,我们必须使用整个“剩余”作为重新扫描的基础。

有和没有后缀链接的处理示例比较

考虑上面的示例的下一步会发生什么。让我们比较一下如何获得相同的结果(即移至下一个要处理的后缀)(带或不带后缀链接)。

使用“后缀链接”

通过后缀链接到达连续的后缀

请注意,如果我们使用后缀链接,我们将自动位于 “正确的位置”。由于“有效长度”可能与新职位 “不兼容”,因此通常并非严格如此。

在上述情况下,由于“有效长度”为 4,所以我们从链接的节点 4 开始使用后缀 “ ABAA” 。但是在找到与后缀的第一个字符( 'A' ),我们注意到我们的“有效长度” 在此边沿溢出了 3 个字符。因此,我们跳过整个边缘,移至下一个节点,并根据跳转所消耗的字符来减少“活动长度”

然后,在找到与后缀'BAA ' 相对应的下一个边缘'B' 之后 ,我们最终注意到边缘长度大于剩余的“有效长度” 3,这意味着我们找到了正确的位置。

请注意,似乎此操作通常不被称为 “重新扫描”,即使在我看来,这与重新扫描直接等效,只是缩短了长度且没有根目录起始点。

使用“重新扫描”

通过重新扫描达到连续的后缀

请注意,如果我们使用传统的 “重新扫描” 操作(在这里假装没有后缀链接),那么我们将从树的顶部开始,从根开始,然后我们必须再次向下移动到正确的位置,沿当前后缀的整个长度。

此后缀的长度是我们前面讨论的“余数” 。我们必须消耗掉剩余的全部,直到达到零。这可能(并且经常如此)包括跳过多个节点,每次跳过都会使剩余部分减少我们跳过的边的长度。最后,我们到达的边缘比剩余的“余数”更长;在这里,我们将有效边设置为给定的边,将“有效长度”设置为剩余的“剩余 ”,就可以了。

但是请注意,实际的“remainder”变量需要保留,并且仅在每次插入节点后才递减。因此,我上面描述的假设使用的是初始化为'remainder'的单独变量。

关于后缀链接和重新扫描的注意事项

1)请注意,两种方法均会导致相同的结果。但是,在大多数情况下,后缀链接跳转明显更快。这就是后缀链接的全部原理。

2)实际的算法实现无需区别。如上所述,即使在使用后缀链接的情况下, “有效长度”也常常与链接位置不兼容,因为树的该分支可能包含其他分支。因此,从本质上讲,您只需要使用“有效长度”而不是“剩余 长度” ,并执行相同的重新扫描逻辑,直到找到比剩余后缀长度短的边即可。

3)关于性能的一个重要说明是,在重新扫描期间无需检查每个字符。由于有效的后缀树的构建方式,我们可以安全地假设字符匹配。因此,您主要是在计算长度,并且当我们跳到新的边缘时,唯一需要进行字符等效性检查,因为边缘由其第一个字符标识(在给定节点的上下文中始终是唯一的)。这意味着 “重新扫描” 逻辑与全字符串匹配逻辑(即在树中搜索子字符串)不同。

4)此处描述的原始后缀链接只是可能的方法之一 。例如NJ Larsson 等。将该方法命名为 “ 面向节点的自上而下” ,并将其与 “ 面向节点的自下而上”和两个“面向边缘的” 方法进行比较。不同的方法具有不同的典型和最坏情况下的性能,要求,限制等,但是通常看来, 面向边缘的方法是对原始方法的整体改进。

@jogojapan,您带来了很棒的解释和可视化。但是正如 @makagonov 所说,它缺少一些有关设置后缀链接的规则。通过 “aabaaabb” 一词逐步浏览http://brenden.github.io/ukkonen-animation/时,可以很好地看到它。当您从步骤 10 转到步骤 11 时,没有从节点 5 到节点 2 的后缀链接,但是活动点突然在那里移动。

@makagonov,因为我生活在 Java 世界中,所以我也尝试遵循您的实现来掌握 ST 构建工作流程,但由于以下原因,我感到很难:

  • 结合边缘和节点
  • 使用索引指针而不是引用
  • 破坏陈述;
  • 继续陈述;

因此,我最终用 Java 实现了这种实现,希望以更清晰的方式反映所有步骤,并减少其他 Java 人员的学习时间:

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

我的直觉如下:

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

从一开始,这意味着后缀树包含一个表示整个字符串的根节点(这是唯一从 0 开始的后缀)。

在 len(string)迭代之后,您将得到一个包含所有后缀的后缀树。

在循环期间,关键点是活动点。我的猜测是,这代表了后缀树中最深的点,该点对应于字符串的前 k 个字符的后缀。 (我认为适当的意思是后缀不能是整个字符串。)

例如,假设您已经看到字符 “abcabc”。活动点将表示树中与后缀 “abc” 相对应的点。

活动点用(origin,first,last)表示。这意味着您当前位于树的起点,即从节点原点开始,然后输入 string [first:last] 中的字符

添加新角色时,您将查看活动点是否仍在现有树中。如果是这样,那么您就完成了。否则,您需要在活动点向后缀树添加一个新节点,回退到下一个最短匹配项,然后再次检查。

注 1:后缀指针提供了指向每个节点的下一个最短匹配的链接。

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

注意 3:标准化部分只是节省了检查活动点的时间。例如,假设您始终使用 origin = 0,并且只更改了 first 和 last。要检查活动点,您每次必须在所有中间节点上都遵循后缀树。通过仅记录到最后一个节点的距离来缓存遵循此路径的结果是有意义的。

您能否举一个 “固定” 边界变量的含义的代码示例?

健康警告:我也发现该算法特别难以理解,因此请意识到,这种直觉在所有重要细节上可能都是不正确的...

您好我已经尝试在 ruby 中实现上述解释的实现,请检查一下。它似乎工作正常。

实现的唯一区别是,我尝试使用 edge 对象而不是仅使用符号。

它也存在于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