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

Binary Indexed Treeの二分探索処理

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

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

| | コメント (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)

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