17

我只想知道,什么时候后缀树优于增强的后缀数组。

在阅读了用增强的后缀数组替换后缀树之后,我看不到使用后缀树的理由了。有些方法可能会变得复杂,但是您可以使用后缀数组来做所有事情,您可以使用后缀树来做任何事情,并且您需要相同的时间复杂度但更少的内存。

一项调查甚至表明,后缀数组更快,因为它们对缓存更友好,并且不会产生尽可能多的缓存未命中,然后是后缀树(因此缓存可以更好地预测数组使用情况,然后是递归树结构)。

那么,有谁知道选择后缀树而不是后缀数组的原因?

编辑 好的,如果您知道更多,请告诉我,到目前为止:

  • 后缀数组不允许在线构建
  • 一些模式匹配算法在后缀树上运行得更快
  • (补充)由于在线构建,您可以将其保存在 hd a 并扩大现有的后缀树。如果您使用 SSD,它也应该很快安静。
4

2 回答 2

1

SO 本身就这个主题有一些有趣的想法。您还可以在线找到更多可用的技术资料。还有另一篇论文可以帮助您解决问题,声称是实现这些结构的另一种有效方法。

我不是这个问题的专家,但在我看来,后缀数组可能会慢一些,即使它们更节省空间。尽管如此,我缺乏对他们两个更详细的实践经验。

于 2012-06-25T18:15:47.000 回答
-3

另一个证明后缀树优越的例子:

如果您已经有后缀树,则可以轻松构建后缀数组。

但是从后缀数组构造后缀树要复杂得多。

于 2012-08-03T14:34:25.653 回答