New Linear SACAs: IS and DS
2008/06/04
まだdraftだけど、新しいSuffix Array構築法に関する論文が公開されています。
- Ge Nong, Sen Zhang and Wai Hong Chan, Two Efficient Algorithms for Linear Suffix Array Construction, 2008?.
[.pdf (http://www.cs.sysu.edu.cn)]
タイトル通り、Suffix Arrayを線形時間で構築できる新しい二つのアルゴリズムについて、サンプルコード付きで解説されています。どちらのアルゴリズムもKA法より高速に動作して、なおかつ extra working space が最悪の場合でもわずか? 2.25n + O(1) bytes となかなかの性能のようです。
それにしてもIS法はすごいなぁ。(L)S-substringのソートをここまでコンパクトにするとは。。