中学生にもわかるウェーブレット行列
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。
…嘘です。
日本以外ではあんまり来ていません。
理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。
まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。
ウェーブレット行列でできること
主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。
rank() は、「文字列の先頭から位置 k までに、文字 x がいくつあるか」。
select()は、「文字列の先頭から見て、n 個目の文字 x の次の位置はどこか*3」。
それぞれ例を挙げます。
"abracadabra" という文字列（S とします）の中で、先頭から位置 8 までの間に、いくつ a があるか。
下の図で、先頭から矢印までの範囲の a を数えることになります。
実際に目で数えてみると、4 つあります。
つまり、rank(S, 8, "a") = 4ということになります *4。
また、この文字列の中で、2 個目の文字 b の次の位置はどこか。
下の図は、先頭から 2 個の b に色をつけたものです。
2 番目の b は位置 8 にあるので、その次である位置 9 が求めるものです。
つまり、select(S, 2, "b") = 9 ということになります*5。
先頭から順に数えるというやり方では、サイズが大きくなるとこれらの操作には長さに比例した時間がかかりますが、ウェーブレット行列*6を使うと、これらの操作が定数時間で可能になります。
位置づけ
ウェーブレット行列の重要な応用としては、FM-Indexというものがあります。
FM-Index というのは、圧縮した文字列から全文検索をすることができるデータ構造です。性質については @tb_yasu さんの FM-index++を公開しました、仕組みについては @echizen_tm さんのwat-arrayでラクラク実装☆FM-Indexの作り方で詳しく解説されています。
また、ウェーブレット行列の基礎となるデータ構造として、完備辞書*7というものがあります。
完備辞書というのは、ビット列に対する 定数時間の rank と select を可能にするデータ構造です。
つまり、ビット列の中で、先頭から位置 k までに 0 （または 1）がいくつあるか、また n 個目の 0（または 1）がどこにあるかということが定数時間でわかるということです。
完備辞書については、完備辞書（簡潔ビットベクトル）の解説という記事に書きましたので、興味があれば読んでみてください。
ウェーブレット行列の作り方
ウェーブレット行列は、元の文字列に対して上の桁から下の桁という順*8で基数ソートを行うような手順で作ります。
普通の基数ソートでは下の桁から上の桁に向かってソートするところですが、それが逆になるため、最終的にはビットの並びを逆にしたものの大小順に並ぶことになります。
実例を見てみます。
文字列は一般的には 8ビット（0〜255）の範囲の数値で表されることが多い*9のですが、ここでは簡単のため、4ビットで表せる 0〜15 ということにします。
対象とする文字列（数字列）は、ここでは次のようなものであるとします。
まずは、これを単純に上の桁から基数ソートする場合を考えてみます。
ものすごく冗長なので、基数ソートに慣れている人は飛ばしてください。
最初は、4 ビットで表した 2進数での最上位ビットに注目します。青く塗られたところが、最上位ビットが 1 のものです。
元の順序を保ったまま、最上位ビットが 0 のものを左に、1 のものを右に寄せます。
いったん色を元に戻すと、次のようになります。
次は、2進数で上から 2 番目のビットに注目します。青く塗られたところが、上から 2 番目のビットが 1 のものです。
元の順序を保ったまま、上から 2 番目のビットが 0 のものを左に、1 のものを右に寄せます。
色を元に戻すと、次のようになります。
今度は、2進数で上から 3 番目のビットに注目します。青く塗られたところが、上から 3 番目のビットが 1 のものです。
元の順序を保ったまま、上から 3 番目のビットが 0 のものを左に、1 のものを右に寄せます。
色を元に戻します。
最後に、2進数で上から 4 番目のビット、つまり最下位ビットに注目します。青く塗られたところが、最下位ビットが 1 のものです。
元の順序を保ったまま、最下位ビットが 0 のものを左に、1 のものを右に寄せます。
色を元に戻します。
この最後の数字列は、それぞれの数字のビットを逆転させたものの順番にソートされています。
重要なのは、数字ごとにブロックに分かれているというところです。
ウェーブレット行列では、基数ソートのそれぞれの段階で注目したビットの列だけを持っています。
この場合、実際に保存されるデータは次のようなものです。
これらのビット列に加えて、各段階での 0 の数（この場合は 19, 12, 14, 16）も保存しておきます。
ここで、ウェーブレット行列のデータを使って、実際に rank の計算をしてみます。
この配列の中で「インデックス 22 より左に "11" はいくつあるか」を調べることにします。
インデックス 22 というのは、下の図で矢印で表した位置です。
先頭からこの位置までの "11" の数を目で数えると、答えは次のように 3 個ということになります。
これを求めることが目的となります。
ウェーブレット行列の、最初のビット列を見てみます。
これは、元の数字列の最上位ビットを並べたものです。
ここで、理解のためにビット列に対応する元の数字列を下に薄く添えます（実際には保存していません）。
インデックス 22 は、矢印で示した位置です。
先頭からこの位置までの間に、検索対象である "11" と最上位ビットが同じもの、つまり最上位ビットが "1" であるものがいくつあるかを数えます。これは完備辞書であれば定数時間でできます。答えは、図からわかるように 10 個です。
ここで、この位置が上から 2 番目のビット列ではどこにあたるかを見てみます。
まず、数字列だけで見てみます。1 列目で矢印の左にあり、最上位ビットが 1 だった 10 個の数字は、2 列目では次のように固まっています。
このブロックの最後の位置が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットが "11" と同じである数字のブロックの終端位置」を表しています。
矢印をつけると次のようになります。
この位置は、太線で表した 0-1 境界（各段階での 0 の数を覚えているので、それを使います）から右に 10（1 列目で矢印の左にあり、最上位ビットが 1 だった数字の数）として計算できます。
上から 2 ビット目の列を、数字列の上に添えます。実際に持っているのはビット列のほうだけです。
先頭から矢印の位置までの間に、検索対象である "11" と上から 2 番目のビットが同じであるもの、つまり "0" であるものがいくつあるかを、完備辞書で数えます。
図のように、11 個あります。
これらに対応する数字列は、3 列目では図のように固まっています。
このブロックの終端位置が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットと上から 2 番目のビットが "11" と同じである数字のブロックの終端位置」となります*10。
上から 3 ビット目の列を、数字列の上に添えます。
先頭から矢印の位置までの間に、検索対象である "11" と上から 3 番目のビットが同じであるもの、つまり "1" であるものがいくつあるかを、完備辞書で数えます。
図のように、6 個あります。
これらに対応する数字列は、4 列目では図のように固まっています。これまでと同じように、このブロックの最後が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットから上から 3 番目までのビットが "11" と同じである数字のブロックの終端位置」となります。
最下位ビットの列を、数字列の上に添えます。
先頭から矢印の位置までの間に、検索対象である "11" と最下位ビットが同じであるもの、つまり "1" であるものがいくつあるかを、完備辞書で数えます。
図のように、10 個あります。
最終的にソートされた数字列（これも実際に持ってはいません）の中では、これらに対応する数字は図のように固まっています。
そして、矢印の位置が「最初の数字列でインデックス 22 より左にある "11" のブロックの終端位置」となります。
ここで、最後の数字列は、ひとつの数字がひとつのブロックになっています。データ作成時に、それぞれの開始位置を記憶しておくと、この場合 "11" のブロックの開始位置と「最初の数字列でインデックス 22 より左にある "11" のブロックの終端位置」との差分をとることで、求める数を知ることができます。
図でわかるように、答えは 3 になります。
このように、上の桁から基数ソートしたときのビット列と、それぞれの段階での 0 の数、それにソート済み数列中でのそれぞれの数字の開始位置を覚えておくことで、rank が行えるということがわかります。
この過程を逆にたどると、select になります。
また、RankLessThan() や QuantileRange() については、以前書いたものがありますので、そちらをご参照ください。
最近「ウェーブレット行列はコード書きやすいけど理解するのはウェーブレット木のほうが楽」というような意見を見たので、ウェーブレット行列難しくないよ！ というのを示すために書きました。
書いてみて…うーん、やっぱり難しいかも。
でも、「完備辞書」をブラックボックスとして受け入れると、ウェーブレット行列自体には 2 進数以外の知識は必要ないので、こういうタイトルにしてみました。
ところで、簡潔データ構造など高速文字列解析に役立ついろいろなトピックをまとめた本があります。
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)
posted with amazlet at 13.03.03
この本の中でもウェーブレット行列は取り上げられているのですが、この本の記述自体もなかなか簡潔なため、私のようにかなり冗長に考えないとなかなか理解できない人向けにと思ってこの記事を書きました。
*1:最初に触れたときにもこれをはじめとしたいくつかの記事を書いたのですが、興奮のためあまりわかりやすい記事が書けていないと思い直したため。
*2:rank_less_than などはとりあえず置いておきます。
*3:rank との対称性のために、直感的に少しわかりにくくなっています。
*4:引数は前から文字列、位置、検索文字です。
*5:引数は前から文字列、個数、検索文字です。
*6:いったんウェーブレット「木」のことは置いておきます。
*7:簡潔ビットベクトルとも。
*8:上の桁からというのは、後で出てくる RankLessThan といった関数の都合です。
*9:文字数の多い日本語なども、UTF-8などで 8 ビットに符号化されることが多いです。
*10:ブロックの開始位置のほうは、最上位ビットの条件を満たしません。
