ウェーブレット木を習得したのでメモしておくよ
ウェーブレット木を習得したので忘れないうちにメモ。
まずウェーブレット木の目的は文字列に対してrank()、select()を可能にすること。select()はrank()の逆関数で二分探索によって実装できるので、以下rank()についてのみ考える。
rank(pos, 1)はビットベクトルに対して定義される関数で、先頭のpos個で1のビットの個数を数えるというもの。rank(pos, 0)なら0のビットを数える。例えば
ビットベクトル:10110010 rank(1,1) = 1 rank(5,1) = 3 rank(2,1) = 1 rank(6,1) = 3 rank(3,1) = 2 rank(7,1) = 4 rank(4,1) = 3 rank(8,1) = 4
となる。で、この操作を文字列に拡張したい。例えば
文字列:banana rank(1,a) = 0 rank(4,a) = 2 rank(2,a) = 1 rank(5,a) = 2 rank(3,a) = 1 rank(6,a) = 3
ということがしたい。これを実現するためには文字列を、それぞれの文字chに付いて、chなら0、そうでないなら1としてビットベクトルをつくる。このとき既にビットベクトルを作った文字chは文字列から逐次除外していく。どういうことかというと
文字列:banana aのビットベクトル:101010 aを除いた文字列:bnn bのビットベクトル:011 aとbを除いた文字列:nn nのビットベクトル:00
というものを作る。これに対してrank()を考える。まずrank(pos,a)は最初の「aのビットベクトル」に対してrank(pos,0)をすれば良い。以下、「文字chのビットベクトルに対するrank()」をrank_ch()と書く。
rank(pos,b)について。rank_a(pos,1)をすることでposから「bのビットベクトル」上の位置を得ることができるので(bのビットベクトルはaのビットベクトルから0を除いたものなので)、rank_b(rank_a(pos,1),0)をすることでrank(pos,b)を得ることができる。
以下同様に、rank()の値を得ることができる。
見てわかるとおり、深い位置にある文字chほど値を得るのに時間がかかるし、必要なビット数も増える(ビットベクトルを作ったchは除くので、早い段階で出現数の多い文字が除かれたほうが必要なビット数が減る)。よって頻出する文字ほど上に来るように並べ替える。
a:3回 n:2回 b:1回 文字列:banana aのビットベクトル:101010 aを除いた文字列:bnn nのビットベクトル:100 aとnを除いた文字列:b bのビットベクトル:0
となる。この考えをもうちょっと進めてビットベクトルをHaffman木のノードとして扱ったものがウェーブレット木。Haffman木は二分木の一種で、頻度の大きいノード(ビットベクトル)ほどルートノードから近い位置にくるようにしたもの。Haffman木の構築はグリーディアルゴリズムで解くことができる。詳細はWikipedia等を参考に。
