unbwt_5n

某フォーラムで公開する予定のものの一部をこちらにも置いておきます。中身は5nスペースのBW逆変換アルゴリズム四種(mergedTL・indexLF・unlimTLF・biPSI)。

File: unbwt_5n.zip
Size: 15,718 bytes
 MD5: a07a2f110dd8adc4a87b695f57db10bc
SHA1: 20ea0fe7618ae51c0a9727ae5a9714b47089582d

unlimTLFはmergedTLとindexLFを組み合わせたもので、LF mappingへマージ出来ないTの部分はbinary searchを用いて復号します。そのためmergedTLとは違い2**24より大きいデータでも処理が可能です。

最後のbiPSIは、PSI arrayを少し弄って一度に二文字ずつ復号出来るようにしたものです。逆変換で最も時間のかかる最後のループ処理でのPSI arrayへのランダムアクセスを約半分に減らせるので、入力データがある程度大きい場合、一文字ベースのmergedTLなどよりも高速に処理できることが多いです。

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#

ようやく、saisのJava版を更新しました。LMSsort2などは面倒なので実装していませんが、以前のバージョンよりは速くなっています。それとついでにC#版も公開。C#のコードを書いたのは初めてなので色々と適当なところはありますが、一応ちゃんと動作はするはず。

File: SAIS-CSharp.zip
Size: 29,875 bytes
SHA1: e1d52fb74c8551cb2881fc2ff3d92ad19a86db22

File: sais-java.zip
Size: 19,603 bytes
SHA1: 79828ab134408a8b414aa517a1885cebf43418fe

接尾辞配列の構築にかかる時間は、Windows上ではJavaよりC#の方がほんの少し速いです。まあどちらもC/C++と比べると倍近く遅いわけですが…。

sais-2.4.1

この間更新したばかりですが、新しいsais-2.4.1とsais-lite-2.4.1を公開しました。今回の変更点は、バグ修正・examplesのLFS対応・CMake周りの修正です。ついでに向こうのサイトも更新〜。

File: sais-lite-2.4.1.zip
Size: 17,097 bytes
SHA1: b3b7396da40022ed7dd7c19ffba81587020750c2

File: sais-2.4.1.zip
Size: 46,304 bytes
SHA1: cccf8d8bd18a893c58527d16ce6613923e22b411

これで暫くは更新しないと思います。Java版は…まあそのうちってことで。