后缀数组 vs 后缀树

Question

后缀数组 vs 后缀树

algorithmtime-complexitysuffix-treespace-complexitysuffix-array

17

我只是想知道，在何时后缀树比增强型后缀数组更优。

在阅读了Replacing sufﬁx trees with enhanced sufﬁx arrays之后，我不再看到使用后缀树的理由。有些方法可能会变得复杂，但你可以用一个后缀数组做到与使用后缀树相同的操作，且时间复杂度相同但占用更少的内存。

甚至有一项调查表明，后缀数组速度更快，因为它们更加友好缓存并且产生的缓存未命中比后缀树少（所以缓存可以更好地预测数组的使用情况，然后递归树结构）。

那么，是否有人知道在何时选择后缀树而不是后缀数组呢？

编辑好吧，如果你知道更多，请告诉我，目前有：

后缀数组不允许在线构建
某些模式匹配算法在后缀树上运行得更快
(附加)由于可以在线构建，因此可以将其保存在硬盘上并扩展现有的后缀树。如果使用SSD，速度也应该很快。

- Nicolas

只是猜测，但实际实现中后缀树可能在内存方面更小。 - Justin

1

@Justin：实际上，增强后缀数组消耗更少的内存，这正是链接论文所讨论的内容。 - Niklas B.

嗯，我不知道。如果我将Ukkonen的后缀树构造与线性时间的后缀数组构造进行比较，我认为它并不更容易。而且，如果你只看最简单的构造方式，那么排序后缀列表比将它们排列成树更容易理解，对吧？ - Nicolas

可能是因为增强后缀数组的复杂性吗？我们都是人类，许多程序员懒得学习新算法，如果需要阅读一份密集的35页文档。我只是在反思自己，因为我花了很多时间研究后缀树，犯了一个错误并实现了错误的数据结构，最终理解了Ukkonen的算法（我希望...）。然后我打开了增强后缀数组论文，意识到我需要学习的东西还有多少（可能超过一天的阅读/学习/编码时间 - 不包括我的先前研究）。 - Sergiy Migdalskiy

2个回答

-3

另一个例子展示后缀树的优越性：

如果你已经有了一个后缀树，那么你可以很容易地构建一个后缀数组。

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

- lavin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rlinden · Accepted Answer

在SO本身上有一些有趣的想法，关于这个主题。您还可以在线找到更多技术材料。还有另一篇论文可能会帮助您解决问题，声称是实现这些结构的另一种有效方式。

我不是这个问题的专家，但我觉得后缀数组可能会慢一些，尽管它们更节省空间。然而，我缺乏实际经验，无法更详细地说明它们两者的区别。