ウェーブレット行列を用いたFM-Indexを大幅に高速化した - EchizenBlog-Zweiなんかすごい高速化できた気がする。 今日は詳しく解説する気力がないので、気になる方はコードの差分をどうぞ。 簡単に言うと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 で肝心のデータサイズと速度はこんな感じ。 ウェーブレッ
