20

我一直在寻找有关后缀树的教程很长一段时间。在 SO 中，我发现了 2 篇关于理解后缀树的帖子：1、2。

但我不能说我了解如何构建一个，哎呀。在 Skiena 的《算法设计手册》一书中，他说：

由于线性时间后缀树构造算法很重要，我建议使用现有的实现。

那么，后缀树的在线构造算法有那么难吗？任何人都可以让我朝着正确的方向理解它吗？

无论如何，切入正题，除了构造之外，关于后缀树还有一件事我不明白。因为后缀树中的边只是一对整数（对吗？）指定子字符串的开始和结束位置，那么如果我想x在这个后缀树中搜索一个字符串，我应该怎么做呢？取消引用后缀树中的那些整数，然后将它们与x? 不可能是这样的。

4

3 回答 3

21

首先，有很多方法可以构建后缀树。有 Weiner (1973) 的原始 O(n) 方法，McCreight (1976) 改进的方法，Ukkonen (1991/1992) 最著名的方法，以及许多进一步的改进，主要与实现和存储有关效率考虑。其中最值得注意的可能是Giegerich 和 Kurtz的惰性后缀树的有效实现。

此外，由于在 2003 年可以在 O(n) 时间内直接构造后缀数组（例如，使用Skew 算法，但也有其他算法），并且由于有经过充分研究的方法

后缀数组通常比后缀树更受欢迎。因此，如果您打算为特定目的构建高度优化的实现，您可能需要研究研究后缀数组构造算法。

但是，如果您对后缀树构造感兴趣，尤其是 Ukkonen 算法，我建议您仔细查看您已经提到的这篇 SO 帖子中的描述，我们会尝试一起改进该描述. 这当然远不是一个完美直观的解释。

回答关于如何将输入字符串与边标签进行比较的问题：出于构建和查找过程中的效率原因，每个边标签的初始字符通常存储在节点中。但是其余的必须在主文本字符串中查找，就像你说的那样，这确实会导致问题，特别是当字符串太大以至于不能轻易保存在内存中时。那（再加上一个事实，就像任何直接实现树一样，后缀树是一个包含大量指针的数据结构，这些指针消耗大量内存并使其难以维护引用的局部性并从内存缓存中受益）是后缀树比倒排索引更难处理的主要原因之一。

于 2012-03-05T02:45:34.860 回答
5

如果您将后缀数组与lcp table和child table结合起来，当然您应该这样做，那么您基本上会得到一个后缀树。这一点在论文中提出：Kim、Park 和 Kim 的 Linearized Suffix Trees。lcp 表实现了一种相当尴尬的自下而上的遍历，而 child 表实现了任何一种简单的遍历。因此，在我看来，关于使用指针导致引用问题的局部性的后缀树的故事是过时的信息。因此，后缀树是“正确且简单的方法”，只要您使用底层后缀数组来实现树。

Kim、Park 和 Kim 的论文描述了 Abouelhoda 等人在题为误导性的论文中的一种变体：用增强的后缀数组替换后缀树。Kim 等人的论文认为这是后缀树的实现，而不是替代. 此外，Abouelhoda 等人的构造细节在 Kim 等人的描述中更加简单直观。

,

于 2012-03-10T12:10:52.360 回答
0

这里有一个 Ukkonen 的后缀树（加上后缀数组，lcp 数组）的线性构造的实现：http ://code.google.com/p/text-indexing/ 。与 suffixtree.js 一起提供的可视化可能会有所帮助

于 2013-11-06T00:05:15.860 回答