ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"

計算機科学

久しぶりに論文を読んだ。

"The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。
機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。


これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文のAlgorithm 2)があった。
Standard Wavelet Treeは空間効率が良くないのでウェーブレット木を実装する場合はLevelwise Wavelet Treeを用いることが多かった(私の実装したShellinford(http://code.google.com/p/shellinford/)もLevelwiseを用いている)。
とはいえLevelwise Wavelet Treeはaccess,rank,selectの操作がやや複雑になってしまうし、あまり速くないなど気になる点もあった。


そこで本論文では既存手法より高速で実装もシンプルな新手法(The Wavelet Matrix. 論文のAlgorithm 3)を提案している。論文のAlgorithmを見比べると他手法より単純になっているのがわかる。
The Wavelet Matrixはデータを階層ごとの配列で持たせている点はLevelwiseと同じ。異なるのはLevelwiseがあくまでノードの並びとして配列を表現しているのに対して、The Wavelet Matrixではウェーブレット木で言うところのノードを持たないという点が異なる(なのでTreeではなくMatrixとなっている)。


以下、The Wavelet Matrixの解説を行う。既存のウェーブレット木の知識は前提としないのでウェーブレット木を知らない人はかえってまっさらな状態でThe Wavelet Matrixを学んだほうがわかりやすいかもしれない。


まず論文のFig. 2.で使われている以下のデータ列を考える。

4 7 6 5 3 2 1 0 1 4 1 7

このデータ列をaccess,rank,selectが可能な形式に変形することを考える。rank,selectは簡潔ビットベクトルに対する演算なのでデータ列を複数のビット列で表現する事を考える。
まず各データとビット列の対応を考える。つまり

0 => 000
1 => 001
2 => 010
3 => 011
4 => 100
5 => 101
6 => 110
7 => 111

という対応を頭に置いておく。
まずは各ビット列の先頭ビットを使ってデータ列をビット列で表現する。つまり

データ列：4 7 6 5 3 2 1 0 1 4 1 7
ビット列：1 1 1 1 0 0 0 0 0 1 0 1

というビット列を作る。これが1本目のビット列となる。


次に2番めのビットを使ってビット列を作るのだが、このときビットの並べる順番に工夫をする必要がある。まずは先頭ビットが0だったデータについてだけ2番めのビットを並べる。つまり

データ列： 3 2 1 0 1 1
ビット列： 1 1 0 0 0 0

というビット列を作る。次に先頭ビットが1だったデータについても同じ事を行う。つまり

データ列： 4 7 6 5 4 7
ビット列： 0 1 1 0 0 1

というビット列を作る。そしてこの2つのビット列をくっつける。

データ列： 3 2 1 0 1 1 || 4 7 6 5 4 7
ビット列： 1 1 0 0 0 0 || 0 1 1 0 0 1

これが2本目のビット列となる(||はわかりやすさのために入れたが特に意味は無い)。


次に3番目のビットを使ってビット列を作る。これも2本目のときと同様にまずは2番目のビットが0だったデータについてだけビットを並べる。つまり

データ列： 1 0 1 1 4 5 4
ビット列： 1 0 1 1 0 1 0

となる。同様に2番目のビットが1だったデータについても

データ列： 3 2 7 6 7
ビット列： 1 0 1 0 1

となる。これらをくっつけて

データ列： 1 0 1 1 4 5 4 || 3 2 7 6 7
ビット列： 1 0 1 1 0 1 0 || 1 0 1 0 1

というビット列を作る。これが3本めのビット列となる。


これらの3本のビット列を並べて行列にする。

データ列：4 7 6 5 3 2 1 0 1 4 1 7
ビット列：1 1 1 1 0 0 0 0 0 1 0 1

データ列： 3 2 1 0 1 1 || 4 7 6 5 4 7
ビット列： 1 1 0 0 0 0 || 0 1 1 0 0 1

データ列： 1 0 1 1 4 5 4 || 3 2 7 6 7
ビット列： 1 0 1 1 0 1 0 || 1 0 1 0 1


行列：
1 1 1 1 0 0 0 0 0 1 0 1
1 1 0 0 0 0 0 1 1 0 0 1
1 0 1 1 0 1 0 1 0 1 0 1

この行列がThe Wavelet Matrix(ウェーブレット行列？)とよばれる。ウェーブレット木の実装を知っている人は単純すぎて驚いたのでは。


さて、このデータ構造についてどうやってaccess,rank,selectを実行するのか。
rankのやり方がわかれば他もわかると思うので(ぶっちゃけめんどくさいので)rankだけ説明する。
例としてrank(4, 10)(データ列の0を先頭として10番目より前に出現する4の回数)を計算する。
まず4はビット列で100なので先頭ビットは1となる。よって1本目のビット列に対してrank1(1, 10)を計算する(以降、N本目のビット列に対するrankを便宜上rankNと表現する)。これはビット列が簡潔ビットベクトルとして実装されていれば定数時間で計算できる。
rank1(1, 10)=5なので10番目より前に先頭ビットが1のデータは5件あることがわかる。
ここで先頭ビットが1のデータは2本目のビット列の後半にくっつけたことを思い出す。すると「1本目のビット列で10番目より前にある先頭がビットが1のデータ」は「2本目のビット列の5番目より前に集まっている」ことがわかる。図で説明すると

データ列：[4] [7] [6] [5] 3 2 1 0 1 [4] 1 7
ビット列：[1] [1] [1] [1] 0 0 0 0 0 [1] 0 1

データ列： 3 2 1 0 1 1 || [4] [7] [6] [5] [4] 7
ビット列： 1 1 0 0 0 0 || [0] [1] [1] [0] [0] 1

のように角括弧で囲ったデータが問題のデータとなる。
ということは次は2本目のビット列で角括弧で囲まれているデータから4の出現回数を計算すれば良いことになる。4の2ビット目は0なので角括弧データに対して0の出現回数を計算する。
最初に角括弧で囲まれたデータの前には先頭ビットが1のデータが並んでいるので1本目のビット列に対してrank1(0, 12)=6と計算すれば角括弧データの開始位置がわかる。よって2本目のビット列に対してrank2(0, 5 + 6) - rank2(0, 6) = 3なので角括弧データ中の0の数が3個だとわかる。


最後に4の最後のビットは0なので3本目のビット列の「ある範囲」から0の出現回数を計算すれば無事に元のデータ列での4の出現回数がわかるのだが「ある範囲」というのを充分に考える必要がある。
3本目のビット列の前半には2本目のビット列で値が0だったデータが集まっている。

データ列： 3 2 (1) (0) (1) (1) || [4] 7 6 [5] [4] 7
ビット列： 1 1 (0) (0) (0) (0) || [0] 1 1 [0] [0] 1

データ列： (1) (0) (1) (1) [4] [5] [4] || 3 2 7 6 7
ビット列： (1) (0) (1) (1) [0] [1] [0] || 1 0 1 0 1

この「2本目のビット列で値が0だったデータ」には2本目のビット列で注目する必要のない前半のデータぶんも含まれている(丸括弧で示したデータ)。なのでこのぶんのカウントを減らしたい。それには2本目のビット列の前半での0の出現回数がわかれば良い。
これはrank2(0, 6)=4としてすぐに計算できる。よって3本目のビット列に対してrank3(0, 3 + 4) - rank3(0, 4) = 2なので角括弧データ中の0の数が2個だとわかる。
よって最初に求めたかったrank(4, 10)=2が無事得られた。


以上。もっと単純に説明できそうな気がするが今日読んだばかりなのでやや冗長になってしまったかもしれない。