「木構造と自然数の重複あり集合は等価だよね」というはなし
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。
とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。
※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。
まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。
親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)
この木構造は以下の重複あり集合によって表現することができる。
{ 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。
何故、木構造が自然数の重複あり集合で表現できるか
上の木構造から重複あり集合を作り出す手順を説明する。
まずは最も番号が小さいノードの最初の子ノードの番号を書き出す。(1)の子ノードは(2, 3)なので
{ 2 }となる。同様に番号が小さい順番に最初の子ノードの番号を書き出す。(2)の子ノードは(4)なので
{ 2, 4 }また(3)の子ノードは(5)なので
{ 2, 4, 5 }さて(4)には子ノードがない。この場合直前に書きだした番号をもう一度書き出す。
{ 2, 4, 5, 5 }最後に(5)にも子ノードがないので
{ 2, 4, 5, 5, 5 }となる。めでたく木構造が自然数の重複あり集合になった。
次にこの集合を木構造に復元する。(1)の子ノードは集合の最初の数から(2番めの数-1)までに等しい。今回の場合は集合の最初の数が(2)で次が(4)なので(2,3)となる。
(1) → (2, 3)
(2)の子ノードは集合の2番目の数から(3番目の数-1)までに等しい。2番目の数が(4)で3番目の数が(5)なので(4)となる。同様に(3)の子ノードは(5)となる。
(1) → (2, 3) (2) → (4) (3) → (5)
(4)の子ノードは4番目の数から(5番目の数-1)に等しい。と言いたいところだが4番目の数が(5)で、5番目の数も(5)だ。この場合子ノードは存在しないと判断する。(5)の子ノードについても同様なので
(1) → (2, 3) (2) → (4) (3) → (5)
重複あり集合で表現することに何の意味があるか
さて上記の説明で木構造は自然数の重複あり集合として表現できることがわかった。これができると何がうれしいのか。
結論は「木構造を小さなビット数で表現できる」ということ。もっというなら(特に構造に仮定のない普通の)木構造を最も小さい情報量で表現できるのが「重複あり集合」だということ。
ではなんで唐突に「重複あり集合」なんてものがでてきたのか。天才のひらめきなのか。そんなことはなくて単純に「小さい」データ構造から順番にあたっていけばいい。
一番小さいデータ構造は重複なしの集合で、取りうる値が1からnの集合はnビットで表現できる。これは「その集合に入っている要素は1を、そうでない要素は0をいれたビット列」を考えればいい。
例えば
{ 2, 4, 5 }
※ただし取りうる値の最大値は8なら
00000000 #取りうる値の最大が8なので8つ0を用意 ↓ 01000000 #集合に2があるので2番目のビットを1にする ↓ 01010000 #集合に4があるので4番目のビットを1にする ↓ 01011000 #集合に5があるので5番目のビットを1にする
として表現できる。重複なし集合の次に小さなデータ構造は、木構造と等価な表現である「重複あり集合」だ。これをビット列で表現するには先程の「重複なし集合」で「n番目のビットを1にする」としていた箇所を「n番目の0の後に1を入れる」とすればいい。
00000000 #取りうる値の最大が8なので8つ0を用意 ↓ 001000000 #集合に2があるので2番目の0(=2番目のビット)のあとに1を入れる ↓ 0010010000 #集合に4があるので4番目の0(=5番目のビット)のあとに1を入れる ↓ 00100101000 #集合に5があるので5番目の0(=7番目のビット)のあとに1を入れる
この方式だと重複のある集合でもビット列にできる。例えば先程の木構造と等価な
{ 2, 4, 5, 5, 5 }なら
00000000 #取りうる値の最大が8なので8つ0を用意 ↓ 001000000 #集合に2があるので2番目の0(=2番目のビット)のあとに1を入れる ↓ 0010010000 #集合に4があるので4番目の0(=5番目のビット)のあとに1を入れる ↓ 00100101000 #集合に5があるので5番目の0(=7番目のビット)のあとに1を入れる ↓ 001001011000 #集合に5があるので5番目の0(=7番目のビット)のあとに1を入れる ↓ 0010010111000 #集合に5があるので5番目の0(=7番目のビット)のあとに1を入れる
となる。このビット列を集合に復元するには、1からnまでの数iに対して順番に「i番目の0の直後にある1の数」を調べればいい。
[001] 0010111000 #2つめの0の直後には1つ1がある
↓
{ 2 } # 集合がもつ2の数は1つだ
[001001] 0111000 #4つめの0の直後には1つ1がある
↓
{ 2, 4 } # 集合がもつ4の数は1つだ
[0010010111] 000 #5つめの0の直後には3つ1がある
↓
{ 2, 4, 5, 5, 5 } # 集合がもつ5の数は3つだこのビット列は「取りうる値の最大」に「集合の要素の数」を足しただけの長さがある。言い換えると最大値がnの自然数がm個ある場合、この重複あり集合はn+mビットで表現できる。
木構造の場合、集合の要素の最大は「幅優先で振った子ノードの番号」なので最大でも木のノード数と同じ。また要素の数は各ノードに対して子ノードの番号を保存するので、これまた木のノード数と同じ。
言い換えるとノード数がnの木構造を重複あり集合で表現した場合「最大値がnの自然数がn個ある」集合であるので2nビットで表現できる。
この2nビットというのが「木構造の情報量的下限」と言われている。英語で言うとInformation Theoretical Lower Bound、略してITLBである。「このデータ構造のITLBは何だろうか」などと口にすれば簡潔データ構造勢を気取ることが可能だ(嘘)。
配列じゃダメなんですか！？
単純に木構造を実装するなら子ノードの番号を保持した配列で表現できる。i番の最初の子ノードがj番ならarray[i]=jといった感じで。ただ配列はn log(n)ビットの情報量を必要とする。重複あり集合なら2nビットなので圧倒的に情報量が小さい。
では配列と重複あり集合、どこで差がついたのか？それは配列は「要素の順番を保持した重複あり集合」だから。ただの重複あり集合は要素の順番を保持していない。
普通に考えると要素の順番を保持していなかったら木構造なんて表現できない。では何故先ほどの例ではそれができたのかというとノードに「幅優先で番号を振った」から。こうすると子ノードの番号は必ず単調非減少になる。なので順番を気にしなくても重複あり集合の要素を昇順に並べるだけで適切な順番になるというわけ。
こういった「要素が単調非減少」のような元のデータ構造(今回は木構造)が「必ず持っている性質」を利用することで別の、持てる情報が少ないデータ構造(今回は重複あり集合)に置き換えることができ、結果的に情報量を削減できる。
俺が！俺たちがLOUDSだ！！
LOUDSとはまさしくここで説明した「木構造を重複あり集合で表現したもの」だ。通常、重複あり集合で木構造を表現すると「親ノードをたどる」「子ノードをたどる」といった操作が効率が悪くなる。しかし重複あり集合のビット列が簡潔ビットベクトル(完備辞書)で実装されていればこれらの操作が効率的に行える。従って木構造を情報量的下限となる重複あり集合で表現するというのは極めて効率的な選択であるといえる。これがLOUDSだ。
なのでLOUDSっていうと物々しい感じだけど、要するに「簡潔ビットベクトル(完備辞書)を使って重複あり集合を作りました」というだけだったりする。
