後綴數組優於後綴樹的位置？

Question

兩個緊密相關的數據結構是後綴樹和後綴數組。從我讀過的內容來看，後綴樹比後綴數組更快，更強大，更靈活，並且內存效率更高。但是，this earlier question,其中一個最佳答案提到後綴數組在實踐中更爲廣泛地使用。我沒有任何使用這些結構的經驗，但現在看來，我總是希望後綴樹比後綴數組更適合需要其提供的功能的問題（例如，快速子字符串檢查）。

在什麼情況下後綴數組可以優於後綴樹？ （順便說一句，雖然這個問題與我已經鏈接的問題有關，但我不認爲它是完全重複的，因爲我僅僅對後綴數組和後綴樹進行比較感興趣，完全離開了這些嘗試出來的圖片。如果您不同意，不過，我想，如果這個問題將被關閉理解。）

Answer 1

從http://www.youtube.com/watch?v=1DGZxd-PP7U

後綴數組引用和後綴樹曾經是不同的。但是現在 後綴數組只是一種實現後綴樹的方法（或者反之亦然 ）。請參閱：Kim，Kim和Park。線性後綴樹：有效的 索引數據結構，具有後綴樹和後綴 數組的功能。 Algorithmica，2007.

Kim等人的論文寫得很好，易於閱讀並且提及其他重要論文，例如Abouelhoda等人的論文。

Answer 2

後綴陣列幾乎總是最好，除了：

• 如果你要索引數據的小ammounts。
• 如果您正在研究蛋白質匹配或dna突變，並且可以訪問極其昂貴的計算機。
• 如果您必須不惜一切代價，請使用帶通配符的錯誤搜索。

後綴數組可用於實現後綴樹。含義後綴樹可以是後綴數組和一些額外的數據結構來模擬後綴樹功能。

因此：

• 後綴陣列使用更少的空間（少了很多）
• 後綴樹是慢打造
• 後綴樹正在做更快的模式匹配操作
• 後綴樹可以做更多操作時，最好的是使用通配符進行錯誤模式匹配（後綴數組也可以進行模式匹配但不包含通配符）

如果您想索引大量數據，例如超過50兆字節。後綴樹使用太多的空間，以至於您的計算機沒有足夠的內存來保存在中央內存中。因此它開始使用二級存儲器，你會看到速度的巨大降低。（例如，人類dna使用700兆字節，該數據的後綴樹「可以」使用40千兆字節 - > *「can」，具體取決於實施方式*）

由於這個原因，後綴樹在實踐中幾乎從未使用。在實踐中使用後綴數組，並且小的附加數據結構賦予它一些額外的功能（從不完整的後綴樹）。

然而它們是不同的。由於速度快，施工速度快和空間使用率低，因此很多情況下，純後綴陣列可用於模式匹配。