詳解 LOUDS (2) ビット列を作ってみる

今回は、前回紹介した LOUDS のデータをどのように作るかについて説明します。

まず、対象とする木構造を再掲します。

この木構造に対応するデータが、次のようなビット列になるということを前回お話しました。

このビット列の作り方は、次のようになります。ビット列は左から右に向けて作っていきます。

左端に、"1 0" という 2つのビットを置く。
それぞれのノードごとに、そのノードが持つ子ノードの数だけ "1" を右に置き、それに続けてひとつの "0" を右に置く。

実際に作る過程を見てみましょう。

まず、最初に 1 0という 2つのビットを置きます。

これは、対象とする木構造によらず、先頭に置くものです。

それに続き、1番ノードの持つ子ノードの数だけ、"1" を置きます。

さて、1番ノードは子ノードをいくつ持っているでしょうか。

図を再掲します。

答えは、2番・3番・4番の「3個」です。ですので、"1" を 3つと最後に "0" をひとつ、つまり 1 1 1 0 を置くことになります。最初に置いた 1 0 と合わせて、全部で 6ビットになります。

次は、2番です。2番の子ノードは 5番ひとつだけですので、ひとつの "1" とひとつの "0" 、つまり 1 0 を置きます。それまでの 6ビットと合わせて、全部で 8ビットになります。

2番の次は、番号順に 3番です。3番は、子ノードを持っていません。「子ノードの数だけ "1" を置く」というルールなので、子ノードのないノードに対しては、"1" を置きません。しかし「最後に 0 を置く」というのはそのままです。ですので、3番に対するビットは、"0" ひとつということになります。これで 9ビットです。