« 2010年9月 | トップページ | 2010年11月 »

cyclic suffix array

cyclic-sais-1.0を公開〜。cyclic stringのsuffix arrayを構築できるsaisです。終端記号'$'を使用しない接尾辞?ソートといった方がわかりやすいかな。これでBW変換を行うと、オリジナルのBWT(BW94)やbzip2のソートとほぼ同じ結果が得られます。

File: cyclic-sais-1.0.zip
Size: 12,090 bytes
 MD5: acd653afbe8b6b6bf1a47f1787926f7d
SHA1: 5fb5bc7eabb04ffd157538f763e32bf84054a510

一応、bzip2-1.0.6のソートをcyclic-saisへ変更できるパッチが入っています。適用(blocksort.cとcyclic-sais.[c,h]をbzip2のフォルダへコピー)すると、ソート処理が入力されるデータによっては極端に遅くなる…などということは無くなりますが、通常のデータに対してはあまり効果がなかったり、逆に少し遅くなったりもするのでご注意を。

| | コメント (0) | トラックバック (0)

« 2010年9月 | トップページ | 2010年11月 »