Hatena::ブログ(Diary)

アスペ日記

2013-03-03

中学生にもわかるウェーブレット行列

id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 ”The Wavelet Matrix”」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。


…嘘です。

日本以外ではあんまり来ていません。

理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。


まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。


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

主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。


rank() は、「文字列の先頭から位置 k までに、文字 x がいくつあるか」。

select()は、「文字列の先頭から見て、n 個目の文字 x の次の位置はどこか*3」。


それぞれ例を挙げます。


"abracadabra" という文字列(S とします)の中で、先頭から位置 8 までの間に、いくつ a があるか。

下の図で、先頭から矢印までの範囲の a を数えることになります。


f:id:takeda25:20130303172841p:image


実際に目で数えてみると、4 つあります。


f:id:takeda25:20130303172842p:image


つまり、rank(S, 8, "a") = 4ということになります *4


また、この文字列の中で、2 個目の文字 b の次の位置はどこか。

下の図は、先頭から 2 個の b に色をつけたものです。


f:id:takeda25:20130303172843p:image


2 番目の b は位置 8 にあるので、その次である位置 9 が求めるものです。

つまり、select(S, 2, "b") = 9 ということになります*5


f:id:takeda25:20130303172844p:image


先頭から順に数えるというやり方では、サイズが大きくなるとこれらの操作には長さに比例した時間がかかりますが、ウェーブレット行列*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 ということにします。

対象とする文字列(数字列)は、ここでは次のようなものであるとします。

f:id:takeda25:20130303172845p:image

まずは、これを単純に上の桁から基数ソートする場合を考えてみます。

ものすごく冗長なので、基数ソートに慣れている人は飛ばしてください。


最初は、4 ビットで表した 2進数での最上位ビットに注目します。青く塗られたところが、最上位ビットが 1 のものです。

f:id:takeda25:20130303172846p:image

元の順序を保ったまま、最上位ビットが 0 のものを左に、1 のものを右に寄せます。

f:id:takeda25:20130303172847p:image

いったん色を元に戻すと、次のようになります。

f:id:takeda25:20130303172848p:image


次は、2進数で上から 2 番目のビットに注目します。青く塗られたところが、上から 2 番目のビットが 1 のものです。

f:id:takeda25:20130303172849p:image

元の順序を保ったまま、上から 2 番目のビットが 0 のものを左に、1 のものを右に寄せます。

f:id:takeda25:20130303172850p:image

色を元に戻すと、次のようになります。

f:id:takeda25:20130303172851p:image


今度は、2進数で上から 3 番目のビットに注目します。青く塗られたところが、上から 3 番目のビットが 1 のものです。

f:id:takeda25:20130303172852p:image

元の順序を保ったまま、上から 3 番目のビットが 0 のものを左に、1 のものを右に寄せます。

f:id:takeda25:20130303172853p:image

色を元に戻します。

f:id:takeda25:20130303172854p:image


最後に、2進数で上から 4 番目のビット、つまり最下位ビットに注目します。青く塗られたところが、最下位ビットが 1 のものです。

f:id:takeda25:20130303172855p:image

元の順序を保ったまま、最下位ビットが 0 のものを左に、1 のものを右に寄せます。

f:id:takeda25:20130303172856p:image

色を元に戻します。

f:id:takeda25:20130303172857p:image



この最後の数字列は、それぞれの数字のビットを逆転させたものの順番にソートされています。

重要なのは、数字ごとにブロックに分かれているというところです。


ウェーブレット行列では、基数ソートのそれぞれの段階で注目したビットの列だけを持っています。

この場合、実際に保存されるデータは次のようなものです。

f:id:takeda25:20130303172858p:image


これらのビット列に加えて、各段階での 0 の数(この場合は 19, 12, 14, 16)も保存しておきます。


ここで、ウェーブレット行列のデータを使って、実際に rank の計算をしてみます。

この配列の中で「インデックス 22 より左に "11" はいくつあるか」を調べることにします。

インデックス 22 というのは、下の図で矢印で表した位置です。

f:id:takeda25:20130303172859p:image

先頭からこの位置までの "11" の数を目で数えると、答えは次のように 3 個ということになります。

f:id:takeda25:20130303172900p:image

これを求めることが目的となります。


ウェーブレット行列の、最初のビット列を見てみます。

f:id:takeda25:20130303172901p:image

これは、元の数字列の最上位ビットを並べたものです。

ここで、理解のためにビット列に対応する元の数字列を下に薄く添えます(実際には保存していません)。

f:id:takeda25:20130303172902p:image

インデックス 22 は、矢印で示した位置です。

f:id:takeda25:20130303172903p:image

先頭からこの位置までの間に、検索対象である "11" と最上位ビットが同じもの、つまり最上位ビットが "1" であるものがいくつあるかを数えます。これは完備辞書であれば定数時間でできます。答えは、図からわかるように 10 個です。

f:id:takeda25:20130303172904p:image

ここで、この位置が上から 2 番目のビット列ではどこにあたるかを見てみます。

まず、数字列だけで見てみます。1 列目で矢印の左にあり、最上位ビットが 1 だった 10 個の数字は、2 列目では次のように固まっています。

f:id:takeda25:20130303172905p:image

このブロックの最後の位置が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットが "11" と同じである数字のブロックの終端位置」を表しています。

矢印をつけると次のようになります。

f:id:takeda25:20130303172906p:image

この位置は、太線で表した 0-1 境界(各段階での 0 の数を覚えているので、それを使います)から右に 10(1 列目で矢印の左にあり、最上位ビットが 1 だった数字の数)として計算できます。


上から 2 ビット目の列を、数字列の上に添えます。実際に持っているのはビット列のほうだけです。

f:id:takeda25:20130303172907p:image


