ウェーブレット行列を用いたFM-Indexを大幅に高速化した

なんかすごい高速化できた気がする。

今日は詳しく解説する気力がないので、気になる方はコードの差分をどうぞ。
簡単に言うとrankの先頭位置って実は持ってなくていいんじゃねっていうtakeda25さんがrank_less_thanの高速化で考えていたようなこと(http://d.hatena.ne.jp/takeda25/20120807/1344336237)をrankでやっただけ。FM-Indexはrank_less_thanは事前に計算しておけるので実行時はrankの速度だけが重要なので。

https://code.google.com/p/shellinford/source/diff?spec=svn22&r=22&format=side&path=/trunk/src/shellinford_wavelet_matrix.h

で肝心のデータサイズと速度はこんな感じ。

ウェーブレット行列: 5, 693, 256 byte
改良版: 5,694,432 byte

ウェーブレット行列:
$$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.shuf 

real	0m22.376s
user	0m22.328s
sys	0m0.045s


改良版:
$ time sample/search_fm_index var/zenkoku.key.fm_wm2 m y < var/zenkoku.shuf 

real	0m17.059s
user	0m17.012s
sys	0m0.041s

かなりいけてる気がするんだけどどうなんだろう。教えて詳しい人。