bwte

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

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

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

Binary Indexed Treeの二分探索処理

少し気になったので過去のコードを調べてみたんですが・・、修正するのをすっかり忘れていましたよ。bitreeのアルファベットサイズが2のn乗以外の場合は、探索の開始位置を変更しないと正しい値を返してくれません。

とりあえずC++に書き直した修正版bitreeを置いておきます。bitree.hxx

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

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

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

参考文献

• Mikaël Salson, Thierry Lecroq, Martine Léonard and Laurent Mouchard, Dynamic Burrows-Wheeler Transform, Proceedings of the Prague Stringology Conference, pp. 13-25, 2008.
  [http://www-igm.univ-mlv.fr/~lecroq/articles/psc2008-sllm.pdf]
  
• Mikaël Salson, Thierry Lecroq, Martine Léonard and Laurent Mouchard, A Four-Stage Algorithm for Updating a Burrows-Wheeler Transform, Theoretical Computer Science Special issue for Maxime Crochemore's 60th Birthday (accepted), [http://www-igm.univ-mlv.fr/~lecroq/articles/tcs2009.pdf]
  
• Mikaël Salson, Thierry Lecroq, Martine Léonard and Laurent Mouchard, Dynamic Extended Suffix Arrays, Journal of Discrete Algorithms (accepted), [http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009.pdf]
  

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