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などよりも高速に処理できることが多いです。

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

bwte

まだアルファ版みたいですが、bwteの論文とそのソースコードが公開されています。外部記憶装置を利用して大規模ファイルのBW変換を直接行うことができるとのこと。

URL: http://people.unipmn.it/manzini/bwtdisk/

サフィックスソート用の文字列を作るのにKMPを使うとは・・おもしろいねぇ。ちなみに入力文字列を逆転させて処理しているので、出力されるBWTは普通のとは違います。FM-indexにとっては都合が良いのかな。

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

libdbwt-0.3.0

こっそり更新。。

"Dynamic Extended Suffix Arrays" という論文に書かれているアルゴリズムがなかなかおもしろかったので、4年ほど前の Dynamic Wavelet Tree を書き直して実装、簡単なライブラリを作ってみました。とりあえず、BWT・Suffix Array・Inverse Suffix Arrayの動的更新が可能になってます。・・遅いけどね。

File: libdbwt-0.3.0
Size: 47,561 bytes
SHA1: 747f8aa9f2eeaf5a6769bfe478a4f2dd0a75af92

かなり適当に作ったので、まだバグやコンパイルできない環境があるかもしれない。

=====================

参考文献

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

bzip2のブロックソート高速化パッチ

  File: blocksort.c.diff.gz
  Size: 16231 bytes
   MD5: cc5677ffec496c55bc0bfd91ea2f8788

こっそりと公開してみる。一応、簡単なテストはしたけど、まだバグがあるかもしれないのでご注意を・・。ちなみに、ソートアルゴリズムには、bzip2用のdivsufsort-1.2.1を使用しております。

追記: パッチファイルを少し修正しました。

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

Improved Two-Stage Sort その3

MSufSort3 の Semidirect な BWT アルゴリズムを実装した「itssort_070210」を公開しました。

この Semidirect BWT は、 ITS Sort の 2nd ステージ時に BWTed string を Suffix array の代わりに構築するシンプルで無駄の無いアルゴリズムのため、普通の Suffixsort + BWT よりも高速に処理を行うことができます。

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

一応

Manzini's Corpusを用いて、ibwtの実行時間を計ってみました。メモリの使用量を考えれば決して悪い結果ではなかったけど・・

実行時間 (計測回数: 3回、単位: 秒)
FileNameFileSizedssort+bwtibwt (m=n/32)qsufsort+bwt
total8968190391849.164490.813480.54
chr22.dna3455375851.4680.2472.39
etext99105277340215.28573.61442.50
gcc-3.0.tar86630400146.65398.78248.57
howto3942210551.83168.98108.63
jdk13c69728899214.97348.15270.93
linux-2.4.5.tar116254720151.14553.18362.70
rctail96114711151370.20638.49536.59
rfc116421901181.11561.61460.61
sprot34.dat109617186216.99579.99445.12
w3c2104201579249.53587.78532.50

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

ibwt の高速化 その2

qsufsort よりは少し遅いですが、まあそれなりに高速で省メモリな ibwt がようやく完成。 ibwt-0.2.6a.tar.bz2 Wavelet Tree を構築する時の必要なスペースは 約 1.125nH0 + 73m bits (mはブロックサイズ) です。・・んー、まだ多いですかねえ。

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

w/o sentinel その2

sentinel 無しの divsufsort を更新。ベースを1.0.1にして、二カ所ほどあったバグを修正しました。libdivsufsort_wos-1.0.1.tar.bz2

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

w/o sentinel

sentinel 無しの BW変換用 divsufsort を作ることは可能ですか? というメールがあったので、ひっそり作ってみる。libdivsufsort_wos-0.2.1.tar.gz

これなら sentinel 有りとたいして変わらない速度で、オリジナル(BW94)のものと同じ BWTed Strings が作れるはずです。

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

ibwt の高速化

0.1.3a よりも (たぶん)高速な ibwt を実装中。。 ibwt-0.2.1a.tar.bz2

今回から、Static な Wavelet Tree に文字を n/v ずつ追加する方法に変更してます。 ("Constructing Compressed Suffix Arrays with Large Alphabets" の Incremental CSA とほぼ同じ方法)

こっそり Canonical Huffman 符号を作ってみる

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

より以前の記事一覧