普通英语的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)。

因此,我们从左侧开始,首先通过创建从根节点(在左侧)到叶的边,然后将其标记为[0,#] ,仅插入单个字符a ,这意味着该边代表子字符串从位置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. 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

  1. 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.

  2. 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.

阅读 607 次发布于 2019年12月27日
推荐阅读
为什么处理排序数组要比处理未排序数组快?

这是一段C ++代码,显示了一些非常特殊的行为。 出于某些奇怪的原因,奇迹般地对数据进行排序使代码快了将近六倍: #include #include #include int main() { // Generate data const unsigned arraySize = 32768; int da...

2019-12-20 阅读 10

如何撤消Git中的最新本地提交?

我不小心将错误的文件提交给Git ,但是我还没有将提交推送到服务器。 如何撤消本地存储库中的那些提交?

2019-12-20 阅读 12

如何在本地和远程删除Git分支?

我想在本地和远程删除分支。 尝试删除远程分支失败 $ git branch -d remotes/origin/bugfix error: branch 'remotes/origin/bugfix' not found. $ git branch -d origin/bugfix error: branch 'origin/bugfix' not found. $ git branch ...

2019-12-20 阅读 9

'git pull'和'git fetch'有什么区别?

主持人注意:鉴于此问题已经发布了67个答案 (其中一些已删除),请在发布另一个问题之前考虑您是否正在贡献新内容 。 git pull和git fetch什么区别?

2019-12-20 阅读 8

什么是正确的JSON内容类型?

我一直在弄乱JSON一段时间,只是将其作为文本推出,并没有伤害任何人(据我所知),但是我想正确地做事。 我已经看到许多所谓的JSON内容类型的“标准”: application/json application/x-javascript text/javascript text/x-javascript text/x-json 但是哪一个是正确的,还是最好的? 我发现在它们之间存在安全性和浏览...

2019-12-20 阅读 10

目录