资源描述：
《后缀树的构造方法-ukkonen详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、后缀树的构造方法-Ukkonen详解问题的来源字符串匹配问题是程序员经常要面对的问题.字符串匹配算法的改进可以使许多工程受益良多,比如数据压缩和DNA排列.这篇文章讨论的是一种相对鲜为人知的数据结构---后缀树,并介绍它是如何通过自身的特性去解决一些复杂的匹配问题.你可以把自己想象成一名工作于DNA排列工程的程序员.那些基因研究者们天天忙着分切病毒的基因材料,制造出一段一段的核苷酸序列.他们把这些序列发到你的服务器里,指望你在基因数据库中定位.要知道,你的数据库里有数百种病毒的数据,而一个特定的病毒可以有成千上万的碱基.你的程序必须像C/S工程那样实时向
2、博士们反馈信息,这需要一个很好的方案.很明显,在这个问题上采取暴力算法是极其低效的.这种方法需要你在基因数据库里对比每一个核苷酸,测试一个较长的基因段基本会把你的C/S系统变成一台古老的批处理机.直觉上的解决方法由于基因数据库一般是不变的,通过预处理来把搜索简化或许是个好主意.一种预处理的方法是建立一棵Trie.我们通过Trie引申出一种东西叫作后缀Trie.(后缀Trie离后缀树仅一步之遥.)首先,Trie是一种n叉树,n为字母表大小,每个节点表示从根节点到此节点所经过的所有字符组成的字符串.而后缀Trie的“后缀”说明这棵Trie包含了所给字段的所有
3、后缀(也许正是一个病毒基因).图1BANANAS的后缀Trie图1展示了文本BANANAS的后缀Trie.关于这棵Trie有两个地方需要注意.第一,从根节点开始,BANANAS的每一个后缀都插入到Trie中,包括BANANAS,ANANAS,NANAS,ANAS,NAS,AS,S.第二,鉴于这种结构,你可以通过从根节点往下匹配的方式搜索到单词的任何一个子串.这里所说的第二点正是我们认为后缀Trie优秀的原因.如果你输入一个长度为N的文本并想在其中搜索一个长度为M的串,传统的暴力匹配需要进行N*M次字符对比,而一些改进过的匹配技术,比如像Boyer-Moo
4、re算法,可以在O(N+M)的时间开销内解决问题,平均效率更是令人满意.然而,后缀Trie亮出了O(M)的牌子,彻底鄙视了其他算法的成绩,后缀Trie对比的次数仅仅相当于被搜索串的长度!这确实是可圈可点的威力,这意味着你能通过仅仅7次对比便在莎士比亚所有作品中找出BANANAS.但有一点我们可不能忘了,构造后缀Trie也是需要时间的.后缀Trie之所以没有家喻户晓正是因为构造它需要O(n2)的时间和空间.平方级的开销使它在最需要它的领域---长串搜索中被拒之门外.横空出世直到1976年,EdwardMcCreigh发表了一篇论文,咱们的后缀树问世了.后缀
5、Trie的困境被彻底打破.后缀树跟后缀Trie有着一样的布局,但它把只有一个儿子的节点给剔除了.这个过程被称为路径压缩,这意味着树上的某些边将表示一个序列而不是单独的字符.图2BANANAS的后缀树图2是由图1的后缀Trie转化而来的后缀树.你会发现这树基本还是那个形状,只是节点变少了.在剔除了只有一个儿子的节点之后,总节点数由23降为11.经过证明,在最坏情况下,后缀树的节点数也不会超过2N(N为文本的长度).这使构造后缀树的线性时空开销成为可能.然而,McCreight最初的构造法是有些缺陷的,原则上它要按逆序构造,也就是说字符要从末端开始插入.如此
6、一来,便不能作为在线算法,它变得更加难以应用于实际问题,如数据压缩.20年后,来自赫尔辛基理工大学的EskoUkkonen把原算法作了一些改动,把它变成了从左往右.本文接下来的所有描述和代码都是基于EskoUkkonen的成果.对于所给的文本T,EskoUkkonen的算法是由一棵空树开始,逐步构造T的每个前缀的后缀树.比如我们构造BANANAS的后缀树,先由B开始,接着是BA,然后BAN,….不断更新直到构造出BANANAS的后缀树.图3逐步构造后缀树初窥门径加入一个新的前缀需要访问树中已有的后缀.我们从最长的一个后缀开始(图3中的BAN),一直访问到
7、最短的后缀(空后缀).每个后缀会在以下三种节点的其中一种结束.l一个叶节点.这个是常识了,图4中标号为1,2,4,5的就是叶节点.l一个显式节点.图4中标号为0,3的是显式节点,它表示该节点之后至少有两条边.l一个隐式节点.图4中,前缀BO,BOO,或者非前缀OO,它们都在某条表示序列的边上结束,这些位置就叫作隐式节点.它表示后缀Trie中存在的由于路径压缩而剔除的节点.在后缀树的构造过程中,有时要把一些隐式节点转化为显式节点.图4加入BOOK之后的BOOKKEEPER(也就是BOOK的后缀树)如图4,在加入BOOK之后,树中有5个后缀(包括空后缀).那
8、么要构造下一个前缀BOOKK的后缀树的话,只需要访问树中已存在的每一个后缀,然后
