algorithm - 后缀数组与后缀树

Question

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

看完Replacing suffix trees with enhanced suffix arrays我看不出有理由再使用后缀树了。有些方法可能会变得复杂，但您可以使用后缀数组来完成所有操作，您可以使用后缀树来完成所有操作，并且您需要相同的时间复杂度但需要更少的内存。

A survey甚至表明，后缀数组更快，因为它们对缓存更友好，并且不会产生那么多的缓存未命中，然后是后缀树(因此缓存可以更好地预测数组的使用，然后在递归树结构上)。

那么，有人知道选择后缀树而不是后缀数组的原因吗？

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

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

Answer 1

有一些interesting thoughts关于SO本身的主题。您还可以找到 more technical material在线提供。有 another paper这可能会帮助您解决问题，声称是实现这些结构的另一种有效方式。

我不是这个问题的专家，但在我看来，后缀数组可能会稍微慢一些，尽管它们的空间效率更高。尽管如此，我缺乏对它们两者更详细的实践经验。