はじめに
大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。
rank(p, c)――T[0...p]中のcの出現回数を返すselect(i, c)――(i+1)番目のcの位置を返す
WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。
対象読者
C++の利用者を対象としています。
必要な環境
C++、32bit環境を想定しています。Windows XP上のVisual Studio C++ 2003、gcc 3.2.2で動作確認済みです。
wavelet treeの概要
wavelet tree (WT）は文字列T[0...n-1]上で定義されるデータ構造であり、rank、selectの2つの操作をサポートします。rank(p, c)はT[0...p]中のcの数を返し、select(i, c)は (i+1)番目のcの位置を返します。WTは、sucBVと呼ばれるデータ構造を拡張したデータ構造です。sucBVで扱えるのはTがbit vector（文字が0か1のみ）の場合だけなのに対し、WTはTがどんな文字列や整数列からなっていてもよいところが違います。
このWTを利用することで、近年提案されている圧縮全文索引（Compressed Suffix Arrays、FM-index、wavelet treeなど）やsuccinct data structure（括弧木など）を実現することができます。WTを利用した、これらのデータ構造についても今後記事にする予定です。
いくつか例を挙げて、WTにおけるrank、select操作を説明します。今、T[0...9] = abccbbabcaが与えられたとします。この時、rank(5, 'b')=3です。なぜなら、T[0...5]中には3つのbがあるからです。同様にしてrank(5, 'c')=2となります。一般にΣ_c rank(p, c)=p+1が成り立ちます（添え字が0始まりなのでpではなくp+1）。またselectの場合は、select(2, 'b')=5となります。なぜなら、（2+1）番目のbの位置は5だからです。同様にして（2+1）番目のcの位置は8なので、select(2, 'c')=8となります。その他の結果は次の通りとなります。
T[0...9] = abccbbabca
| p | rank(p, 'a') | rank(p, 'b') | rank(p, 'c') |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 2 |
| 5 | 1 | 3 | 2 |
| 6 | 2 | 3 | 2 |
| 7 | 2 | 4 | 2 |
| 8 | 2 | 4 | 3 |
| 9 | 3 | 4 | 3 |
| p | select(p, 'a') | select(p, 'b') | select(p, 'c') |
| 0 | 0 | 1 | 2 |
| 1 | 6 | 4 | 3 |
| 2 | 9 | 5 | 8 |
| 3 | - | 7 | - |
このrank、select操作を、前処理無しに毎回求めるとO(n)時間必要です。前もって全ての答えを求めておく場合も、rank、selectの結果を全て明示的に保持するには、文字種類数がAの時、約32 (A+1) N bit必要になります（rankに32AN bit、selectに32N bit必要）。これは文字列本体の作業領域量: N lg(A) bit（lg(x)は2を底としたxの対数）の32(A+1) / lg(A)倍にもなります。今回紹介するWTは、定数時間（正確には入力長に対し定数時間。入力する文字種類数がSの時はlg(S)より小さい0次エントロピー）でrank、select操作を約3 lg(A) N bitの作業領域で実現しています。
