Wavelet Matrix
ウェーブレット行列 (Wavelet Matrix) とは，文字列$ D=d_0d_1\cdots d_{n-1}\in\Sigma^* について，以下の3つの操作を可能にするデータ構造のこと． $ \mathrm{access}(D, i)：$ i+1番目の文字$ d_iを与える
$ \mathrm{rank}_c(D, i)：先頭$ i文字（$ d_0\cdots d_{i-1}）に含まれる文字$ cの個数を与える
$ \mathrm{select}_c(D, i)：$ d_k = cを満たす$ i + 1番目の位置$ kを与える
Claude, NavarroらによってSPIRE 2012で発表された（論文）．機能はウェーブレット木と同じだが，実装の易しさにおいて上位互換． 構造
ある数$ wについて$ |\Sigma|<2^wであると仮定し，文字列$ Dを$ wビットで表現される数が並んだ数列$ d_0d_1\cdots d_{n-1}とみなす．以降，数$ dがビット列$ d=b_0b_1\cdots b_{w-1} \ (b_k\in\{0,1\})で表現されるとき，$ b_kを$ dの第$ kビットと呼ぶ．
数列$ Dを次のように繰り返し並べ替えて，$ w + 1個の数列$ D_0, \ldots, D_wを作る．
$ D_0 = D,
$ D_{k+1}=l_0l_1\cdots l_{L-1}r_0r_1\cdots r_{R-1},
ただし$ l_iは数列$ D_kの要素で第$ kビットが 0 である$ i番目のもの，および$ r_jは数列$ D_kの要素で第$ kビットが1である$ j番目のもの．
論文の例に使用されている数列D = 476532101417 ($ w = 3) の場合だと以下のようになる．
code:txt
D_0 = 4 7 6 5 3 2 1 0 1 4 1 7
D_1 = 3 2 1 0 1 1|4 7 6 5 4 7 （前行で第1ビットが0であるものが左，1であるものが右）
D_2 = 1 0 1 1 4 5 4|3 2 7 6 7 （前行で第2ビットが0であるものが左，1であるものが右）
D_3 = 0 4 4 2 6|1 1 1 5 3 7 7 （前行で第3ビットが0であるものが左，1であるものが右）
仕切り|は$ D_kの定義における$ l_0l_1\cdots l_{L-1}と$ r_0r_1\cdots r_{R-1}の境目を示している．
ウェーブレット行列が実際に保持するのは，各数列$ D_k$ (k = 0, \ldots, w-1)について，$ D_kを構成する数の第$ kビット目を並べたビットベクトル$ B_0, \ldots, B_{w-1}である．各ビットは，対応する数が次行で左右のどちらに行ったか（0→左，1→右）を示す．上の例だと次のようになる（仕切りの位置は同じ）．
code:txt
B_0 = 1 1 1 1 0 0 0 0 0 1 0 1 （D_0の各数値の第0ビット目）
B_1 = 1 1 0 0 0 0|0 1 1 0 0 1 （D_1の各数値の第1ビット目）
B_2 = 1 0 1 1 0 1 0|1 0 1 0 1 （D_2の各数値の第2ビット目）
$ D_k=d_0^{(k)}\cdots d_{n-1}^{(k)}および$ B_kの仕切りの位置を$ z_k \ (k=1,\ldots,w)とする．$ i\in[0, z_k)で$ d_i^{(k)}の第$ k - 1ビットは$ 0，$ i\in[z_k, n)で$ d_i^{(k)}の第$ k - 1ビットは$ 1である．$ k行目において，次行の仕切りの位置$ z_{k+1}は$ B_kに現れる$ 0の個数を数えれば計算できる．すなわちビットベクトル$ B_kにおけるrank計算から$ z_{k+1}=\mathrm{rank}_0(B_k, n)が成り立つ．このように仕切りの位置は$ B_0, \ldots, B_{w-1}から復元できるが，後の計算でよく使うので一緒に保存しておくことが多い．
access
$ \mathrm{access}(D, i)は$ i+1番目の文字$ d_iを与える．$ B_kから，$ d_iの第$ kビットおよび並び替え操作によって$ d_iが$ D_{k+1}のどこに移動したかがわかるので，$ d_iの移動先を追跡しながら第$ 0ビットから第$ w-1ビットまで順に復元していく．
最初の行$ D_0について，$ d_iは$ D_0の$ i番目にある．
$ d_iが$ D_kの$ s番目にあるとき，$ d_iの第$ kビットはビットベクトル$ B_kの$ s番目のビットに等しい．これはビットベクトル$ B_kにおけるaccess計算$ \mathrm{access}(B_k, s)で得られる．
次に$ d_iが次行$ D_{k+1}の何番目に移動したかを考える．
$ d_iの第$ kビットが$ 0であるとき，$ d_iは$ B_{k+1}の仕切りの左側にある．$ D_kから$ D_{k+1}への並べ替えの際，第$ kビットが等しいものの間では順序が保存されるので，$ D_kにおいて$ d_iの左側にあった第$ kビットが$ 0である数は，$ D_{k+1}上で$ d_iの左側に過不足なく並ぶ．このような数の個数は$ \mathrm{rank}_0(B_k, s)であり，$ d_iの移動先$ D_{k+1}における番地に等しい．
$ d_iの第$ kビットが$ 1であるとき，$ d_iは$ B_{k+1}の仕切りの右側にある．上と同じ理由から，$ D_kにおいて$ d_iの左側にあった第$ kビットが$ 1である数は，$ D_{k+1}上で仕切りと$ d_iの間に過不足なく並ぶ．このような数の個数は$ \mathrm{rank}_1(B_k, s)であり，それに仕切りの位置$ z_{k+1}を足した値が$ d_iの移動先$ D_{k+1}における番地である．
Python風の擬似コードを以下に示す．
code:access.py
def access(i):
s = 0
d = 0
for k in range(0, w):
b = get_bit(c, k)
if b == 0:
else:
s = wm.zk + 1 + wm.Bk.rank1(s) d |= 1 << (w - k - 1)
rank
$ \mathrm{rank}_c(D, i)は$ Dの先頭$ i文字（$ d_0\cdots d_{i-1}）に含まれる文字$ cの個数を与える．
位置$ s_k及び$ e_k\ (k = 0, \ldots, w)を，以下の条件$ P_kを満たすように定める：
範囲$ [s_k, e_k)で切り出される$ D_kの部分列は，$ d_0, \ldots, d_{i-1}のうち，$ cと第$ 0, \ldots, k-1ビットが一致するものの並べ替えである．
このとき，$ D_w上の$ [s_w, e_w)の範囲には$ Dの先頭$ i文字のうち$ cと完全に一致するもののみがすべて現れるので，$ \mathrm{rank}_c(D, i)=e_w-s_wである．範囲$ s_k,\ e_kを順に狭めるようにして求める．
$ k = 0のとき，$ s_0 = 0および$ e_0 = iとすればよい．
$ s_kと$ e_kから$ s_{k+1}と$ e_{k+1}を求める．$ D_k上の範囲$ [s_k,e_k)にある数のうち，第$ kビットが$ cと一致するものが$ D_{k+1}上に固まって移動するので，その範囲を$ [s_{k+1}, e_{k+1})とすれば$ P_{k+1}が満たされる．
$ cの第$ kビットが$ 0であるとき，範囲$ [s_{k+1}, e_{k+1})は$ D_{k+1}の仕切りの左側にある．$ D_kにおいて番地$ s_kの左側にあった第$ kビットが$ 0である数は，$ D_{k+1}上で番地$ s_{k+1}の左に過不足なく並ぶ．このような数の個数が$ s_{k+1}に等しい．すなわち$ s_{k+1}=\mathrm{rank}_0(B_k, s_k)．同様に$ e_{k+1}=\mathrm{rank}_0(B_k, e_k)．
$ cの第$ kビットが$ 1であるとき，範囲$ [s_{k+1}, e_{k+1})は$ D_{k+1}の仕切りの右側にある．$ D_kにおいて番地$ s_kの左側にあった第$ kビットが$ 1である数は，$ D_{k+1}上で仕切りと番地$ s_{k+1}の間に過不足なく並ぶ．このような数の個数に仕切りの位置を足したものが$ s_{k+1}に等しい．すなわち$ s_{k+1}=z_{k+1}+\mathrm{rank}_1(B_k, s_k)．同様に$ e_{k+1}=z_{k+1}+\mathrm{rank}_1(B_k, e_k)．
Python風の擬似コードを以下に示す．
code:rank.py
def rank(c, i):
s = 0
e = i
for k in range(0, w):
b = get_bit(c, k)
if b == 0:
else:
s = wm.zk + 1 + wm.Bk.rank1(s) e = wm.zk + 1 + wm.Bk.rank1(e) 例において$ \mathrm{rank}_4(D, 10)=2と$ \mathrm{rank}_6(D, 10)=1を計算した例：
code:rank_4_10.txt
*k = 0 (bit: 1)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s-------------------e
D_0 4 7 6 5 3 2 1 0 1 4 1 7
B_0 1 1 1 1 0 0 0 0 0 1 0 1
*k = 1 (bit: 0)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s---------e
D_1 3 2 1 0 1 1|4 7 6 5 4 7
B_1 1 1 0 0 0 0|0 1 1 0 0 1
*k = 2 (bit: 0)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s-----e
D_2 1 0 1 1 4 5 4|3 2 7 6 7
B_2 1 0 1 1 0 1 0|1 0 1 0 1
*k = 3
addr 0 1 2 3 4 5 6 7 8 9 a b c
s---e
D_3 0 4 4 2 6|1 1 1 5 3 7 7
code:rank_6_10.txt
*k = 0 (bit: 1)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s-------------------e
D_0 4 7 6 5 3 2 1 0 1 4 1 7
B_0 1 1 1 1 0 0 0 0 0 1 0 1
*k = 1 (bit: 1)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s---------e
D_1 3 2 1 0 1 1|4 7 6 5 4 7
B_1 1 1 0 0 0 0|0 1 1 0 0 1
*k = 2 (bit: 0)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s---e
D_2 1 0 1 1 4 5 4|3 2 7 6 7
B_2 1 0 1 1 0 1 0|1 0 1 0 1
*k = 3
addr 0 1 2 3 4 5 6 7 8 9 a b c
s-e
D_3 0 4 4 2 6|1 1 1 5 3 7 7
select
$ \mathrm{select}_c(D, i)は$ d_k = cを満たす$ i + 1個目の番置$ kを与える．
rankのときと同様に$ s_kを定める．すると$ D_wにおいて$ i+1個目の$ cは$ s_w+i番目にある．$ Dにおける$ i+1個目の$ cの$ D_kへの移動先を$ e_kとすると$ e_w = s_w + iであり，また$ e_0が$ D_0における$ i + 1個目の$ cの番地であるから$ \mathrm{select}_c(D, i)=e_0である．$ w行目から$ 0行目まで遡って$ e_kを順に求める．
$ e_{k+1}から$ e_kを求める．このとき以下の関係を使う：
$ \mathrm{select}_c(B, \mathrm{rank}_c(B, i))=i.
$ cの第$ kビットが$ 0であるとき，$ Dにおける$ i+1個目の$ cは，$ D_k上の番地$ e_kから$ D_{k+1}の仕切りの左側に移動する．rankのときと同様の議論より，移動先の番地は$ e_{k+1} = \mathrm{rank}_0(B_k, e_k)で表される．ここで両辺を入れ替えて$ \mathrm{select}_c(B_k, \cdot)の中に入れると$ \mathrm{select}_0(B_k, \mathrm{rank}_0(B_k, e_k)) = \mathrm{select}_0(B_k, e_{k+1})，さらに上に示した関係より$ e_k = \mathrm{select}_0(B_k, e_{k+1})．
$ cの第$ kビットが$ 1であるとき，$ Dにおける$ i+1個目の$ cは，$ D_k上の番地$ e_kから$ D_{k+1}の仕切りの右側に移動する．rankのときと同様の議論より，移動先の番地は$ e_{k+1} = z_{k+1}+\mathrm{rank}_0(B_k, e_k)で表される．ここで$ z_{k+1}を移項して$ \mathrm{select}_c(B_k, \cdot)の中に入れると$ \mathrm{select}_0(B_k, \mathrm{rank}_0(B_k, e_k)) = \mathrm{select}_0(B_k, e_{k+1}-z_{k+1})，さらに上に示した関係より$ e_k = \mathrm{select}_0(B_k, e_{k+1}-z_{k+1})．
Python風の擬似コードを示す．
code:select.py
def rank(c, i):
s = 0
for k in range(0, w):
b = get_bit(c, k)
if b == 0:
else:
s = wm.zk + 1 + wm.Bk.rank1(s) e = s + i
for k in reversed(range(0, w)):
b = get_bit(c, k)
if b == 0:
else:
e = wm.Bk.select1(e - wm.zk + 1) return e
例において$ \mathrm{select}_1(D, 1)=8を計算した例（上から下にsを計算し，下から上にeを計算する．
code:select_1_1.txt
*k = 0 (bit: 0)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s e
D_0 4 7 6 5 3 2 1 0 1 4 1 7
B_0 1 1 1 1 0 0 0 0 0 1 0 1
*k = 0 (bit: 0)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s e
D_1 3 2 1 0 1 1|4 7 6 5 4 7
B_1 1 1 0 0 0 0|0 1 1 0 0 1
*k = 2 (bit: 1)
addr 0 1 2 3 4 5 6 7 8 9 a b c
s e
D_2 1 0 1 1 4 5 4|3 2 7 6 7
B_2 1 0 1 1 0 1 0|1 0 1 0 1
*k = 3
addr 0 1 2 3 4 5 6 7 8 9 a b c
s e
D_3 0 4 4 2 6|1 1 1 5 3 7 7
計算量
実装
参考
Claude F., Navarro G. (2012) The Wavelet Matrix. In: Calderón-Benavides L., González-Caro C., Chávez E., Ziviani N. (eds) String Processing and Information Retrieval. SPIRE 2012.