ACM通信
评论文章
后缀树40年
信贷:Papuchalka
当威廉·莱格兰德最终解密这个字符串时，似乎并没有比以前更有意义。
关键的见解
53305) 6 * 48264) 4 z); 806、488 p60)) 85; 1(;: * 883(88) 5 *, 46(88 * 96 * ?; 8) *(485); 5 * 2: *(; 4956 * 2(5 *陶瓷)8 p8 *, 4069285);) 68) 4; 1 (9; 48081; 8: 81; 4885; 4) 485528806 * 81 (9; 48 (88; 4 (34;48) 4; 161; 188;？；
解码后的信息是这样的:“在主教宿舍的好玻璃杯在魔鬼的座位41度13分东北和由北主干第七翼东侧从死神的左眼射一个蜜蜂线从树穿过射五十英尺外。”但至少它听起来更像自然语言，并最终引导了埃德加·爱伦·坡的《金甲虫》的主角。36去发现他一直在寻找的宝藏。Legrand用符号频率解决了一个替换密码。他首先寻找最频繁出现的符号，并将其变成英语中最频繁出现的字母，然后以同样的方式推断出最频繁出现的单词，然后是标点符号，等等。
在1843年之前和之后，面对一些神秘的消息时，人们的自然冲动是计算单个标记或子组件的频率，以寻找线索。生物序列或许是这种研究中最激烈、最吸引人的课题之一。一旦这些序列出现，统计分析人员就试图将字符或字符块与相关的生物功能联系起来。随着20世纪90年代中期出现的完整基因组的早期例子，似乎很自然地要统计大小为1、2等的所有块的出现，直到任何想要的长度，寻找编码区、启动子区等的统计特征。
本文不是关于密码学的。它是关于数据结构及其变体，以及它所携带的许多令人惊讶和有用的特性。其中一个事实是，为所有子字符串(也称为因素)，任何长度，文本字符串的n字符，它只需要时间和空间在文本字符串的长度中线性。虽然没有人会愚蠢到先生成所有可能的以指数形式出现的字符串，然后逐一计算它们出现的次数，但文本字符串仍然可能包含(n2)不同的子字符串，所以在线性空间(更不用说线性时间)将它们全部制成表格，已经令人费解了。
多年来，这种结构在文本搜索、索引、统计和压缩以及生物序列的汇编、比对中占据了中心舞台。他们的范围扩展到各种各样的领域，如检测剽窃，发现文本中令人惊讶的子字符串，测试代码的独特可解密性，等等。他们对计算机科学和整个IT的影响怎么强调都不为过。文本检索和生物信息学都离不开它们。在2013年，组合模式匹配研讨会庆祝了40th韦纳发明后缀树的周年纪念日41专门为那件事开了一节课。
历史点滴
在“弦学”的黎明，Donald Knuth推测了寻找两个总长度的长文本序列共同的最长子字符串的问题n要求(n日志n)时间。一个O（n日志n)的时间由卡普、米勒和罗森博格提供。26这种结构注定要在平行模式匹配中发挥作用，但Knuth的猜想没有持续多久:1973年，Peter Weiner证明了这个问题承认了一个优雅的线性时间解，41只要字符串的字母是固定的。这样的解决方案实际上是他最初为不同目的而建立的一种构造的副产品，即标识文本文件的任何子字符串，而不指定它们的所有子字符串。在这样做的过程中，Weiner引入了文本倒索引的概念，它将引发40年的改进、分析和应用，这是任何其他数据结构都难以共享的特性。
Weiner的原始构造从右到左处理文本文件。当每个新字符被读入时，他称之为“双树”的结构将被更新，以适应文本文件的越来越长的后缀。因此，这是一个固有的离线构建，因为文本必须在构建开始之前被完整地了解。或者，也可以说，该算法将为在线文本的反向构建结构。大约三年后，Ed McCreight提供了一个从左到右的算法，并将结构的名称改为“后缀树”，这个名称会被记住。32
让x是一串n- 1个符号超过一些字母和$一个额外的字符不在。扩展后缀树Tx与x一个数字搜索树收集的所有后缀x美元。具体地说,Tx定义如下。
- Tx有n叶子，标记为1到n。
- 每条弧都用符号{$}标记。对于任何我， 1我n，从根开始的路径上的标签的串联Tx到叶我正是后缀
- 对于任意两个后缀进而我而且进而j的x美元,如果wij最长公共前缀是这个吗进而我而且进而j有共同之处，那么Tx相对wij的路径是相同的进而我而且进而j．
中给出了扩展后缀树的一个例子图1．
该树可以解释为确定性有限自动机的状态转换图，其中所有节点和叶子都是最终状态，根是初始状态，标记的弧，假设指向下，表示状态转换函数的一部分。图中未指定的状态转换将导致唯一的非final水槽状态。我们的自动机可以识别由字符串的所有子字符串组成的(有限)语言x．这个观察结果也阐明了如何在在线搜索中使用树:让y作为模式，我们在树中沿着向下的路径来响应连续的符号y每次一个符号。很明显,y发生在x当且仅当这个过程导致最终状态时。而言,Tx，我们称之为弦的轨迹y如果存在，节点的路径是否从根开始Tx是标签y。
一个算法的直接构造展开Tx(通常称为后缀trie)很容易派生出来(参见图2)．我们从一个空树开始，并向其添加后缀x一次一美元。这个过程需要时间（n2),O（n2)空间，然而，它很容易减少空间到O（n)从而产生紧凑形式的后缀树(图3)．一旦做到了这一点，就有可能实现一个预期的非微不足道的目标O（n)时间施工。
在2013年的CPM大会上，麦克雷特透露了他的想法O（n)时间结构并不是作为韦纳的替代品而诞生的，她发明它是为了理解韦纳的论文，但当他把时间结构拿给韦纳看，请他确认他已经理解了那篇论文时，回答是“不，但你提出了一个完全不同的、优雅的结构!”在1975年未发表的课堂讲稿中，沃恩·普拉特展示了这种结构和韦纳的“重复器”的二元性。37麦克雷特的算法在本质上仍然是离线的，它立即引发了对在线版本的搜索。人们对在线算法做了一些部分的尝试，但为了1995年Esko Ukkonen的论文，这种变体不得不等了近20年。39在所有这些线性时间结构中，线性是基于有限字母表的假设和(n日志n)时间。1997年，马丁·法拉奇(Martin Farach)提出了一种算法，摒弃了当时流行的“在时间上使用一个后缀”的方法;该算法从构建后缀树到字符排序的时间线性缩短，因此对所有字母都是最优的。17特别地，对于更大的字母类，它在线性时间内运行，例如，当字母大小在输入长度上是多项式时。
1984年左右，Blumer等人。9和Crochemore14揭示了最小的有限自动机识别所有且仅识别字符串的后缀的惊人结果n人物只有O（n)状态和边缘。最初创造了一个有向无环词图(DAWG)，如果所有状态都是终端状态，它甚至可以进一步简化。14然后它接受字符串的所有子字符串，称为factorsubstring自动机。当字符串没有结束标记，并且它的后缀在树中用结束状态标记时，索引数据结构之间有很好的关系。
然后，后缀树是树的边缘压缩版本，它的节点数量可以像任何自动机一样最小化，从而提供字符串的压缩DAWG。将压缩和最小化这两种操作排列在一起，就会产生相同的结构。显然，Anatoli Slissenko(请参阅ACM数字图书馆“源材料”下的这篇文章的附录)在检测字符串中重复的工作中使用了类似的结构。这些自动机为Knuth的猜想提供了另一个更有效的反例，当它们被当作模式匹配机器来使用时图4)．
后缀树的出现与信息论中一些有趣而独立的发展相吻合。在他关于信息概念的著名方法中，Kolmogorov将字符串中的信息或结构等同于通用图灵机生成该字符串所需的最短程序的长度。不幸的是，这种度量是不可计算的，即使可以计算，大多数长字符串也是不可压缩的(也就是说，缺少生成它们的短程序)，因为长字符串越来越多，而短程序(本身就是字符串)相对少得多。
Kolmogorov的通用和无所不知的机器所利用的规律可能是任何可以想象的类型，但如果把它们限制在影响文本的重复子字符串形式的语法冗余呢?如果一个字符串重复了很多次，可以通过指向一个普通副本的指针对所有出现的情况进行编码。这个副本可以是文本内部的，也可以是文本外部的。在前一种情况下，指针可以指向两个方向，也可以只指向一个方向，允许或禁止指针嵌套，等等。吉姆•斯托勒在他的博士论文中指出，几乎所有这类“宏观计划”都难以解决，只有一个例外。在此之前不久，在一篇名为《论有限序列的复杂性》的里程碑式论文中，30.亚伯拉罕·伦佩尔(Abraham Lempel)和雅各布·齐夫(Jacob Ziv)提出了一种变量到块的编码，基于对文本的简单解析，压缩所获得的特征在限度内与根据源概率量身定制的压缩器产生的特征匹配。因此，由伦佩尔和齐夫提出的压缩方法通过显著的恒星对齐，不仅在信息理论意义上是最优的，而且它通过后缀树找到了一个最优的线性时间实现，正如迈克尔·罗德(Michael Rodeh)、沃姆·普拉特(Vaugham Pratt)和西蒙·Even立即详细说明的那样。38
在他的原始论文中，Weiner列出了他的“双树”的几个应用，包括最著名的离线字符串搜索:预处理一个文本文件，以支持查询，返回在时间上线性的模式长度的给定模式的出现。当然，“双树”解决了Knuth的猜想，通过展示如何在线性时间内找到有限字母表中两个文件共有的最长子字符串。随后普拉特发表了一篇题为《韦纳重复查找器的改进和应用》的文章。37十年后，阿尔贝托·阿波斯托里克在一篇名为《后缀树的无数优点》的论文中列出了更多的应用，2二十年后，在Crochemore和Rytter、Dan Gusfield以及Crochemore、Hancart和Lecroq的参考书中，后缀树和与其相关的结构及其应用产生了几个章节(参见ACM数字图书馆中与本文一起提供的附录)。
后缀树所需要的空间在最需要它们的应用程序中是一个麻烦。例如，对于g级的基因组，比源基因组大20倍与只大11倍之间的空间差异可能非常大。为了一些照明，斯蒂芬·库尔茨和他的同事们致力于巧妙地分配这棵树和它的一些同伴结构。282001年，David R. Clark和J. Ian Munro提出了二级存储中最节省空间的方法之一。13克拉克和门罗的“简洁的后缀树”试图尽可能多地保留后缀树的结构。然而，乌迪·曼伯和尤金·w·迈尔斯采取了不同的方法。1990年，他们引入了“后缀数组”，31它消除了后缀树的大部分结构，但仍然能够实现许多相同的操作，要求每个文本字符的空间等于2个整数，并及时搜索O(|P| +日志n)(通过接受搜索时间可约化为1O(|P| +日志n))。后缀数组将输入的后缀按字典顺序存储，可以看作是在后缀树中通过预序遍历找到的叶子标签序列，并根据字典顺序展开每个节点。
虽然后缀数组一开始似乎是一种不同于后缀树的数据结构，但这种区别已经消失了。例如，Manber和Myers对后缀数组的原始构造O（n日志n)时间，但后缀数组可以从任何字母的后缀树在线性时间内构建。2001年，Toru Kasai等人。27说明后缀树可以由后缀数组在线性时间内构造出来。因此后缀数组被认为是后缀树的一种简洁的表示。2003年，三组人对Farach的后缀树构造算法进行了三种不同的修改，给出了第一个直接构造后缀数组的线性时间算法;即，第一个计算后缀数组的线性时间算法，它没有首先计算完整的后缀树。从那时起，出现了许多快速构建后缀数组的算法，尤其是Nong, Zhang和Chan，35这是线性时间，在实践中很快。后缀数组是目前软件系统中应用最广泛的后缀树变体，其构造算法快速，所需空间小。更简洁的后缀树和数组O（n)位来表示二进制字母表(O（n格罗西和维特提出的。21
虽然后缀数组一开始似乎是一种不同于后缀树的数据结构，但这种区别已经消失了。
实际上，后缀树和压缩的历史是紧密交织的。这并不令人惊讶，因为模式发现试图发现的冗余是为了压缩而删除的理想对象。1994年，M. Burrows和D.J. Wheeler提出了一种突破性的基于后缀排序的压缩方法。11大约在1995年，Amihood Amir, Gary Benson和Martin Farach提出了在压缩文本中搜索的问题。12000年，Paolo Ferragina和Giovanni Manzini引入了FM-inde x，这是一种基于Burrows-Wheeler变换的压缩后缀数组。19该结构可能比源文件更小，支持搜索而不解压。这在Ferragina等人的压缩树索引问题中得到了推广。18使用了对Burrows-Wheeler变换的修改。
辐射，扩展和挑战
正如一开始所强调的那样，几乎没有任何文本处理应用程序在某一点或另一点不需要这些索引。一个著名的案例是寻找错误，1985年盖德·兰道在他的博士论文中首次有效地解决了这个问题。29在这种搜索中，查找与模式不同的文本的子字符串，这种错误的数量有限，比如单个字符的删除、插入或替换。为了有效地解决这个问题，朗道将后缀树与所谓的最低共同祖先(LCA)问题的巧妙解决方案结合起来。LCA问题假设给定了一棵有根的树，然后它寻找任意一对节点，树中最低的节点是这两个节点的祖先。23可以看出，在对树进行线性时间预处理之后，任何LCA查询都可以在常数时间内得到回答。Landau在后缀树上使用LCA查询，在保证匹配模式的文本片段上执行恒定时间的跳转。当k错误是允许的，在任何给定位置上发生的搜索可以被放弃k这样的跳跃。这就产生了一种算法，可以搜索带有的模式k的文本中的错误n字符O（nk)的步骤。
当然，在后缀树和数组支持的基本原语中，可以发现前面提到的在文本中搜索模式的时间与模式的长度成比例，而不是文本的长度。事实上，甚至可以枚举与次数成比例的时间出现次数，并通过对树进行简单的预处理，告诉任何查询模式在时间上与模式大小成比例的总出现次数。找到在文本中出现两次或在两个文件之间共享的最长子字符串的问题已经在前面提到过:这可能是一切开始的地方。一个密切相关的问题是检测文本中的平方、重复和最大周期，这个问题源于阿克塞尔·休(Axel Thue)一个多世纪前的工作，当时在压缩和DNA分析方面有多种应用。正方形是由相同字符串的两个连续出现组成的模式。后缀树用于最优检测O（n日志n)计算文本中所有方格(或重复)的时间，每个方格都有一组起始位置，5然后在线性时间内找到并存储文本中所有不同的方子串。对于任何查询模式，正方形在后缀树的扩充中发挥作用，适合报告其非重叠出现的次数。6，10
后缀树在为文本字符串设置某种类型的签名以及相似性或差异度量方面有多种用途。
后缀树在为文本字符串设置某种类型的签名以及相似性或差异度量方面有多种用途。
在后一种情况下，存在计算文本中禁用或缺失的单词的问题，这些单词是不出现在文本中的最小字符串(而它们的所有适当子字符串都出现)。8，15这些词导致了一种原始的文本压缩方法。16后缀树曾经被认为是文本“词袋”的简洁表示，可以用来评估两个文本文件的相似性，从而支持聚类、文档分类，甚至系统发育。4，12，40直观上，这是通过评估两个输入序列的树有多少共同点来完成的。适当增加子字符串在每个节点结束的概率，树可以用来检测任何长度的子字符串，3.例如，在探索生物序列中的启动子区域。
后缀树的连接，例如，k2文本文件，支持有效的解决问题，从抄袭检测领域的motif发现的生物序列。的必要性k不同的结束标记在保持线性时间方面带来了一些微妙的变化，这一点读者可以参考Gusfield。22在其最初的形式中，为多个文本建立索引的问题被称为“颜色问题”，并试图报告对于任何给定的查询字符串以及在查询的时间线性中，总共有多少个文档k包含查询的至少一次出现。许焯权(Lucas C.K. Hui)在1992年给出了一个简单而优雅的解决方案。25近年来，许多字符串的组合后缀树(也称为广义后缀树)被用来解决各种文档列出问题。在这里，一组文本文档被预处理为组合后缀树。问题是返回包含查询模式的所有文档的列表，其时间与此类文档的数量成比例，而不是与出现的总次数(occ)成比例，后者可能要大得多。这个问题在Muthukrishnan得到了解决33通过将其还原为最小范围查询．这个基本的文档列出问题已经扩展到许多其他问题，包括列出top-k在各种字符串和信息距离中。例如，在Hon等人中，24广义后缀树结构是设计线性机字数据结构的关键k最常见的包含模式的文档p在时间上几乎线性的模式大小。
后缀树的一个令人惊讶的变体是由Brenda Baker引入的，目的是检测学生报告中的剽窃行为以及优化软件开发。7这种模式匹配的变体被称为参数化的匹配，使人们能够找到与系统地改变参数相同的程序片段，或与系统地重新标记或排列字母表中的字符相同的子字符串。后缀树概念的一个明显扩展是向不止一个维度扩展，尽管扩展本身的机制远非显而易见。34在更遥远的亲戚中，人们发现"小波树"最初作为压缩后缀数组的一种表示，20.小波树使人们能够对一般字母执行排序和选择原语，以前仅限于位向量等。
这个列表可以无限延伸，但是本文的范围并不是详尽的。事实上，经过40年的不懈发展，我们有理由认为这个名单会继续增加。开放性问题也比比皆是。例如，许多观察到的序列是用数字而不是字符表示的，并且在这两种情况下都受到各种类型的错误的影响。虽然两个字符比较的结果只有一个比特，但两个数字可以或多或少接近，这取决于它们的差异或其他指标。同样，两个文本字符串或多或少可能相似，这取决于更改其中一个字符串所需的基本步骤的数量。这个框架最具破坏性的方面是失去了传递性，而传递性会导致最有效的精确字符串匹配解决方案。然而，能够支持刚才强调的那种快速而优雅的近似模式查询的索引将非常有用。希望他们很快就能恢复过来，并及时拥有自己的40个th周年庆典。
致谢我们感谢Ed McCreight, Ronnie Martin, Vaughan Pratt, Peter Weiner和Jacob Ziv的讨论和帮助。我们非常感谢审稿人对本文早期版本的仔细审查，这导致了许多改进。
参考文献
1.Amir, A.， Benson, G.和Farach, M.让沉睡的文件躺下:z压缩文件中的模式匹配。在5年会议的程序th离散算法年会(阿灵顿，弗吉尼亚州，1994)，705714。
2.后缀树的无数优点。词的组合算法，北约高级科学研究所第12卷，F系列。A. Apostolico和Z. Galil编。斯普林格-弗拉格，柏林，1985,8596。
3.Apostolico, A.， Bock, M.E.和Lonardi, S.惊讶的单调和对不寻常词汇的大规模探索。J.计算生物学10， 3 / 4(2003)， 283311。
4.Apostolico, A.， Denas, O.和Dress, A.比较子串分析的有效工具。生物技术149， 3(2010)， 120126。
5.Apostolico, a .和prepare ata, F.P.字符串中重复次数的最佳离线检测。定理。第一版。Sci。22， 3(1983)， 297315。
6.字符串统计问题的数据结构和算法。Algorithmica 15， 5(1996年5月)，481494。
7.字符串中的参数化重复:算法和软件维护的应用。26 . c， 5(1997)， 13431362。
8.比尔,M.-P。，Mignosi, F. and Restivo, A. Minimal forbidden words and symbolic dynamics. In13年的会议记录th计算机科学理论年会，计算机科学课堂讲稿第1046卷(1996年2月2224日，法国格勒诺布尔)。施普林格,555566年。
9.Blumer, A.， Blumer, J.， Ehrenfeucht, A.， Haussler, D.， Chen, M.T.和Seiferas, J.识别文本子词的最小自动力。定理。第一版。Sci 40。， 1(1985)， 3155。
10.Brodal, g.s.， Lyngsø， r.b.， Östlin, A.和Pedersen, C.N.S.及时解决字符串统计问题O（n日志n)。在29年的会议记录th国际自动机、语言和程序设计研讨会，计算机科学讲义第2380卷(2002年7月813日，西班牙马拉加)。施普林格,728739年。
11.Burrows, M.和Wheeler, D.J.一种分块排序无损数据压缩算法。1994年5月，数字设备公司，技术报告124。
12.Chairungsee, S.和Crochemore, M.使用最小缺席词建立系统发育学。计算机理论450， 1(2012)， 109116。
13.Clark, D.R.和Munro, j。i。二级存储的高效后缀树。在七项会议的议事程序th离散算法年会，(亚特兰大，乔治亚州，1996)，383391。
14.Crochemore, M.换能器和重复。定理。第一版。科学。, 45岁， 1(1986)， 6386。
15.M. Crochemore, M. Mignosi, F.和A. Restivo, A. Automata和forbidden words。信息处理信件67， 3(1998)， 111117。
16.M. Crochemore, Mignosi, F.， Restivo, A和S. Salemi, S.使用反字典的数据压缩。在无损数据压缩学报11(2000)。斯托勒主编，17561768。
17.用大字母构建最优后缀树。在三十八届立法会会议纪要thIEEE计算机科学基础年会(迈阿密海滩，佛罗里达州，1997)，137143。
18.Ferragina, P.， Luccio, F.， Manzini, G.和Muthukrishnan, S.压缩和索引标记树的应用程序。JACM 571(2009)。
19.Ferragina, P.和Manzini, G.机会数据结构及其应用。在foc(2000), 390398。
20.Grossi, R.， Gupta, A.和Vitter, J.S.高阶熵压缩文本索引。在苏打水(2003), 841850。
21.压缩后缀数组和后缀树，用于文本索引和字符串匹配。在美国计算机学会计算理论研讨会论文集(波特兰,或,2000)。ACM出版社,397406年)。
22.Gusfield D。字符串，树和序列的算法:计算机科学和计算生物学。剑桥大学出版社，英国剑桥，1997年。
23.Harel, D.和Tarjan, R.E.寻找最近共同祖先的快速算法。13 . c， 2(1984)， 338355。
24.亲爱的,W.-K。，Shah, R. and Vitter, J.S. Space-efficient framework for top-k字符串检索问题。在foc．计算机学报，2004,24(3):362 - 368。
25.颜色集大小问题及其在字符串匹配中的应用。在3个会议的会议记录理查德·道金斯“组合模式匹配学术年会”，2016。计算机科学课堂讲稿第644页，(图森，AZ, 1992)。A. Apostolico, M. Crochemore, Z. Galil, U. Manber主编。斯普林格出版社,柏林,230243年版。
26.卡普，r.m.，米勒，r.e.和罗森伯格，A.L.快速识别字符串，树和数组中的重复模式。在四人会议的会议记录th美国计算机学会计算理论研讨会(丹佛,有限公司,1972年)。ACM出版社,12513年。
27.Kasai, T.， Lee, G.， Arimura, H.， Arikawa, S.和Park, K.后缀数组的线性时间最长公共前缀计算及其应用。CPM。斯普林格出版社,2001年版,181192年版。
28.减少后缀树的空间要求。Softw。Pract。Exp。29， 13(1999)， 11491171。
29.错误输入中的字符串匹配。1986年，特拉维夫大学计算机学系博士学位论文。
30.李彦宏，李彦宏。有限序列的复杂性。IEEE反式。正无穷。理论22(1976), 7581。
31.后缀数组:在线字符串搜索的一种新方法。在1的会议记录圣离散算法年会(旧金山，CA, 1990)， 319327。
32.一种空间经济型后缀树构造算法。j .算法23， 2(1976)， 262272。
33.文档列出问题的有效算法。在13年的会议记录th离散算法年会(2002), 657666。
34.J. C. Na, P. Ferragina, R. Giancarlo和K. Park。二维模式索引。《算法百科全书》，2008。
35.农庚，张森，陈伟华，等。线性时间后缀数组构造的两种有效算法。IEEE反式。第一版。60， 10(2011)， 14711484。
36.坡,电子艺界金甲虫和其他故事。多佛节俭版系列。多佛,1991年。
38.Rodeh, M.， Pratt, V.和Even, S.通过字符串匹配进行数据压缩的线性算法。j . Assoc。第一版。马赫。28， 1(1981)， 1624。
39.后缀树的在线构建。Algorithmica 14， 3(1995)， 249260。
40.Ulitsky, I.， Burstein, D.， Tuller, T.和Chor, B.系统基因组重建的平均常见子串方法。计算生物学13， 2(2006)， 336350。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM股份有限公司
没有发现记录