LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。
Space-efficient Static Trees and Graphs
G. Jacobson, 1989
LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。
そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済む。
上で紹介した元論文に倣って、以下の木構造を考える。
1 +---+---+ 2 3 4 +---+ + 5 6 7 + + 8 9
ちょっと見にくいので、元論文のFigure3を見ていただけると幸い。
さて、まず各ノードを子ノードの数の1の後ろに0をひとつ付けてビット表現する。例えば上の図でノード2は110、ノード4は01、ノード8は0という感じ。
つぎに
10
というビット列を用意し、これの後ろにノードに対応するビット表現を追加していく。追加の順番は深度の浅い方から、左から順に入れていく(つまり上の図のノード番号の順)。
すると
1 2 3 4 5 6 7 8 9 10 1110 110 0 10 10 10 0 0 0 => 1011101100101010000
となる。このビット列に対してrank()およびselect()という操作をすることで子ノードへの移動、親ノードへの移動、となりのノードへの移動が可能になる。rank()、select()は上手く実装すれば定数時間で実行できる。このようなrank()、select()の用意されたビットベクトルをsuccinct bit vector(簡潔ビットベクトル)という。これの詳細は、
Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- - EchizenBlog-Zwei
などを読むと良い。
話を戻す。現在ビット列のmの位置にいるときに、最初の子ノードの位置を得るには
select(rank(m, 1), 0) + 1
とすればよい。rank(m, 1)によってmまでに出現する1の数(「子」ノードの数)がわかる。これはmの位置のノードの最初の子ノードまでに出てくるノードの総数xと同じ。一方でselect(x, 0)によってx番目の0(x番目のノードを表すビット表現の末尾)に移動できる。従って、これに1足した数が、mの位置のノードの最初の子ノードの位置。
親ノードの位置を得るには
select(rank(m, 0), 1)
とする。rank(m, 0)によってmまでに出現する0の数(ノードの数)がわかる。これはmの位置のノードが何番目のノードであるかということと同じ。よってselect(x, 1)によってx番目のノードを子ノードとしてもつノードのビット表現に移動できる(あとは右側に0が出るまで移動すればよい)。
というわけでsuccinct bit vector(簡潔ビットベクトル)を使うことで効率的に木構造が表現できるよ、というお話。LOUDSはTx(有名なトライのライブラリ)にも利用されている。
の参考文献がとても参考になる。
