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

maichao 投递于 2013/07/18 15:10 (共 16 段, 翻译完成于 07-28)
阅读 11109
收藏 61
7
加载中

本文试图描述Ukkonen算法,首先显示当字符串是简单的(即不包含任何重复的字符)时候它做什么,然后扩展到完整的算法。

首先来看一些前言:

  1. 我们正在建设的,基本上像一个搜索特里结构(单词查找树)。所以有一个根节点,从根节点引出新的节点,以及进一步从新节点引出其它节点,依次类推。
  2. 但是:与搜索单词查找树中不同,边标签不是单个字符。相反,每个边的标签是使用一对整数[从哪,到哪]。这些都是指向文本的指针。从这个意义上说,每个边有任意长度的字符串标签,但只需要O(1)的空间(两个指针)。
赵亮-碧海情天
赵亮-碧海情天
翻译于 2013/07/19 15:20
4

基本原理

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

abc

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

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

赵亮-碧海情天
赵亮-碧海情天
翻译于 2013/07/19 15:33
1

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

而其意义如下:


现在我们前进到位置2(b的右边)。 我们每个步骤的目标是插入至当前位置的所有后缀。
我们通过以下动作完成目标:
  •  扩展已存在边a为ab
  •  插入一条新边b
在我们的图示里,它看起来如下:
enter image description here
而其意义如下:

