我只想知道,什么时候后缀树优于增强的后缀数组。
在阅读了用增强的后缀数组替换后缀树之后,我看不到使用后缀树的理由了。有些方法可能会变得复杂,但是您可以使用后缀数组来做所有事情,您可以使用后缀树来做任何事情,并且您需要相同的时间复杂度但更少的内存。
一项调查甚至表明,后缀数组更快,因为它们对缓存更友好,并且不会产生尽可能多的缓存未命中,然后是后缀树(因此缓存可以更好地预测数组使用情况,然后是递归树结构)。
那么,有谁知道选择后缀树而不是后缀数组的原因?
编辑 好的,如果您知道更多,请告诉我,到目前为止:
- 后缀数组不允许在线构建
- 一些模式匹配算法在后缀树上运行得更快
- (补充)由于在线构建,您可以将其保存在 hd a 并扩大现有的后缀树。如果您使用 SSD,它也应该很快安静。