最近在学习后缀树的构造，在网上找了好久发觉国内详解它的构造的文章胜少，在苦苦寻觅了许久，终于发现了一个网友翻译的一篇文章，很好，于是我转帖出来，希望能有更多的人受益，也希望国内多一些英文高手多翻译一些国外的技术文章，好让我们这些英文很烂的人受益，呵呵！
后缀树
Fast String Searching With Suffix Trees
原著
Mark Nelson. Fast string searching with suffix trees. 1996.
构造法
E. Ukkonen. On-line construction of suffix trees. 1995.
翻译
3xian / 三鲜 in GDUT
三鲜 序
原来是打算翻译Sartaj Sahni的Suffix tree, 并专注地进行了一周, 连复习备考的时间也不惜占去. 我希望给国产的同好者提供更通俗易懂的资料, 在翻译的同时对原文进行了删改, 并加入了许多自己的心得. 然而后来发现了Mark Nelson的这篇文章, 相比之下更有亲和力, 于是老实地尽弃前功来翻译这篇. 更重要一个原因是, Mark Nelson介绍的是Ukkonen的构造法O(n), 它比Sartaj Sahni的构造法O(nr), r为字母表大小 在时间上更有优势. 但我们不能说Sartaj Sahni的算法慢, 因为r往往会很小, 因此实际效率也接近线性, 两种构造法在思想上均有可取之处.
本文偏重于阐述后缀树的构造过程, 而并没有直接介绍后缀树除了匹配以外还能做什么. 其实后缀树是一种功能非常强大的数据结构, 你可以去搜索引擎了解一下它还有多少功能, 当然我最希望的是你在阅读本文之后已经足以体会后缀树的妙处, 日后遇到诸多问题的时候都能随心随意地用上.
最后唠叨一句. 我所见过的各种介绍后缀树的论文都难免使初学者陷入混乱, 本文估计也好不到哪里去. 这在一定程度上说明了后缀树的原理是不太浅显的, 理解它需要在整体上把握, 建议希望读者先不要纠结于细节, 思路不清则反复阅读.
问题的来源
字符串匹配问题是程序员经常要面对的问题. 字符串匹配算法的改进可以使许多工程受益良多, 比如数据压缩和DNA排列. 这篇文章讨论的是一种相对鲜为人知的数据结构 --- 后缀树, 并介绍它是如何通过自身的特性去解决一些复杂的匹配问题.
你可以把自己想象成一名工作于DNA排列工程的程序员. 那些基因研究者们天天忙着分切病毒的基因材料, 制造出一段一段的核苷酸序列. 他们把这些序列发到你的服务器里, 指望你在基因数据库中定位. 要知道, 你的数据库里有数百种病毒的数据, 而一个特定的病毒可以有成千上万的碱基. 你的程序必须像C/S工程那样实时向博士们反馈信息, 这需要一个很好的方案.
很明显, 在这个问题上采取暴力算法是极其低效的. 这种方法需要你在基因数据库里对比每一个核苷酸, 测试一个较长的基因段基本会把你的C/S系统变成一台古老的批处理机.
直觉上的解决方法
由于基因数据库一般是不变的, 通过预处理来把搜索简化或许是个好主意. 一种预处理的方法是建立一棵Trie. 我们通过Trie引申出一种东西叫作后缀Trie. (后缀Trie离后缀树仅一步之遥.) 首先, Trie是一种n叉树, n为字母表大小, 每个节点表示从根节点到此节点所经过的所有字符组成的字符串. 而后缀Trie的 “后缀” 说明这棵Trie包含了所给字段的所有后缀 (也许正是一个病毒基因).
图1
BANANAS的后缀Trie
图1展示了文本BANANAS的后缀Trie. 关于这棵Trie有两个地方需要注意. 第一, 从根节点开始, BANANAS的每一个后缀都插入到Trie中, 包括BANANAS, ANANAS, NANAS, ANAS, NAS, AS, S. 第二, 鉴于这种结构, 你可以通过从根节点往下匹配的方式搜索到单词的任何一个子串.
这里所说的第二点正是我们认为后缀Trie优秀的原因. 如果你输入一个长度为N的文本并想在其中搜索一个长度为M的串, 传统的暴力匹配需要进行N*M次字符对比, 而一些改进过的匹配技术, 比如像Boyer-Moore算法, 可以在O(N+M)的时间开销内解决问题, 平均效率更是令人满意. 然而, 后缀Trie亮出了O(M)的牌子, 彻底鄙视了其他算法的成绩, 后缀Trie对比的次数仅仅相当于被搜索串的长度!
这确实是可圈可点的威力, 这意味着你能通过仅仅7次对比便在莎士比亚所有作品中找出BANANAS. 但有一点我们可不能忘了, 构造后缀Trie也是需要时间的.
后缀Trie之所以没有家喻户晓正是因为构造它需要O(n2)的时间和空间. 平方级的开销使它在最需要它的领域 --- 长串搜索 中被拒之门外.
横空出世
直到1976年, Edward McCreigh发表了一篇论文, 咱们的后缀树问世了. 后缀Trie的困境被彻底打破.
后缀树跟后缀Trie有着一样的布局, 但它把只有一个儿子的节点给剔除了. 这个过程被称为路径压缩, 这意味着树上的某些边将表示一个序列而不是单独的字符.
图2
BANANAS的后缀树
图2是由图1的后缀Trie转化而来的后缀树. 你会发现这树基本还是那个形状, 只是节点变少了. 在剔除了只有一个儿子的节点之后, 总节点数由23降为11. 经过证明, 在最坏情况下, 后缀树的节点数也不会超过2N (N为文本的长度). 这使构造后缀树的线性时空开销成为可能.
然而, McCreight最初的构造法是有些缺陷的, 原则上它要按逆序构造, 也就是说字符要从末端开始插入. 如此一来, 便不能作为在线算法, 它变得更加难以应用于实际问题, 如数据压缩.
20年后, 来自赫尔辛基理工大学的Esko Ukkonen把原算法作了一些改动, 把它变成了从左往右. 本文接下来的所有描述和代码都是基于Esko Ukkonen的成果.
对于所给的文本T, Esko Ukkonen的算法是由一棵空树开始, 逐步构造T的每个前缀的后缀树. 比如我们构造BANANAS的后缀树, 先由B开始, 接着是BA, 然后BAN, … . 不断更新直到构造出BANANAS的后缀树.
图3
逐步构造后缀树
初窥门径
加入一个新的前缀需要访问树中已有的后缀. 我们从最长的一个后缀开始(图3中的BAN), 一直访问到最短的后缀(空后缀). 每个后缀会在以下三种节点的其中一种结束.
l 一个叶节点. 这个是常识了, 图4中标号为1, 2, 4, 5的就是叶节点.
l 一个显式节点. 图4中标号为0, 3的是显式节点, 它表示该节点之后至少有两条边.
l 一个隐式节点. 图4中, 前缀BO, BOO, 或者非前缀OO, 它们都在某条表示序列的边上结束, 这些位置就叫作隐式节点. 它表示后缀Trie中存在的由于路径压缩而剔除的节点. 在后缀树的构造过程中, 有时要把一些隐式节点转化为显式节点.
图4
加入BOOK之后的BOOKKEEPER
(也就是BOOK的后缀树)
如图4, 在加入BOOK之后, 树中有5个后缀(包括空后缀). 那么要构造下一个前缀BOOKK的后缀树的话, 只需要访问树中已存在的每一个后缀, 然后在它们的末尾加上K.
前4