はじめに
前回登場した「完備辞書」というビット列を使うと木構造を非常に小さなデータ量で保持することができる。LOUDS と呼ばれているのであるが、これはなんと1ノードあたり2bitしか用いずに木構造を保持できるというすさまじいものである。
個人的には理解するのに結構苦労したが理解してみれば非常にシンプルな話であり、言いたくはないが最初に読んだ資料が悪かったのではないかとちょっと疑っている。(いや…たぶん自分の頭の問題だとは思うが)
以下では木構造のビット列への変換を極力可視化して5分で理解できるような資料を作成してみた。
完備辞書
前回説明したように、完備辞書は以下の二つの操作が定数時間でできるビット列のことだ。
- 0～n-1番目のビットまでに true もしくは false がいくつあるか数える操作。以降 int rank(lboolean[] v, int nth, boolean b); というような関数として表現する。
- 先頭から数えてn個目の true もしくは false であるビットがk番目にあるとして、k+1を求める操作。以降 int select(boolean[] v, int n, boolean b); というような関数として表現する。
前回同様、「定数時間」というところを無視して今は下記のようなコードだと思って先へ進むことにしよう。前回も指摘したが rank と select は逆関数になっていることも強調しておく。
public static int rank(boolean[] v, int num, boolean bit) {
int result = 0;
for (int i = 0; i < num; i ++) if (v[i] == bit) result ++;
return result;
}
public static int select(boolean[] v, int nth, boolean bit) {
for (int i = 0; i < v.length; i ++) if (rank(v, bit, i) == nth) return i;
throw new IndexOutOfBoundsException();
}
木構造をビット列に変換する
以下の図(左)のような木構造があったとしよう。この木の各ノードに幅優先で番号を割り当てる。幅優先というのは図(右)で示されるような順番のことを指す。
次に以下の図のように木を斜めに変形し、親子関係のところに三角形を貼りつける。その三角形を幅優先で並べて行く。
ここで上(親側、三角形の頂点)のノードだけ横にノード番号を読んでいくと「1,2,3,4,5,6…」と連番になっていることに着目しておいて欲しい。また下(子側、三角形の底辺)のノードだけ横にノード番号を読んでいくと「2,3,4,5,6,7…」とこれまた連番になっている。これは幅優先でノード番号を振った効果でありこれが木構造を簡潔に表現する重要な秘密となっている。また、この三角形の列には同じノードが2回現われることに(親ノード側と子ノード側として)注意しておいて欲しい。具体的には例えばノード6は上側の列には前から6番目の三角形の頂点として現われているし、下側の列には2番目の三角形の底辺部分として存在している。ということで、ノード6の子の情報が欲しい時は6番目の三角形を見れば良いし、ノード6の親の情報が欲しい時は2番目の三角形を見ればよい。
さて、次にこの三角形の列を元にビット列vを作る。作り方は以下に図示した通りであるがノードが上側(親)にある場合false、下側(子)にある場合trueといった形にする。さらに理由は後述するが先頭にtrueのビットを付け加える。
以上でLOUDSで用いるLBSと呼ばれるビット列の完成だ。信じられないような話であるが、以下で図示する通り、このビット列さえあれば木構造を辿っていくのに必要な情報は全て入手することができてしまう。
具体的には以下のような操作となる。(以下ではビット位置をp-1、ノード番号をnとする)
- ビット位置(=p-1)から子側のノード番号(=n)を求める ⇒ n = rank(v, p, true)
- ビット位置(=p-1)から親側のノード番号(=n)を求める ⇒ n = rank(v, p, false)
- ノード番号(=n)から子側のビット位置(=p-1)を求める ⇒ p = select(v, n, true)
- ノード番号(=n)から親側のビット位置(=p-1)を求める ⇒ p = select(v, n, false)
親子関係の探索は上の図で書いたように隣接したビットを辿っていけば良い。例えばノード12の親の情報はノード12の子側のビット位置を求め、それより前にあるfalseのビットを探しだせば良い。親ノードに対応するビット位置さえわかれば、そのノード番号を求めることは極めて簡単だ。
各ノードはビット列中に2回(上側と下側)登場するので、ノードの数×2bit + 1bit(先述のトリック用)しかメモリを必要としない。すさまじいまでの省メモリ化である。
おしまい。