2

两个密切相关的数据结构是后缀树和后缀数组。根据我的阅读，后缀树比后缀数组更快、更强大、更灵活、内存效率更高。但是，在这个较早的问题中，最重要的答案之一提到后缀数组在实践中得到了更广泛的使用。我没有任何使用这些结构的经验，但现在对于需要它们提供的功能的问题（例如快速子字符串检查），我似乎总是更喜欢后缀树而不是后缀数组。

在什么情况下后缀数组比后缀树更可取？

（顺便说一下，虽然这个问题与我所链接的问题有关，但我认为这不是一个完全重复的问题，因为我只对后缀数组和后缀树的比较感兴趣，完全不考虑尝试. 但是，如果您不同意，我会理解这个问题是否要关闭。）

4

2 回答 2

3

引自http://www.youtube.com/watch?v=1DGZxd-PP7U

后缀数组和后缀树曾经是不同的。但是现在后缀数组只是实现后缀树的一种方式（反之亦然）。参见：Kim、Kim 和 Park。线性化后缀树：一种高效的索引数据结构，具有后缀树和后缀数组的能力。算法，2007。

Kim 等人的论文写得很好，易于理解，并引用了其他重要论文，例如 Abouelhoda 等人的论文。

于 2011-08-21T18:00:11.853 回答
2

后缀数组几乎总是可取的，除了：

  • 如果您要索引少量数据。
  • 如果您正在研究蛋白质匹配或 dna 突变并且可以使用极其昂贵的计算机。
  • 如果您必须不惜一切代价使用通配符的错误搜索。

后缀数组可用于实现后缀树。这意味着后缀树可以是一个后缀数组和一些额外的数据结构来模拟后缀树的功能。

所以：

  • 后缀数组使用更少的空间（少很多）
  • 后缀树的构建速度较慢
  • 后缀树进行模式匹配操作的速度更快
  • 后缀树可以做更多的操作，最好的是错误模式匹配通配符（后缀数组也做模式匹配但不使用通配符）

如果要索引大量数据，例如超过 50 兆字节。后缀树占用了太多空间，以至于您的计算机没有足够的内存将其保存在中央存储器中。因此它开始使用辅助内存，您会看到速度大幅下降。（例如，人类 dna 使用 700 MB，该数据的后缀树“可以”使用 40 GB -> *“可以”取决于实现 *）

因此，后缀树几乎从未在实践中使用过。在实践中，使用了后缀数组，并且小的附加数据结构为其提供了一些额外的功能（从来没有完整的后缀树）。

然而它们是不同的。在很多情况下，纯后缀数组更适合模式匹配，因为它具有高效的速度、快速的构建速度和低的空间使用率。

于 2012-06-19T17:16:27.123 回答