ウェーブレット木でできることはウェーブレット行列でもできる

ウェーブレット行列のテスト実装に、rank(), select() の他、wat-array で実装されているものをだいたい追加しました。ウェーブレット木でできることは、ウェーブレット行列でも同じようにできる（元論文の最後にちゃんとそう書いてある）ということが確認できました。

なぜ可能なのかというと、ウェーブレット行列でもウェーブレット木のブロックがそのまま保たれているからです。

例として、11, 0, 15, 6, 5, 2, 7, 12, 11, 0, 12, 12, 13, 4, 6, 13, 1, 11, 6, 1, 7, 10, 2, 7, 14, 11, 1, 7, 5, 4, 14, 6 という配列に対してウェーブレット木とウェーブレット行列を作ることを考えます。

まず、ウェーブレット木の場合から見てみます。

初めに、最上位ビットが 0 か 1 かを調べて、その配列を作ります。また、配列を左から見て、順番を保ったままで最上位ビットが 0 のものを左にまとめ、1 のものを右にまとめます。ここでは、それぞれをブロックと呼ぶことにします。

次に、それぞれのブロックの中で、上から 2番目のビットが 0 か 1 かを調べて、その配列を作ります。また、それぞれのブロックを左から見て、順番を保ったままで上から 2番目のビットが 0 のものをブロック内で左に寄せ、1のものを右に寄せ、それぞれ別のブロックとします。ブロックは 4つになります。

同じように、3番目のビットについても同じことをします。上から 3番目（下から 2番目）のビットの配列を作り、それぞれのブロックを左から見て、上から 3番目（下から 2番目）のビットが 0 のものをブロック内で左に寄せて、1 のものを右に寄せます。ブロックは 8つになります（この例ではたまたま 8・9 がないので、そのブロックは空です）。

最後に、最下位ビットについても同じことをすると、それぞれの数字が 1つのブロックになります。また、その結果としてできる配列の中では、数字はすべてソートされています。

この時、数字の配列は保存せず、ビットの配列のみを保存しておくことになります。また、それぞれの段階でブロック境界を記憶します。

次に、ウェーブレット行列の場合です。

初めに、最上位ビットが 0 か 1 かを調べて、その配列を作ります。また、配列を左から見て、順番を保ったままで、最上位ビットが 0 のものを左にまとめ、1 のものを右にまとめます。ここまでは、ウェーブレット木の場合と同じです。

次に、配列全体を左から見て、上から 2番目のビットが 0 か 1 かを調べて、その配列を作ります。また、配列全体を左から見て、順番を保ったままで上から 2番目のビットが 0 のものを左に寄せ、1 のものを右に寄せます。

この時、ウェーブレット木の場合とは違い、前段階でのブロックについては考えないのですが、順番を保ったまま操作しているので、前段階でブロックの左にあったものと右にあったものが混ざることはありません。この図で、1 と 11 の間と、6 と 15 の間が、前段階でのブロック境界に対応しています。11 と 6 の間の境界は、この段階で新しくできたものです。

ここで、上の図をウェーブレット木の場合と比べてみます。場所が違うだけで、同じブロックができているのがわかります。

3番目のビットについても同じことをします。上から 3番目（下から 2番目）のビットが 0 か 1 かを調べて、その配列を作ります。また、配列全体を左から見て、順番を保ったままで上から 3番目（下から 2番目）のビットが 0 のものを左に寄せ、1 のものを右に寄せます。

もう一度、ウェーブレット木のブロックと比べてみます。下がウェーブレット木です。

最後に、最下位ビットについても同じことをすると、それぞれの数字が 1つのブロックになります。

最後に残る数字列（0, 0, 4, 4, 12, 12, 12, 2, 2, ...）は、ビットの順番（上位・下位）を逆転にすると、その順番でソートされていることがわかります（0, 0, 2, 2, 3, 3, 3, 4, 4, ...）。ビットを逆転させた数字を添えると次のようになります。

ウェーブレット行列を作る時には、上のビットから順番に基数ソートをしていることになります。それで、結果がビットを逆転させた数字の順番に並ぶことになります。それぞれの数字に対する最後の配列でのインデックスを覚えておくことで、rank() や select() で各ビット列に対する操作を減らすことができます。

例として、この配列の中で、「インデックス 22 より左に "11" はいくつあるか」（rank）を調べる手順を見てみます。

下の図で赤線を引いた位置が、検索位置であるインデックス 22 です。まず、"11" の最上位ビットは "1" なので、赤線より左に "1" がいくつあるか調べます。答えは 10 個です。

次に、この境界が次の配列ではどこにあたるかを計算します。今回、"0" と "1" の境界線はインデックス 19（下の図で青線を引いた位置）で、ここから最上位ビットが "1" のものが始まります。そこから右に 10個（前段階で赤線より左にあったものの中で、最上位ビットが "1" のものの数）数えたところ、つまりインデックス 29（下の図で赤線を引いた位置）が、この段階で検索位置に対応することになります。

"11" の上から 2番目のビットは "0" なので、配列全体の中で、赤線より左に "0" がいくつあるか調べます。答えは 11個です。

今回はビットが "0" であるため、次の配列ではインデックス 11 が検索位置になります。下の図で赤線を引いてあります。"11" の上から 3番目のビットは "1" であるため、ビット列全体の中で赤線より左にある "1" の数を調べます。答えは 6個です。

前段階でのビットが "1" だったため、次の配列での検索位置は、0-1 境界であるインデックス 14（青線の位置）から右に 6個ずらしたところ、つまりインデックス 20 になります。"11" の最下位ビットは "1" なので、配列全体の中で赤線より左にある "1" の数を調べます。答えは 10個です。