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

前回に引き続きLOUDSという簡潔木の話。前回準備したunaryの簡潔ビットベクトルを使って親ノード、子ノードへのアクセスが効率的に可能な木構造であるLOUDSの話をする。

前回までの記事：
簡潔データ構造超入門〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei

さて、LOUDS(Level Order Unary Degree Sequence、ラウズ)は木構造を表すデータ構造のひとつ。データサイズを小さく抑えつつ親ノード、子ノードへのアクセスも効率的(O(logN))に可能になっている。
まず子ノードへのアクセスについて考える。この場合、木構造では各ノードは「子ノード位置のリスト」を持っている。この部分を「先頭の子ノード位置」を持たせるだけで「子ノード位置のリスト」を持っているのと同じことをできるようにしよう、というのが基本的なアイデア。「子ノード位置のリスト」は「ポインタサイズ*子ノード数」のデータサイズが必要だが「先頭の子ノード位置」だけであれば例えばポインタサイズだけで済む。
「先頭の子ノード位置」だけで子ノードの位置すべてを知るには子ノードがまとまって並んでいれば良い。これには木のノードを深さ優先探索の順番で並べてあげれば良い。具体的には

親　　　子
1 => (2, 3, 4, 5)
2 => (6, 7)
3 => (8)
4 => (9, 10)

というようなものを想像してもらうと良い。このように子ノードが連番になっていれば

親　　　子の先頭位置
1 => 2
2 => 6
3 => 8
4 => 9

というようにデータサイズを縮小できる。なぜ縮小しても大丈夫かというと、例えば2番のノードの子ノードを列挙したいとする。このとき2番に対応する「子の先頭」が6番、3番に対する「子の先頭」が8番なので6番、7番が子ノードであることがわかる。つまり

i番のノードの子ノードリスト
=i番の子の先頭から(i+1)番の子の先頭直前までの番号全部

となっている。

さて、ここで注目したいのが「子ノードの先頭位置」。値が単調増加している。ということはunaryの簡潔ビットベクトルで表現が可能ということ。
復習しておくとunaryの簡潔ビットベクトルは単調増加列を効率的に扱う簡潔構造で、以下の2つの操作が可能だった。

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

このうちrank(select0(i))を使えば、この先頭位置を自由に取り出せる、というわけ。ちなみに計算量はrankがO(1)、select0がO(logN)で実装していたので全体でO(logN)となっている。selectを効率化すればここは改善される。

ということでもう一つの話題である親ノードへのアクセスを。これは単純に考えると各ノードが「親ノードへのポインタ」を持っていれば良い。が、unaryを使えば「親ノードへのポインタ」がなくても大丈夫だったりする。
ここで最初に示した木を振り返ると

親　　　子
1 => (2, 3, 4, 5)
2 => (6, 7)
3 => (8)
4 => (9, 10)

となっている。例えば8番のノードに注目する。3行目に着目すると、このノードの親ノードは3番であることがわかる。ここで「親」の部分を消してみる。

　子
(2, 3, 4, 5)
(6, 7)
(8)
(9, 10)

こうすると親ノードは特定できないか？そんなことはなく「8番があるのは3行目だから親は3番」と考えて良い。
ということはあるノードについて親ノードを知りたい場合は「自分の所属する行が何行目か」ということがわかればよい。言い換えると「自分の所属する行までに何行あるか」がわかればよい。
ここでrank0(select(x))の出番。この関数はxより小さい値の数を返すものだった。unaryには「子ノードの先頭位置」が記録されていた。つまり

　子
([2], 3, 4, 5)
([6], 7)
([8])
([9], 10)

の四角カッコをつけた部分。これは各行ひとつずつある。
そこでunaryのrank0(select(x))を使ってあげるとx=8のときに、8より小さい要素は2と6の2つなので2が帰ってくる。これは自分の行までに2行あるよ、ということなので自分は3行目にいる(=3番が親ノード)ということがわかる。

以上。ちょっと複雑だったがLOUDSをunaryの簡潔ビットベクトルで表現する方法を説明した。ここで扱ったunaryの簡潔ビットベクトルは「集合の簡潔構造」と深い関係がある。次回はそのへんを話す予定。なおLOUDSに関する詳細は以下のJacobson論文を参考にされたい。

Space-efficient Static Trees and Graphs G. Jacobson; IEEE1989