詳解 LOUDS (5) 木構造の復元

LOUDS


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

次のような手順により実現できます。


まず、木構造の深さ 0 に、根（0番ノード）がひとつある状態から始め、0番ノードを「今見ている親ノード」、LOUDS データの最初のビットを「今見ているビット」とした上で、次の手順をビット列の終わりまで行います。

今見ているビットが "1" であれば：
  「今見ている親ノード」に対して子ノードを増やす。番号は、前に増やした子ノードの番号に 1 を足したもの。
今見ているビットが "0" であれば：
  「今見ている親ノード」の番号に 1 を足したものを、新しい「今見ている親ノード」とする。

次のビットに移る。

とても単純な手順なのですが、これだけではイメージがわかないかと思います。

実際のデータを元にしてやってみることにします。できれば、紙に書いてやってみてください。


最初に挙げた大きな木構造に対する LOUDS のビット列は次のようなものでした。ここでは、ビット列のみに注目します。

これに対して、上記の手順を適用してみます。

まず、最初に 0番ノードを最初に置き、それを「今見ている親ノード」とします。「今見ている親ノード」は、太線で、赤い矢印をつけています。

また、「今見ているビット」は左端のビットになります。「今見ているビット」は、薄く色をつけたところです。

今見ているビットは "1" なので、「今見ている親ノード」（0番ノード）に子ノードを増やします。番号は、0 の次で 1 とします。

「今見ているビット」をひとつ右に移します。

今見ているビットが "0" なので、「今見ている親ノード」を、0番ノードから 1番ノードに移します。

次のビットに移ります。

今見ているビットは "1" なので、「今見ている親ノード」（1番ノード）に子ノードを増やします。番号は、1 の次で 2 とします。

次のビットに移ります。

今見ているビットは "1" なので、「今見ている親ノード」（1番ノード）に子ノードを増やします。番号は、2 の次で 3 とします。

次のビットに移ります。

今見ているビットは "1" なので、「今見ている親ノード」（1番ノード）に子ノードを増やします。番号は、3 の次で 4 とします。

次のビットに移ります。

今見ているビットが "0" なので、「今見ている親ノード」を、1番ノードから 2番ノードに移します。

次のビットに移ります。

今見ているビットは "1" なので、「今見ている親ノード」（2番ノード）に子ノードを増やします。番号は、4 の次で 5 とします。

次のビットに移ります。

今見ているビットが "0" なので、「今見ている親ノード」を、2番ノードから 3番ノードに移します。

次のビットに移ります。

今見ているビットが "0" なので、「今見ている親ノード」を、3番ノードから 4番ノードに移します。

以降は省略しますが、このような手順で木構造が復元できることがわかると思います。


この手順の中では、あえて「親」と「子」の行には触れませんでした。

改めて、「親」と「子」の行の意味について見てみます。

例えば、上の手順の中で、「今注目しているビット」が次のようになっている状態に戻ってみます。

「今見ている親ノード」（1番ノード）に、3番ノードという子ノードを増やすところです。

ここで、表で「今注目しているビット」の上下を見て下さい。

上（「親」）の行は "1"、下（「子」）の行は "3" となっています。

これは、このビットが「1番ノードを親とする、3番ノード」を表していることを意味します。

そういうわけで、ここでは 1番ノードを親として、それに 3番ノードを子として追加することになるわけです。


今回のまとめです。
  • LOUDS のビット列から、元の木構造を復元することができる。

実際に LOUDS を利用する時には、木構造を別の場所に展開することなく、データそのままの形で、「親ノードから子ノードを列挙する」「子ノードから親ノードをたどる」といった操作を行えます。その詳細については、次回以降解説します。


今回の問題です。

次のビット列から、格納された木構造を復元してみてください。


前回の答えです。

"1" のビットが、左から順番に、1, 2, 3... というノード番号に対応しています。