Wavelet Matrix のテスト実装

えちぜんさんによる Wavelet Matrixの紹介記事を読んで、これはすごいと感銘を受けたので、試しに Python で実装してみた。

https://github.com/hiroshi-manabe/wavelet-matrix

(追記: wat-array を元にした C++https://github.com/hiroshi-manabe/wavelet-matrix-cpp も書きました。)

実装したのは rank() だけ*1

ここで使っているビットベクタはモックで、rank() の実行にサイズに対して線形の時間がかかるため、Wavelet Matrix も同じだけ時間がかかる。ビットベクタを定数のものに替えたら、こちらも定数(bit 数には比例するけど)でいけるはず。

理解するためにノートに実際の例を書いて手動ステップ実行して、それでやっと実装できた。

それにしても、Wavelet Tree はあんなに複雑だったのに、こんなに単純になるとは。

情報科学の進歩はすごい。


ぼくはなかなか論文を読まないので、えちぜんさんのようにわかりやすい紹介記事を書いてくれるのは本当にありがたいです。

(2012-08-03 追記: access() と select() も実装した。文字種ごとの数を保存して、ビットベクタに対する rank(), select() 操作を半分にした。)
(2012-08-07 追記: RankLessThan(), QuantileRange() も実装した。各レベルでのノード開始位置を記録して、RankLessThan() 等をレベルごとに 1回の rank() 呼び出しでできるようにした)

*1:追記したように、後からいろいろ加えています。