簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜

今回はLOUDS(Level Order Unary Degree Sequence, ラウズ)というデータ構造の話。LOUDSは木構造の簡潔データ構造版、簡潔木と呼ばれているものの一種。
簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものがある。BPやDFUDSは部分木の大きさを効率的に計算できるという利点がある。実際は各ノードから親ノード、子ノードへのアクセスが効率的に出来れば十分な場合も多いので、そういう場合はLOUDSが活躍する。
今回はそんなLOUDSのお話の準備編。LOUDSに必要なデータ構造を用意するところまで。

前回までの記事：
簡潔データ構造超入門〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei

まずは前回の復習。前回は検索エンジンで利用される転置インデックスを簡潔ビットベクトルを使って効率的に実現する話をした。転置インデックスは

orange  1, 2, 4, 6

のように単語とそれに対するID列で構成されている。このID列を差分列のunary符号で表現した。

元のデータ列  1, 2, 4, 6
差分列           1, 1, 2, 2
unary符号      1010110110

このunary符号形式のビット列を簡潔ビットベクトルで持たせることにした。簡潔ビットベクトルにはrank/selectという2つの操作が実装されていた。

rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数
select(i): i番目に立っているビットの位置

この2つの操作を使うことである「あるIDより小さいのIDの数」を求めることができた。例えば、以下のようにするとID3より小さいのIDは2つ(1と2)であることが求められた。

rank0(select(3))
= rank0(4)
= 4 + 1 - rank(4)
= 4 + 1 - 3
= 2

ここまでで復習終わり。具体例として転置インデックスを挙げたが、要するに「単調増加する数値列」に対して「ある数値より小さい数値がいくつあるか効率的に計算する」というのを実現した。今回はこれに加えて「i番目の数値がいくつなのかを効率的に計算する」というのを実現する。
普通の配列aだとa[i]などとすればいいので全く簡単なのだが、差分をとってunary符号化してあるので(データサイズは小さくなったが)要素へのアクセスは簡単ではなくなってしまっている。
まずunary符号化されたビットベクトルでi番目の値に該当する部分を探す。例えば3番目の要素なら

1010[110]110

のカッコで示した範囲を知りたい。範囲なので先頭位置と終了位置があるが、とりあえず終了位置を知ることにする。
これは実は簡単。unary符号では数値の切れ目には必ず0が来るので3番目の0の位置がわかれば良い。ここで簡潔ビットベクトルのselectという操作を思い出すと

select(i): i番目に立っているビットの位置

というものだった。これの逆で

select0(i): i番目に立っていないビットの位置

をすればよい。通常のselectはrankの二分探索で実装した。select0はrank0の二分探索で実装できる(詳細は割愛)。
ともあれselect0を使うと

select(3) = 6

101011[0]110

となりunaryでの3番目の値の末尾の位置がわかる。
ではいよいよ3番目の要素の値を求めたい。unaryでは差分列を持たせていた。よってunaryで3番目までの累計値がわかればよい。ここで簡潔ビットベクトルのrankという操作を思い出すと

rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数

というものだった。これをそのまま使えばunaryでの3番目までの累計値がわかる。つまり

rank(select0(3))
= rank(6)
= 4

となる。この4は元のデータ列(1, 2, 4, 6)の3番目の値。無事i番目の数値を求めることができたことがわかる。
まとめると単調増加するデータ列に対して

rank0(select(x)): xより小さいの値の数
rank(select0(i)) : i番目の値

という操作が定義できたことになる。これを用いて次回はLOUDSの実現方法を解説する予定。LOUDSについては以前にDSIRNLPで発表した資料があるので興味ある方はそちらを参考にされたい。こちらの資料を見れば今回の操作がなぜ必要なのかはわかると思う(もちろん次回の記事でも解説する)。

DSIRNLP#1で発表しました「TRIEにトライ！〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei