真的很难理解后缀树
我一直在寻找关于后缀树的教程很长一段时间。 在SO中，我找到了2篇有关理解后缀树的文章：1,2。
但我不能说我懂得如何构建一个哎呀。 在Skiena的算法设计手册中，他说：
由于线性时间后缀树构造算法非常平凡，我推荐使用现有的实现。
那么，后缀树的在线构建算法是如此困难？ 任何人都可以让我朝正确的方向去了解它？
无论如何，除了施工之外，还有一件事我不了解后缀树。 因为后缀树中的边只是一对整数（右），指定了子串的起始和结束位置，所以如果我想在这个后缀树中搜索字符串x ，我该怎么做？ 在后缀树中取消引用这些整数，然后将它们逐一与x进行比较？ 不能这样。
首先，构建后缀树有很多种方法。 Weiner（1973）的原始O（n）方法，McCreight（1976）的改进方法，Ukkonen最为人熟知的方法（1991/1992）以及一些进一步的改进，主要与实现和存储有关效率考虑。 其中最值得注意的可能是Giegerich和Kurtz的延迟后缀树的高效实现。
此外，由于后缀数组的直接构造在2003年的O（n）时间已成为可能（例如，使用Skew算法，但也有其他的算法），并且由于有充分研究的方法
后缀数组通常优于后缀树。 因此，如果您的目的是为特定目的构建高度优化的实现，您可能需要研究后缀数组构造算法。
然而，如果你的兴趣是后缀树结构，尤其是Ukkonen算法，我想建议你仔细看看这个SO帖子中的描述，你已经提到过，并且我们试图一起改进这个描述。 这绝对不是一个完美直观的解释。
要回答有关如何将输入字符串与边缘标签进行比较的问题：为了在构造和查找期间提高效率，每个边缘标签的初始字符通常存储在节点中。 但其余部分必须在主文本字符串中查找，就像您所说的那样，而且实际上这可能会导致问题，特别是当字符串太大以至于无法将其保存在内存中时。 这（再加上像树的任何直接实现一样，后缀树是一个包含大量指针的数据结构，这些指针消耗大量内存，并且难以维护引用的局部性并受益于内存缓存）的事实是后缀树比倒过来的索引更难处理的主要原因之一。
如果将后缀数组与一个lcp表和一个子表结合在一起，你当然应该这样做，你基本上得到一个后缀树。 这一点在Kim，Park和Kim的文章“Linearized Suffix Trees”中做了介绍。 lcp表使得自底向上的遍历相当尴尬，并且子表使得能够轻松遍历任何一种类型。 所以关于后缀树使用指针引起参考问题的地方的故事在我看来是过时的信息。 因此，只要您使用基础后缀数组实现树，后缀树就是“正确且简单的方法”。
Kim，Park和Kim的论文描述了Abouelhoda等人误导性论文中的一种变体方法：用增强后缀数组替换后缀树。 Kim等人的论文认为这是后缀树的实现 ，而不是替代 。 此外，Abouelhoda等人的构造细节在Kim等人的论文中更简单和直观地描述。
，
这里有一个Ukkonen线性构建后缀树（加后缀数组，lcp数组）的实现：http：//code.google.com/p/text-indexing/。 与suffixtree.js一起提供的可视化可能会有所帮助
链接地址: http://www.djcxy.com/p/40083.html