Kan-Ru Chen's Weblog

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 秒內建完樹並回報內部節點個數。

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