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

今回は、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" となっています。