我们看到了两点:

  • ab边的图示与它在起始树:[0,#]边的图示是相同的。它的意义却已经自动更改了,因为我们把当前的位置#从1更改到2。
  • 每条边使用的空间复杂度为O(1),因为无论边代表多少个字符 ,它都是由指向文本里的两个指针组成。
接着我们再次增加位置,并且修改树:给每个已经存在的边增加c,插入一条表示新后缀c的边。
在我们的图示里,它看起来如下:

而其意义如下:

我们看到
  •   这棵树是经过上面的每个步骤后至当前位置的正确的后缀树。
  •   步骤数目与文本中包含的字符一样多。
  •   每个步骤的工作量是O(1),因为所有已经存在的边都是增加#来自动更改的,而且为最后一个字符插入一条新边的时间复杂度为  O(1)。因此对一个长度为n的字符串来说,只需要O(n)时间复杂度。
几点人
几点人
翻译于 2013/07/27 14:39
2

第一次扩展:简单的重复

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

abcabxabcd
这个字符串像前面例子里一样是abc开始的,接着重复ab ,紧跟着x,再接着重复abc,紧跟着d。

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

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

而且我们需要在根节点插入当前步骤的最末的后缀a。
我们做这些之前,我们引入除#之外的 两个或者更多变量,当然这些变量一直都存在,只是我们迄今为止没有使用它们:
  •    活动点,它是一个三元组(活动节点,活动边,活动长度)
  •    剩余后缀数,它是一个整数,来说明我们需要插入多少个新的后缀。
几点人
几点人
翻译于 2013/07/27 15:04
2
这两个图示的确切含义不久就会清晰,不过现在我们只能说:
  •  在简单的abc例子里,活动点总是(root,'0x',0),也就是说,活动节点是根节点,活动边是由空字符'0x'指定的边,活动长度是0。这么做的结果是我们在每一步骤里插入的一条新边是作为新创建的边插入到根节点。不久我们就会明白为什么需要三元组表示这条信息。
  •  在每个步骤开始时剩余后缀数总是设置为1。它的意义是我们主动插入到每一步骤末尾的后缀数目是1(总是最后一个字符)。
现在将有变化了,当我们给根节点插入当前最后一个字符a的时候,我们特别注意到已经存在一条以a开始的边:abca。在这种情况下我们做如下工作:
  • 我们不向根节点插入一条新边[4,#]。相反,我们只是注意到后缀a已经在我们的树里。它终止在更长的边的中间位置,不过这么做我们并不疑惑,我们还是保留它们原来的样子。
  • 我们设置活动点为(root,'a',1)。这意味着活动点现在是在根节点的以a开始的向外的边的中间某个位置,具体地指这条边的位置1之后。我们注意到这条边只是由它的首个字符a来声明的。这就足够了,因为以一个特定的字符开始的只有一条边(通读整个文档之后可以确定这是真的)。
  • 我们还增加了剩余后缀数, 那么在下一步骤开始的时候,剩余后缀数为2。
几点人
几点人
翻译于 2013/07/27 15:51
2

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

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

而且 由于剩余后缀数为2 ,我们需要插入目前位置的两个最终后缀:ab和b。这主要是因为:
  • 前一步骤的a后缀从来都没有真正地插入。因此它保留下来,然而由于我们已经向前走了一步,它现在由a延长为ab。
  •  还有,我们需要插入新的最终边b。
 实际上,这意味着我们要修改活动点(它现在指向的是abcab边里的a之后),而且插入当前的最后一个字符b, 不过:同时它也证明b也 已经出现在同一条边里。
 因此,我们再次不修改这棵树,我们只是:
  •  修改活动点为(root,'a',2)(是与前面相同的节点和边,只不过现在我们指向到b之后)
  •  增加剩余后缀数为3 ,因为我们仍然不能插入前一个步骤的最终边,同时我们也不能插入当前的最终边
几点人
几点人
翻译于 2013/07/27 16:26
2

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

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

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

这条边表示的仍然是指向文本内部的指针,因此分割和插入内部节点的时间复杂度为O(1)。

几点人
几点人
翻译于 2013/07/27 16:42
2

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

向根节点插入遵循:

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

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

再此说明,它的时间复杂度为 O(1),而且我们按照规则1所示把剩余后缀数修改为1,活动节点修改为(root,'x',0)。
几点人
几点人
翻译于 2013/07/27 17:08
2

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

如果我们分割一条边并插入新的节点,而且如果它不是在当前步骤里创建的第一个节点
的话,我们通过特殊的指针,即后缀连接,把 以前插入的节点和新增的节点连接起来
。后面我们将明白为什么这么做是有用的。这儿我们要明白:后缀连接表示为虚线边:
我们仍然需要插入当前步骤的最终后缀x。因为活动节点的活动长度部分已经减少到0,最终直接插入到根节点上。由于根节点上没有以x开始的边,所以我们插入了新边:

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

几点人
几点人
翻译于 2013/07/27 17:25
2

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

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

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

几点人
几点人
翻译于 2013/07/27 17:42
2
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(9)

少主丶无翼
自己用Java实现了一个,欢迎大家点评:http://blog.csdn.net/vickyway/article/details/50067101
豆豆爸
豆豆爸
赞一个,我正在学习中,编写一个Golang的实现,完工了就共享出来
maichao
maichao
当时看的时候觉得讲的思路比较清晰,然后就投递过来了,文章仅仅讲了Ukkonen 的算法。

应用的话很广泛的,比如:在生物信息学中的DNA索引,利用后缀树来表示DNA碱基的信息。

文章说了后缀树构建的最基本的算法,属于In-memory,但是在面对大量数据的时候memory locality较差,效率很低。还有好多其他构建的算法,如:TDD,WaveFront等。在2012年Essam等人提出的ERA,可以并行化,对于构建很长的字符串的后缀树比较有效,速度也较快。
GreatFish
GreatFish
这文章选的不太好啊,都没介绍这个算法有什么实际的用处啊
沙枣
沙枣
这个算法有何应用?有没有实现语言?
晕dows
晕dows

引用来自“kuntzuo”的评论

原文在何处?

标题下面有个英文原文的链接
kongnanlive
kongnanlive
弱弱的问下,这个用到什么地方合适?
XMAN2017
XMAN2017
原文在何处?
Anterior
Anterior
不错正在做
返回顶部
顶部