Alc*_*ott 20 algorithm suffix-tree
我一直在寻找关于后缀树的教程很长一段时间.在SO,我发现了2个职位大概了解后缀树:1,2.
但我不能说我理解如何建立一个,哎呀.在Skiena的书"算法设计手册"中,他说:
由于线性时间后缀树构造算法非常重要,我建议使用现有的实现.
那么,后缀树的在线构造算法是如此难以实现吗？任何人都可以让我朝着正确的方向去理解它吗？
无论如何,切入追逐,除了建设之外,还有一件我对后缀树不了解的事情.因为后缀树中的边只是一对整数(右？),指定了子串的起始和结束位置,那么如果我想x在这个后缀树中搜索一个字符串,我应该怎么做呢？在后缀树中取消引用那些整数,然后逐个比较它们x？不可能这样.
jog*_*pan 21
首先,有许多方法来构造后缀树.Weiner(1973)的原始O(n)方法,由McCreight(1976)改进的方法,Ukkonen最着名的方法(1991/1992),以及一些进一步的改进,主要与实施和储存有关效率考虑.其中最值得注意的可能是Giegerich和Kurtz 对Lazy后缀树的高效实现.
此外,由于后缀数组的直接构造在2003年的O(n)时间内已经成为可能(例如使用Skew算法,但也有其他方法),并且因为有充分研究的方法
后缀数组通常比后缀树更受欢迎.因此,如果您的目的是为特定目的构建高度优化的实现,您可能需要研究后缀数组构造算法.
但是,如果您对后缀树构造感兴趣,特别是Ukkonen算法,我建议您仔细查看此SO帖子中的描述,您已经提到过,我们一起尝试改进该描述.这肯定远非完全直观的解释.
回答有关如何将输入字符串与边缘标签进行比较的问题:出于效率原因,在构造和查找期间,每个边缘标签的初始字符通常存储在节点中.但是其余部分必须在主文本字符串中查找,就像你说的那样,这确实会引起问题,特别是当字符串太大而不能容易地保存在内存中时.(加上事实,就像任何树的直接实现一样,后缀树是一个包含大量指针的数据结构,它消耗大量内存并且难以维护引用的局部性并从内存缓存中受益)后缀树比反向索引更难处理的主要原因之一.
如果将后缀数组与lcp表和子表结合使用(当然应该这样做),实际上就是获得后缀树.这一点在文章中提出:Kim,Park和Kim的Linearized Suffix Trees.lcp表启用了一个相当笨拙的自下而上遍历,子表可以轻松遍历任何一种类型.所以关于后缀树的故事使用引起参考问题局部性的指针在我看来是过时的信息.因此,只要使用底层后缀数组实现树,后缀树就是"正确而简单的方法".
Kim,Park和Kim的论文描述了Abouelhoda等人误导性标题文章中的方法变体:用后缀阵列替换后缀树.Kim等人的文章认为这是后缀树的实现,而不是替代.此外,在Kim等人的文章中更详细和直观地描述了Abouelhoda等人的构造的细节.
,