概念上簡單的線性時間後綴樹構造

1973年，韋納給出了第一個後綴樹的線性時間構造。該算法在1976年由McCreight簡化，在1995年由Ukkonen簡化。儘管如此，我從概念上找到了Ukkonen的算法。概念上簡單的線性時間後綴樹構造

自1995年以來是否對Ukkonen的算法進行了簡化？

2012-02-17 Randomblue

這不是一個直接的答案，但它可以幫助你。去年，在研究這個問題時，我使用了後綴數組而不是後綴樹，而IIRC則使用了「快速後綴數組構造的不兼容算法」KBSchürmann（2007）[1]作爲參考。 IIRC，它是一個建立後綴數組的雙通線性算法。

2012-02-17 16:09:29 Scharron

該算法經驗證明執行得非常好，但據我所知（並由作者陳述），它沒有被證明是線性複雜的。 – jogojapan 2012-02-18 13:29:43

哦，這是一種比較容易構建的折衷方案嗎？（正如我所說，一年前我讀過它:-)） – Scharron 2012-02-20 09:03:53

更直接的答案原來的問題是自頂向下（和懶惰）後綴樹結構由Giegerich，庫爾茨，Stoye：https://pub.uni-bielefeld.de/luur/download?func=downloadFile&recordOId=1610397&fileOId=2311132

另外，後綴陣列（正如前面的答案中所提到的）不僅更容易構建，而且可以增強它們以便模擬後綴樹中所期望的任何內容：http://www.daimi.au.dk/~cstorm/courses/StrAlg_e04/papers/KurtzOthers2004_EnhancedSuffixArrays.pdf

由於增強型後綴數組中涉及的數據結構可以是壓縮，壓縮（仿真）完成ix樹成爲可能：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8644&rep=rep1&type=pdf

2012-02-18 13:44:45 jogojapan

回答