« 確率と識別 | Main | 午後からの日々 »

2005.02.18

SA

ちょっと、目を離すと研究はあっという間に進むもので、Suffix Arraysも去年まとめて書いたころとはかなり状況が変わっているみたい。

yuuさんのページがSuffix Arraysに関して、この一年でかなり充実してきて、すばらしい。いろいろな手法の比較検討もしているし。ただ、線形時間のやつは速くないってのはもうちょっと工夫すれば使えると思う。教えてもらったことではあるが、mod3で分ける方法とかは途中で普通のSA構築アルゴリズムに切り替えれば結構速く使える。100Mとか超えてくると差がちゃんとでてきそう。

結局、二段階ソート(それをさらに儘田さんが発展させたやつ)と線形ソートはどっちが速いんだろう。アルファベットサイズによるといわれればそれまでだが、これが最強ってないのかなぁ。メモリ量も問題になるけど。

まぁ、構築するのは一回だけだから、実用的にはそんなに問題にならないんだろうけどねぇ。それよりは利用する際のメモリ、速度のほうが問題なんだろうなぁ。でも、構築は奥が深くて面白い。

|

« 確率と識別 | Main | 午後からの日々 »

Comments

S.J.Puglisi, The Perfomance of Linear Time Suffix Sorting Algorithm. DCC2005, pp.358-376.
は御覧になりましたか?
Ko-Aluru, Karkkainen-Sanders, Larsson-Sadakane, Karkkainen-Burkhardt, Manzini-Ferragina の手法を比較しています。
これを見ると、やはりというかMFが一番速くてかつ省メモリであり、O(n)手法はまだまだなのかなぁ、と思わされます。

なお、私の三分割法(俗称)は、正式な論文にするため、現在執筆中です。
ただ、いろいろな人の改良案がすでにあるため、記述に苦労しております。

Posted by: S | 2005.02.18 at 07:37 AM

どうもありがとうございます。

これは、まだ見てません。作者のページには公開されていないようなのですが、DCC2005の論文はもう公開されているのかな。自分もポスター出しているはずなのにわからない・・。調べてみます。

MFが強いってのは予想していたとはいえ、ちょっとがっかりな。すごい大きいデータに対してもそうなんでしょうかね。

今日は数百MBのデータを圧縮しようとしてbzip使ったときに結構時間かかったので、まだまだSA構築の高速化は必要だなと思いました(笑)

インクリメンタルなSA構築はいくつか知っているのですが、データの部分挿入、削除などを行った場合のSA再構築の効率よいアルゴリズムはまだ知られてませんよね?

Posted by: oka | 2005.02.20 at 02:25 AM

ありました。これですね。
http://www.computing.edu.au/~smyth/pst.ps

この結果をみるとやはり2段階ソートやその変種と比べたくなりますね。

Posted by: oka | 2005.03.01 at 10:48 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/2978447

Listed below are links to weblogs that reference SA:

« 確率と識別 | Main | 午後からの日々 »