« sais-java & C# | トップページ | unbwt_5n »

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のフォルダへコピー)すると、ソート処理が入力されるデータによっては極端に遅くなる…などということは無くなりますが、通常のデータに対してはあまり効果がなかったり、逆に少し遅くなったりもするのでご注意を。

|

« sais-java & C# | トップページ | unbwt_5n »

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: cyclic suffix array:

« sais-java & C# | トップページ | unbwt_5n »