Suffix Tree

Suffix Tree，在字串處理上有非常多的應用，尤其是字串的搜尋、定位等等，利用這個資料結構很多都可以在 O(n) 也就是 linear time 做完。

這是在這學期的 字串學(stringology) 學到的，作業就是實做 suffix tree，我用的是 Ukkonen 的演算法，可以用 on-line construction 的方法建構 suffix tree。

我是用 Nemerle 寫的（因為在練習），後來也有用 C# 改了另外的版本，但是還是 Nemerle 的版本比較完整。原本是用 System.Collections.Generic.Dictionary 來存每個 State 裡面的 transitions，可是非常的吃記憶體，用 mono –profile 可以很容易看出來一個 500kb 的檔案，在建構的時候光 Dictionary 就可以吃掉近 150mb 的記憶體；後來改用自己的 linked list 來做，節省了很多資源，2mb 的測試檔可以在 9 秒內建完樹並回報內部節點個數。

整個程式應該還有多可以改進的地方，但是目前的效率作為作業已經可以接受了，先放上來。在這裡。

摘自：http://blog.kanru.info/archives/56