後綴數組與後綴樹

Question

我只想知道，當後綴樹優於增強後綴數組。

看完Replacing suffix trees with enhanced suffix arrays我沒有看到再使用後綴樹的理由。有些方法可能會變得複雜，但您可以使用後綴數組完成所有工作，可以使用後綴樹執行什麼操作，並且需要相同的時間複雜性，但內存較少。

一個survey甚至表明，該後綴陣列的速度更快，因爲它們緩存友好的，並且不產生儘可能多的高速緩存未命中，那麼後綴樹（因此緩存能夠預測陣列的使用要好得多，然後在遞歸樹結構）。

那麼，有沒有人知道選擇一個後綴樹超過後綴數組的原因？

編輯 好吧，如果你知道更多的告訴我，至今它：

• Suffixarrays不要讓上線建設
• 一些模式匹配算法運行
• （加在Suffixtrees
快）由於在線建設，您可以將它保存在hd a上並放大現有的後綴樹。如果你使用SSD，它應該安靜快速。

Answer 1

有一些interesting thoughts在SO本身的主題。您也可以在網上找到more technical material。有another paper可能會幫助你解決你的問題，聲稱是實現這些結構的另一種有效方法。

我不是這個問題的專家，但在我看來後綴數組可能會稍微慢一些，即使它們更節省空間。儘管如此，我還是缺乏實踐經驗來更詳細地介紹兩者。

Answer 2

另一個例子表明，一個後綴樹優越：

您可以輕鬆地構建一個後綴數組，如果你有一個後綴樹了。

但是，從後綴數組構造後綴樹要複雜得多。