WTの使い方
WTは、任意の整数列を引数に渡して構築します。任意の整数列unsigend int* Tもしくはunsigned char* Tを用意し、WTのコンストラクタに渡します。具体的なソースコードは以下の通りです。
#include "waveletTree.hpp" #define alphaSize 0x100 using namespace cs; ... unsigend char T[10] = "abccbbab" waveletTree wt(T,10,alphaSize);
実際にrank、selectを利用する場合はwaveletTreeのメンバ関数であるrank()、select()を呼び出します。以下では、上述の例のrank、selectを実際に求めています。
printf("rank(5,b)=%d rank(5,c)=%d select(2,b)=%d select(2,c)=%d\n",
opb.rank(5,'b'),opb.rank(5,'c'),
opb.select(2,'b'),opb.select(2,'c'));
waveletTreeを構築、利用する一連の流れのサンプルは「waveletTree_unitTest.cpp」にあります。このコードでは最初にランダムな整数列を生成した後、それからwaveletTreeを構築します。その後、実際直接rank、selectを求めた場合と値をチェックした後、速度計測をしています。
waveletTreeは圧縮率の高い整数集合コンテナとしても利用できますが、その真価を発揮するのは圧縮索引などで利用する場合です。これらのデータ構造での使用例については、今後の記事を参考にしてください。
技術解説
waveletTreeは[1]で圧縮索引用にはじめて登場しました。詳しい解説は[2]に書いてあります。ここでは、T[0...9] = abccbbabcaに対するwaveleTreeの例を通して簡単な説明をします。waveletTreeは、内部データ構造は木構造であり、各木の節点にはrank/select操作を備えたbit vectorが付随されてます（図1)。
この木は入力データから求められたHuffman木（図2）と同じ形をしています。
次に各節点のbit vectorがどのように定義されるかを説明します。まず根に付随するbit vectorはT[0...n-1]の各文字をHuffman符号で符号化した場合の最初のbitを並べたものです。今回の例ではbの最初のbitが'0'、aとcの最初のbitが'1'なので、bが出現した位置に'0'、aまたはcが出現した位置に'1'を配置したbit vectorが根に付随するbit vectorとなります。次に、Huffman木に沿ってTの各文字を元の順序関係を保ったまま左右の子に移動させます。今回の例の場合、bが左側の子、a，cが右側の子に移動します。T=abccbbabcaでのa，cはa_cc__a_caと出現しているので、右側の子にはaccacaが移動します。そして今度は2番目のbitを順に並べたものを各節点のbit vectorにします。a、cの2番目のbitはそれぞれ0、1なので、右側の子に付随するbit vectorは011010となります。これを葉にたどり着くまで再帰的に繰り返します。
Waveletの名前の由来はおそらく、Huffman符号に従って各文字を再帰的にfilteringしている部分にあると考えられます。
次にこのデータ構造を用いて、どのようにしてrank、selectを求めるかを例を通して説明します。はじめの例としてrank(5,c)を求める場合を扱います。rankの場合、根からcの葉に向かって各節点でrankを求めていきます。まず根の節点において、cの最初のbitが1なので、rank(5,1)を求めます。この場合の答えは3=rank(5,1)です。この3の意味はaまたはcが5番目の位置までで3回出現しているという意味です。次に右の子に移動し、rank(3,1)を求めます。この場合の答えは2=rank(3,1)なので、rank(5,c)の答えが2だと分かります。
次にselect(1,a)の例を扱います。selectの場合、aの葉から根に向かって各節点でselectを求めていきます。まずaの親の節点において、select(1,0)を求めます。この場合の答えは3=select(1,0)です。次に根である親の節点においてselect(3,1)を求めます。この場合の答えは6=select(3,1)なので、select(1,a)の答えが6だと分かります。
waveletTreeでは、任意の文字列に対するrank、selectを、各節点におけるbit vectorに対するrank、selectで実現しています。bit vectorに対するrank、selectはsucBVの記事で扱っているように、さまざまな方法が既に提案されています。今回の実装では以前の記事で紹介したsucBVを使っています。
wavelet treeを利用するのに必要な作業領域量は、理論的には入力テキストのH0（0次エントロピー）*N bitです。なぜなら、全節点のbit vectorをつなぎ合わせたものの長さが、元のテキストをHuffman符号で符号化した時の長さと一致するからです。しかし、実際には各節点のbit vectorでrank、selectを定数時間で実現するためには、約2倍のオーバーヘッドが必要なので、大体 3*H0*N bit必要ということになります。H0はデータによりますが、英文の場合大体半分から0.75ぐらいなので、元テキストの大体2倍必要になります。
select操作をrank操作の2分探索に置き換えるなど、速度を犠牲にすることで作業領域量を情報理論的な限界に近づけることが可能です。今後の研究や実用上の改良によって、作業領域量が大幅に改善されると思います。
まとめ
今回紹介したデータ構造wavelet treeは、任意の文字列に対するrank/select操作を定数時間で実現するものです。このデータ構造はsucBV同様、もともと圧縮索引やSuccinct Data Structureのために提案されたものですが、その他の応用用途も考えられます。例えば、文字集合として単語集合を考えた場合、転置ファイルに置き換えるものとしてwavelet treeを利用できます。
参考資料
- SODA '03 『High-order entropy-compressed text indexes』 R. Grossi・A. Gupta・J. S. Vitter 著、2003年1月
- Technical Report TR/DCC-2005-7 『Compressed Full Text Indexes』 V. Makinen・G. Navarro 著、2005年1月
- 『圧縮索引とその周辺』 岡野原大輔 著、2005年12月