先頭から矢印の位置までの間に、検索対象である "11" と上から 2 番目のビットが同じであるもの、つまり "0" であるものがいくつあるかを、完備辞書で数えます。

f:id:takeda25:20130303172908p:image

図のように、11 個あります。

これらに対応する数字列は、3 列目では図のように固まっています。

f:id:takeda25:20130303172909p:image

このブロックの終端位置が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットと上から 2 番目のビットが "11" と同じである数字のブロックの終端位置」となります*10

f:id:takeda25:20130303172910p:image

上から 3 ビット目の列を、数字列の上に添えます。

f:id:takeda25:20130303172911p:image

先頭から矢印の位置までの間に、検索対象である "11" と上から 3 番目のビットが同じであるもの、つまり "1" であるものがいくつあるかを、完備辞書で数えます。

f:id:takeda25:20130303172912p:image

図のように、6 個あります。

これらに対応する数字列は、4 列目では図のように固まっています。これまでと同じように、このブロックの最後が、「最初の数字列でインデックス 22 より左にあり、かつ最上位ビットから上から 3 番目までのビットが "11" と同じである数字のブロックの終端位置」となります。

f:id:takeda25:20130303172913p:image

最下位ビットの列を、数字列の上に添えます。

f:id:takeda25:20130303172914p:image

先頭から矢印の位置までの間に、検索対象である "11" と最下位ビットが同じであるもの、つまり "1" であるものがいくつあるかを、完備辞書で数えます。

f:id:takeda25:20130303172915p:image

図のように、10 個あります。

最終的にソートされた数字列(これも実際に持ってはいません)の中では、これらに対応する数字は図のように固まっています。

f:id:takeda25:20130303172916p:image

そして、矢印の位置が「最初の数字列でインデックス 22 より左にある "11" のブロックの終端位置」となります。


ここで、最後の数字列は、ひとつの数字がひとつのブロックになっています。データ作成時に、それぞれの開始位置を記憶しておくと、この場合 "11" のブロックの開始位置と「最初の数字列でインデックス 22 より左にある "11" のブロックの終端位置」との差分をとることで、求める数を知ることができます。

f:id:takeda25:20130303172917p:image

図でわかるように、答えは 3 になります。


このように、上の桁から基数ソートしたときのビット列と、それぞれの段階での 0 の数、それにソート済み数列中でのそれぞれの数字の開始位置を覚えておくことで、rank が行えるということがわかります。

この過程を逆にたどると、select になります。


また、RankLessThan()QuantileRange() については、以前書いたものがありますので、そちらをご参照ください。


最近「ウェーブレット行列はコード書きやすいけど理解するのはウェーブレット木のほうが楽」というような意見を見たので、ウェーブレット行列難しくないよ! というのを示すために書きました。

書いてみて…うーん、やっぱり難しいかも。

でも、「完備辞書」をブラックボックスとして受け入れると、ウェーブレット行列自体には 2 進数以外の知識は必要ないので、こういうタイトルにしてみました。


ところで、簡潔データ構造など高速文字列解析に役立ついろいろなトピックをまとめた本があります。



この本の中でもウェーブレット行列は取り上げられているのですが、この本の記述自体もなかなか簡潔なため、私のようにかなり冗長に考えないとなかなか理解できない人向けにと思ってこの記事を書きました。

*1:最初に触れたときにもこれをはじめとしたいくつかの記事を書いたのですが、興奮のためあまりわかりやすい記事が書けていないと思い直したため。

*2:rank_less_than などはとりあえず置いておきます。

*3:rank との対称性のために、直感的に少しわかりにくくなっています。

*4引数は前から文字列、位置、検索文字です。

*5引数は前から文字列、個数、検索文字です。

*6:いったんウェーブレット「木」のことは置いておきます。

*7:簡潔ビットベクトルとも。

*8:上の桁からというのは、後で出てくる RankLessThan といった関数の都合です。

*9:文字数の多い日本語なども、UTF-8などで 8 ビットに符号化されることが多いです。

*10:ブロックの開始位置のほうは、最上位ビットの条件を満たしません。

わからないわからない 2013/03/04 13:01 ところどころ端折られていて分かりにくい。 わざわざ「rank(S, 8, "a") = 4」と例を挙げているのに「select(S, 2) = 9」とかが無かったり、簡単のために文字列を「0-15」としたときに「2進数で4ビット」の解説なしにいきなり最上位ビットの話をしたりしている。

takeda25takeda25 2013/03/04 13:45 ご意見ありがとうございます。修正しました。

通りすがり通りすがり 2013/03/04 19:37 わかりやすい説明でとても参考になりました。
ところで、おかしな、というか見当はずれな質問かもしれませんが、
こういったデータ構造の場合、動的な更新というのは難しいのでしょうか?
例えば、文字列(数列)の末尾に要素を追加するといった操作です。
勿論、実装の仕方に依存するとは思いますが…

takeda25takeda25 2013/03/04 22:24 ウェーブレット行列の元となったウェーブレット木のほうで、動的な更新をサポートするものが出ているようです。 http://arxiv.org/abs/1206.6982 ただ、残念ながら私は追えていません。静的なものに比べると、やはりだいぶ難しくなりそうです。

espresso3389espresso3389 2013/03/06 11:00 この説明だと、途中で迷子になります。元の文字列、ソート途中の文字列、ビット配列毎に色を変えるなどの工夫を加えないと、どれがどの表なのか途中で分からなくなりました・・・。

takeda25takeda25 2013/03/06 11:42 そうですね。それぞれのビット配列が紛らわしいというのは、書き終わってから思いました。
ただ、すでに 0 と 1 のビットで色分けしているので、さらに区別をするには工夫をする必要がありそうです。
余裕があれば作り直します。
ありがとうございます。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証