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

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

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

参考文献

2009/07/03 Burrows-Wheeler Transform | | コメント (0) | トラックバック (0)

IS法 その5

saisとsais-liteを更新。BWTとOpenMP用のコードを追加しました。これでマルチCPUやマルチコアCPUを搭載したマシンならSuffix arrayの構築時間が少し短縮できる・・かもしれません。

CMake version

File: sais-lite.zip
Size: 13,154 bytes
SHA1: 904f22769fbc974f6b49c9f38d0cb38b9091cb89

CMake version

File: sais.zip
Size: 26,620 bytes
SHA1: c21bc6f1d3ece5485fb05604ca4bfaee388a73ab

あと、Java言語版を作ってみました。さすがにC言語版より遅いけど、とりあえずちゃんと動作します。

Java language version

File: sais-java.zip
Size:  9,955 bytes
SHA1: b5b88324eabf5f308abd5704309ce981c5bc081f

2009/01/10 Suffix Array | | コメント (0) | トラックバック (0)

TXTCache

なにやらTXTCacheというJava言語で書かれた圧縮インデックスライブラリがリリースされている。中身は・・、Pizza&Chili Corpusのソースコードを移植したものみたいですね。

2008/11/19 Suffix Array | | コメント (0) | トラックバック (0)

2.0.0

libdivsufsort-2.0.0 とその簡易版 libdivsufsort-lite を公開しました。

version 1.2.3 からの変更点は以下のとおりです。

  • ベースを itssort_0080412 に変更。
    • 一部OpenMPに対応。
    • 常に先頭に配置される終端記号のインデックスを Suffixarray から除外。
  • 64ビットのインデックスに対応。(CMakeのみ)
  • 性能がほんの少し向上。
  
File: libdivsufsort-2.0.0.tar.bz2
Size: 252,912 bytes
SHA1: 168bac570726619409d05814ac1c9ab14a248dc4
  
File: libdivsufsort-lite.zip
Size:  21,348 bytes
SHA1: 6068f9571a9b15831082b8dccfc005cee7b47956

2.0.0は、SVNのものと違って configure などのファイルも含まれているので、CMakeが無い環境でもビルドは可能です。簡易版は、ライブラリのビルドが面倒な人向けのパッケージです。divsufsort.cと.hをそのままコピーして使っちゃって下さい。

追記: divbwtのバグと ChangeLog を修正するのを忘れてました・・。そのうち直します。

追記そのに: こっそり修正しました。

2008/08/23 Suffix Array | | コメント (5) | トラックバック (0)

«IS法 その4