« 2005年10月 | トップページ | 2006年1月 »

一応

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)

ピザ チリ

Pizza&Chili Corpus -- Compressed Indexes and their Testbeds という圧縮全文索引関連のサイトを発見。 今度 SA のベンチマークを取るときはここのコーパスも使ってみるかな。って 1GB のファイルもあるのかい・・。

linksCompressed Suffix Arrays and Suffix Trees に論文を追加しました。(LZ系を含む)様々な圧縮全文索引技術について書かれてあります。

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

w/o sentinel その2

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

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

1.0.1

libdivsufsort-1.0.1 を公開しました。ほんの少しだけソートが速くなってます。

あと、ベンチマーク結果の divsufsort と MSufSort を最新のバージョンに置き換えました。やはり、サイズの大きいファイルになると MSufSort-2.2 が圧倒的に速いですね・・。

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

« 2005年10月 | トップページ | 2006年1月 »