« Improved Two-Stage Sort その4 | トップページ | IS法 その1 »

New Linear SACAs: IS and DS

まだdraftだけど、新しいSuffix Array構築法に関する論文が公開されています。

タイトル通り、Suffix Arrayを線形時間で構築できる新しい二つのアルゴリズムについて、サンプルコード付きで解説されています。どちらのアルゴリズムもKA法より高速に動作して、なおかつ extra working space が最悪の場合でもわずか? 2.25n + O(1) bytes となかなかの性能のようです。

それにしてもIS法はすごいなぁ。(L)S-substringのソートをここまでコンパクトにするとは。。

|

« Improved Two-Stage Sort その4 | トップページ | IS法 その1 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/154471/41473696

この記事へのトラックバック一覧です: New Linear SACAs: IS and DS:

« Improved Two-Stage Sort その4 | トップページ | IS法 その1 »