たぶん30分でよくわかるLOUDS入門
IME本の効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。
というわけでLOUDSをどこまでわかりやすく説明できるか？ということに挑戦したくなったので記事を書いてみるよ。
LOUDSというのは木を表すデータ構造。木というのは以下のようなものを想像すればよい。
この木を表すデータ構造を作りたい。単純に考えると各ノード毎に子ノードのIDを持たせておけばよい。つまり
0 => {1, 4, 5}
1 => {2, 3}
2 => {}
3 => {}
4 => {}
5 => {6}
6 => {7}というようなものを考える。ここで各IDと子ノード数を各1バイトで管理したとして
0 => {1, 4, 5} # 1 + 3 = 4バイト
1 => {2, 3} # 1 + 2 = 3バイト
2 => {} # 1 + 0 = 1バイト
3 => {} # 1 + 0 = 1バイト
4 => {} # 1 + 0 = 1バイト
5 => {6} # 1 + 1 = 2バイト
6 => {} # 1 + 0 = 1バイト
=======================
13バイトとなる。各行の+1は子ノード数を格納する変数のぶん。この13バイトをもっと小さくしたい。
これに対する一つの答えは、ノードのIDを入れ替えることで達成できる。具体的には以下のようにIDを振り直す。
この図ではIDを幅優先探索の順番で振っている。こうすると、すべてのノードに対して子ノードIDが連番になっていることがわかる。
0 => {1, 2, 3}
1 => {4, 5}
2 => {}
3 => {6}
4 => {}
5 => {}
6 => {}連番になっているので子ノードの先頭位置だけ持っておけばよくなる。つまり
0 => 1 1 => 4 2 => 4 3 => 6 4 => 6 5 => 6 6 => 6
で7バイトあればよくなる。子ノードがないノードは便宜上、直前のノードの先頭子ノードIDと同じIDを与えた。
これをさらに小さくしたい。
これには簡潔ビットベクトルというデータ構造を使う。簡潔ビットベクトルは登録しておいたIDを小さい順に取得するselect()という操作ができる。例えば
bit_vector.set(1); bit_vector.set(4); bit_vector.set(6); bit_vector.select(0); # 1を返す bit_vector.select(1); # 4を返す bit_vector.select(2); # 6を返す
というようなものになる。簡潔ビットベクトルは登録されている最大の数をNとして(N+1)ビット(バイトではなので注意)で実現できる。↑の例では7ビットになる。これを使えば7バイトを更に小さくできそう。
ただし簡潔ビットベクトルはIDを小さい順にしか登録できない。また同じ値を複数登録できないという欠点がある。なので子ノードが存在しないノードの扱いに困る。
この問題は「子ノードの先頭位置＋自分のノードID」を登録することで解決できる。つまり
0 => 1 + 0 = 1 1 => 4 + 1 = 5 2 => 4 + 2 = 6 3 => 6 + 3 = 9 4 => 6 + 4 = 10 5 => 6 + 5 = 11 6 => 6 + 6 = 12
これを簡潔ビットベクトルに登録する。
bit_vector.set(1); bit_vector.set(5); bit_vector.set(6); bit_vector.set(9); bit_vector.set(10); bit_vector.set(11); bit_vector.set(12);
あるノードIDから先頭の子ノードIDを得るにはselect(ノードID) - ノードIDを計算すればよい。
bit_vector.select(0) - 0 = 1 - 0 = 1 bit_vector.select(1) - 1 = 5 - 1 = 4 bit_vector.select(3) - 3 = 9 - 3 = 6
以上のように子ノード数を計算することができた。また簡潔ビットベクトルに登録した最大のIDが12なので必要なデータサイズは13ビットで最初の13バイト、IDを振りなおした改良版の7バイトに比べて大幅にデータサイズが小さくなったことがわかる。
これの具体的な実装は昨日の記事
を参考にされたい。より詳しい解説はIME本
や
などを見るとよい。
＜3/7追記＞
@takeda25さんから指摘をいただいたので追記。↑のリンクの実装例では簡潔ビットベクトルに登録する値として
0 => 1 + 0 = 1 1 => 4 + 1 = 5 2 => 4 + 2 = 6 3 => 6 + 3 = 9 4 => 6 + 4 = 10 5 => 6 + 5 = 11 6 => 6 + 6 = 11
のように先頭子ノードID＋注目ノードIDではなく
0 => 3 + 1 = 4 1 => 5 + 2 = 7 2 => 5 + 3 = 8 3 => 6 + 4 = 10 4 => 6 + 5 = 11 5 => 6 + 6 = 12 6 => 6 + 7 = 13
末尾子ノードID＋注目ノードID+1を使っている。
こうすると子ノードへのアクセスをするのに、select(ノードID - 1) - ノードID + 1という計算をしないといけないので少々複雑になる。
bit_vector.select(0 - 1) - 0 = 0 - 0 + 1 = 1 bit_vector.select(1 - 1) - 1 = 4 - 1 + 1 = 4 bit_vector.select(3 - 1) - 3 = 8 - 3 + 1 = 6
一方で、子ノード数の計算がselect(ノードID) - select(ノードID - 1) - 1で行えるという利点がある。
bit_vector.select(0) - bit_vector.select(0 - 1) + 1 = 4 - 0 - 1 = 1 bit_vector.select(1) - bit_vector.select(1 - 1) + 1 = 7 - 4 - 1 = 2 bit_vector.select(3) - bit_vector.select(3 - 1) + 1 = 10 - 8 - 1 = 1
