詳解 LOUDS (1) LOUDS とは

LOUDS


以前、「情報系修士にもわかるダブル配列」が好評だったので、続けて「情報系修士にもわかるLOUDS」を書きました。しかし、残念なことにあまり多くの人にわかってもらえてはいないようです。それで書き直すことにしました。今回は全12回に分けて解説します。

今回は、「トライ」ではなく「木構造」を扱います。

木構造というものについては皆様わかっているものとして進めます。


今回、例として使う木構造は次のようなものです。

「木構造」というと、それぞれのノードが最大 2個の子を持った「二分木」を連想される方も多いと思いますが、ここでの木は、子の個数に制限のないタイプです。

ラベルの番号は、浅いものから順に、横に振っていきます（幅優先）。

さて、この木をデータとして持つには、どのようなデータ構造がいいでしょうか。


例えば、単純な実装例を考えてみます。

配列の配列というやり方です。

プログラミング言語によって書き方は違いますが、だいたい

A[1] = [2, 3, 4]
A[2] = [5]
A[3] = []
A[4] = [6, 7, 8]
A[5] = []
...

のようなものです。

ここで、このような構造を扱うのにコンピュータはどのようにしているかを考えます。

まず、それぞれの親から、子ノードの配列を指す「ポインタ」のようなものが必要です。

また、子ノードの配列は可変長なので、それぞれの長さを覚えておく場所も必要になります。

これを図にすると、次のようになります。

左が親ノードで、それからそれぞれの子ノードの配列に対するポインタを持っていることを表しています。子ノード配列の左端にある青い数字は、配列の長さを表しています。


さて、この単純な実装をするのに、どれだけのメモリが必要かを考えます。

それぞれのノード番号は正の整数なので、例えば C などであれば unsigned int などを使います。

サイズは環境によって違いますが、最低 4バイト（32ビット）は必要になります。


ここで、メモリの中で数字というものがどのように格納されているかを考えます。

例えば、11 という数字は、4バイトの整数型に保存する時、ビット列は概念的には次のようになっています。

上のほうの桁が 0 ばかりですね。

整数型には、もっと短いものもあります。例えば、unsigned char は 1バイト（8ビット）でひとつの数字を表します。

ただ、短いぶんだけ表せる数値の上限も小さく、4バイト（32ビット）符号なし整数では 40億以上まで表せるのに対し、1バイト（8ビット）整数では 255 までしか表せません。ここでは例なので小さな数字しか使いませんが、実際はもっと大きな数字を入れる必要があります。

2バイト（16ビット）整数だと 65535 までですが、実用的にはこれでも足りません（例えば、少し大きめの辞書であれば、十万以上のエントリを持っています）。ですので、どうしても 1つの数字には最低 4バイト（32ビット）は必要になり、その中身はかなりの部分が 0 で埋まることになります。


上で挙げた単純な実装例を再掲します。

この表で右側にある、それぞれの子ノード配列の長さや、配列内の子ノード番号を表すのに、1つ 4バイト必要になります。子ノード配列は 11個あり、配列内の子ノードは 10個あります。ざっと 20個とすると、80バイト（640ビット）は必要です。さらに、それぞれの「親」から、自分の「子」の配列へのポインタにも 4バイト（32ビット）ずつ使うとすると、さらに 40バイト(320ビット）ほど必要になります。そう考えると、全部で 120バイト（960ビット）ほど使うことになります。ノードひとつにつき 12バイト（96ビット）ほどです。


簡潔データ構造というものを使うと、それよりもずっと小さなメモリ量で木構造を保存できます。

ここで解説する LOUDS というのもその一種です。


それでは、LOUDS を使うと上の木がどのようなデータによって表されるかを見てみましょう。

次のようなビット列になります。

23個の 0 と 1 があります。仕切りが太いところや点線のところがありますが、意味は次回以降説明します。ここではただのビット列として見てください。

保存する時はそれぞれ 1ビットずつしか使わないので、全部で 23ビットです。4バイト（32ビット）整数ひとつ分も使わないということです。ノードの番号などは、どこにも格納していません。しかし、これだけで元の木構造に関する必要十分な情報を持っています。


LOUDS で木構造を保存するのに必要なビット数は、（ノード数）× 2 + 1 で、1ノードあたりだいたい 2ビットです。ノード数がいくら増えても、この「1ノードあたり 2ビット」という割合は変わりません。上で挙げた単純な実装例に比べて、1/48 になります。

また、木構造を保存するだけでなく、この形のままで木構造に関するさまざまな操作（親ノードから子ノードの列挙、子ノードから親ノードの検索など）を行うことができます。


今回のまとめです。

  • 木構造を単純に実装すると、1ノードあたり数十ビットが必要になる。
  • LOUDS では、1ノードあたり 2ビットで木構造を保存できる。
  • LOUDS として保存したデータをそのまま使って、子ノードの列挙や親ノードの検索ができる。

次回は、「 LOUDS のデータをどのように作るのか」について見ていきます。