詳解 LOUDS (4) ビットの意味


今回は、LOUDS のそれぞれのビットが意味するところについて書きます。

最初の大きな木に、仮想的な 0番ノードを加えたものを再掲します。

これに対して LOUDS のデータを作る途中で、1番ノードに対応するブロックまで作り終わったところを考えます。

ここで、「親」の行が 1 であるブロックの、3つの "1" に注目してください。どうして 3つの "1" を置いたか覚えているでしょうか。これは、1番ノードが 2番、3番、4番という 3つの子ノードを持っているからでした。

この 3つの "1" のビットは、それぞれ左から 2番・3番・4番という、1番ノードの持つ子ノードを表しています。次に続く "0" は、そこで子ノードの列が終わりということを表しています。


この情報も、表に書き添えてみましょう。次のようになります。

「子」という行を加えました。

まずは、「親」の行が 1 となっているところの、4つのビットを見てください。

それぞれの "1" というビットに対して、「子」の行には、それぞれが表すノードの番号である 2, 3, 4 を書いています。"0" のビットに対しては "-" を埋めています。

続けて、2番ノードに対しても書いてみます。

2番ノードは 5番というひとつの子ノードを持っているため、1 0 というビット列を加えますが、この時 "1" は 5番ノードを、"0" は子ノード列の終わりを表しています。「子」の行で "5 -" と書いてあるのはそのことを表しています。

ここで、「親」の行が 0 となっている部分に戻ってみます。

このブロックは、親が「0番ノード」である子ノードを表しています。

「0番ノード」というのは、仮想的に付け加えたノードです。

図の中で、「0番ノード」の部分を見てみます。

「0番ノード」が、1番ノードという子ノードをひとつだけ持っていることがわかるでしょうか。

子ノードがひとつだけなので、ビット列は 1 0 となります。また、最初の 1 のビットが表すものは、0番の子ノードである 1番ノードです。ですので、「子」の行には "1" という数字を書きます。次の 0 は、0番ノードの子ノード列の終わりを表しているため、「子」の行は空にしておきます。


この手続きを最後まで続けると、次のような表ができます。

ここで、色をつけた "1" のビットに対応する「子」の行に、1 から 11 までのすべてのノード番号が 1回ずつ現れていることに注目してください。

ここで、「すべてのノードは、親ノードをひとつだけ持つ」ということによるものです。それぞれのノードは、その親ノードのブロックに必ず 1回だけ、それに対応する "1" のビットが置かれます。

それぞれの "1" に対するノード番号は、左から順番に 1, 2, 3, ... とひとつずつ増えていきます。

この「子」の行は、「親」と同じく説明のためのもので、実際にデータとして持っているわけではありません。



今回のまとめです。

  • 各ブロックのそれぞれの "1" のビットは、そのノードを親ノードとするそれぞれの子ノードを表している。
  • 各ブロックの最後の "0" のビットは、子ノード列の終わりを表している。
  • すべてのノードは、対応する "1" のビットをひとつだけ持っている。

次回は、LOUDS のデータから木構造が復元できることを示します。



今回の問題です。

前回と同じ、次の木構造に対して LOUDS のビット列を作り、それに「親」と「子」の行を追加してください。

今回も、仮想的な「0番ノード」を考えるとわかりやすいかと思います。



前回の答えです。

この木構造に対して LOUDS のビット列を作り、それに「親」の行を追加して、ブロックに分けるというものでした。

答えは、次のようになります。


作り方を復習してみましょう。

まず、与えられた木構造に仮想的な「0番ノード」を追加します。

この木構造のそれぞれのノードに対して、「ノードごとに、そのノードが持つ子の数だけ "1" を置き、それに続けてひとつの "0" を置く」というルールを適用していきます。

まず、 0番ノードに対して、子の数だけ "1" を置き、最後に "0" をひとつ置きます。子は 1番ひとつなので、ひとつの "1" とひとつの "0"、つまり1 0 を置くことになります。0番ノードに注目して処理を行ったので、「親」の行には 0 と書きます。

次は 1番ノードです。子は 2番 ひとつなので、"1" ひとつと "0" ひとつの 1 0 になります。「親」の行には 1 を埋めます。

2番ノードは、子が 3番と 4番の 2つなので、"1" 2つと "0" ひとつの 1 1 0 です。「親」の行は 2 になります。

3番ノードは、子がないので "1" はなく、0 だけです。「親」の行は 3 です。

この手順を最後まで繰り返すことで、上に挙げた解答になります。