こんにちは。レトリバのリサーチャーの木村@big_wingです。 4月から静岡県の浜松市に引っ越しをして、引き続きフルリモートで働いています。ずいぶん久しぶりになってしまいましたが、今回は簡潔データ構造シリーズの続きで順序木に対する簡潔データ構造について、導入編ということで順序木に対する3つの簡潔表現を紹介したいと思います。

1回目の記事はこちら (簡潔データ構造の概略)
2回目の記事はこちら (ビットベクトルに対するrank演算)
2.5回目の記事はこちら (ビットベクトルに対するselect演算)

簡潔データ構造の書籍としてはNavarro氏の本、日本語で書かれたものとしては定兼氏の本と岡野原氏の本があります。また今回紹介する順序木に対する簡潔データ構造を日本語入力に応用したものとして徳永氏の本があります。

順序木に対する簡潔データ構造

順序木に対する簡潔データ構造

今回はノード数が $n$ である根付き順序木を対象として考えます。まず根付き順序木をどのくらいの大きさで表現可能か確認しましょう。実は1回目の記事ですでに紹介してしまいましたが、ノード数が $n$ である根付き順序木の数は、カタラン数と呼ばれる数 $C_n = \frac{1}{n+1} \binom{2n}{n}$ を用いて $C_{n-1}$ と表現することができます。そのため情報理論的下限は $L = 2\it{n} - \rm{\Theta}(lg\it{n}\rm{)}$ ビットとなります。ここで $\rm{lg}$ は2を底とする対数であり、また $\rm{\Theta}(lg\it{n}\rm{)}$ は漸近的に $\rm{lg}\it{n}$ によって上下から抑えることができる関数の集合です。この情報理論的下限に対し、従来のデータ構造として例えばポインタベースでの表現を考えると、一つのノードの表現には $\rm{\Theta}(lg\it{n}\rm{)}$ ビット必要であり、木構造全体では $\rm{\Theta}(\it{n}\rm{lg}\it{n}\rm{)}$ ビットとなります。これは先程の情報理論的下限を大きく上回っています。目標は $2\it{n}$ ビットに漸近する大きさで根付き順序木を表現するデータ構造を与えることです。

このような根付き順序木に対して代表的な簡潔表現として以下の3つがあります。

LOUDS表現(Level-Order Unary Degree Sequence representation)
BP表現(Balanced Parentheses representation)
DFUDS表現(Depth-First Unary Degree Sequence representation)

LOUDS、BP、DFUDSと進むにつれて木構造に対するよりリッチな演算が可能ですが、より複雑な索引が必要となります。以降これらの簡潔表現を順に説明していきますが、導入編の今回はそれぞれの表現についてだけ紹介し、具体的にサポートする木構造上での演算や実現方法については次回以降にしたいと思います。

LOUDS表現

LOUDS表現(Level-Order Unary Degree Sequence representation)は $n$ 個の $1$ と $n + 1$ 個の $0$ を用いた計 $2n + 1$ のビット列 $L[1,2n + 1]$ , $L[i] \in \{0,1\}$ ビットで根付き順序木を表現します。符号化のルールは、

先頭2ビットは $10$ とする
幅優先順に順序木を走査し、子の数と同じ数の $1$ を並べ、その後に1個の $0$ を置く

です。2. がまさにLevel-Order Unary Degree Sequenceとなっています。具体例で上記を確認してみましょう。図1に根付き順序木の例を示し、これに対応するLOUDS表現を図2に示します。上記のルールによって図1のノード数 $9$ の根付き順序木に対して最終的に $1$ が9個と $0$ が10個の計 $2\times 9 + 1 = 19$ ビットの表現が得られます。以下が具体的な手順です。

先頭2ビットに10を加える。ここまでのビット列は10
次に根ノードである $F$ ノードから幅優先順に木を走査する。 $F$ ノードの子ノードは $B$ と $G$ の2個なので $1$ を2個並べたあとに1個の $0$ を置く。ここまでのビット列は10110
幅優先順に次のノードは $B$ 。 $B$ ノードの子ノードは $A$ と $D$ の2個なので、やはり $1$ を2個並べたあとに1個の $0$ を置く。ここまでのビット列は10110110
幅優先順に次のノードは $G$ 。 $G$ ノードの子ノードは $I$ の1個なので、 $1$ を1個並べたあとに1個の $0$ を置く。ここまでのビット列は1011011010
幅優先順に次のノードは $A$ 。 $A$ ノードに子ノードは存在しないので、1は並べずに1個の $0$ のみを置く。ここまでのビット列は10110110100
以下最後まで省略
幅優先順に最後のノードは $H$ 。 $H$ ノードに子ノードは存在しないので、1は並べずに1個の $0$ のみを置く。これで最終的に図2のビット列1011011010011010000となる

上記の手順でLOUDS表現の構築がイメージできたでしょうか？最初の先頭2ビットに $10$ を加える箇所は、根ノードにさらなる親ノードが存在すると仮想的に想定していただければ直感的に理解しやすいかもしれません。

LOUDSでは幅優先順に $i$ 番目に訪問したノードがビットベクトル中の $i$ 番目に出現する $1$ に対応しています。今回は演算については紹介しませんが、図2の赤字の各ノードに対応する子ノードを見てなんとなく木構造上の演算ができそうな気持ちになれるでしょうか？LOUDSは以下に紹介するBP表現やDFUDS表現に比べて実現できる機能は少ないですが、0/1上のrank、select演算で木構造上の様々な演算を実現でき、最もシンプルな簡潔表現となっています。

BP表現

BP表現(Balanced Parentheses representation)は $n$ 個の開括弧 $($ と $n$ 個の閉括弧 $)$ の計 $2n$ 個の括弧を用いて $2n$ ビットで根付き順序木を表現します。各ノードが１つの開括弧 $($ と1つの閉括弧 $)$ のペアで表現され対応が取れていることがBP表現(Balanced Parentheses representation)の由来です。

ここでLOUDSでは0/1で表現していたものをなぜわざわざ括弧で表現するのか、0/1でも同じではないかと思われるかもしれません。わざわざ括弧を用いる理由として、今回は紹介しないBP表現での基本演算の定義があります。先程述べたようにBP表現では１つの開括弧 $($ と1つの閉括弧 $)$ の対応するペアで表現しており、このような対応関係にある括弧を対象とした演算が基本演算で定義されます。そのため、このような対応関係のある括弧についての演算を定義、実現するために括弧による表現が用いられているのだと思います(間違っていたらご指摘下さい…)。

さて本題に戻ってBP表現の符号化のルールは、

深さ優先順に順序木を走査し、行きの訪問で開括弧を1個置き、帰りの訪問で閉括弧を1個置く

です。具体例で上記を確認してみましょう。以下に図1の根付き順序木の例を再掲し、これに対応するBP表現を図3に示します。上記のルールによって図1のノード数 $9$ の根付き順序木に対して最終的に開括弧が9個と閉括弧が9個の計 $2\times 9 = 18$ ビットの表現が得られます。以下が具体的な手順です。

根ノードである $F$ ノードから深さ優先順に木を走査する。行きで $F$ ノードを訪問したので開括弧を置く。ここまでの表現は (
深さ優先順に次のノードは $B$ 。行きで $B$ ノードを訪問したので、開括弧を置く。ここまでの表現は ((
深さ優先順に次のノードは $A$ 。行きで $A$ ノードを訪問したので、開括弧を置く。また $A$ ノードに子は存在しないので戻る、帰りで $A$ ノードを訪問したので閉括弧を置く。ここまでの表現は((()
深さ優先順に次のノードは $D$ 。行きで $D$ ノードを訪問したので、開括弧を置く。ここまでの表現は((()(
深さ優先順に次のノードは $C$ 。行きで $C$ ノードを訪問したので、開括弧を置く。また $C$ ノードに子は存在しないので戻る、帰りで $C$ ノードを訪問したので閉括弧を置く。ここまでの表現は((()(()
以下最後まで省略
深さ優先順に走査をして最後は帰りで $D$ ノードを訪問するので閉括弧を置く。最終的に図3の表現((()(()()))((())))となる

上記の手順でBP表現の構築がイメージできたでしょうか？BP表現では深さ優先順に $i$ 番目に訪問したノードが $i$ 番目に出現する開括弧に対応しています。BP表現は最初に紹介したLOUDS表現よりもリッチな木構造上の演算が可能です。

DFUDS表現

DFUDS表現(Depth-First Unary Degree Sequence representation)はBP表現とは異なりますが、 $n$ 個の開括弧 $($ と $n$ 個の閉括弧 $)$ の計 $2n$ 個の括弧を用いて $2n$ ビットで根付き順序木を表現します。符号化のルールは、

先頭1ビットは開括弧とする
深さ優先順に順序木を走査し、子の数と同じ数の開括弧を並べ、その後に1個の閉括弧を置く

です。2. がまさにDepth-First Unary Degree Sequenceとなっています。具体例で上記を確認してみましょう。以下に図1の根付き順序木の例を再掲し、これに対応するBP表現を図4に示します。上記のルールによって図1のノード数 $9$ の根付き順序木に対して最終的に開括弧が9個と閉括弧が9個の計 $2\times 9 = 18$ ビットの表現が得られます。以下が具体的な手順です。

先頭を開括弧とする。ここまでの表現は (
深さ優先順に順序木を走査する。最初のノードは $F$ であり、その子ノードは $B$ と $G$ の2個なので開括弧をを2個並べたあとに1個の閉括弧を置く。ここまでの表現は((()
深さ優先順に次のノードは $B$ であり、その子ノードは $A$ と $D$ の2個なので開括弧をを2個並べたあとに1個の閉括弧を置く。ここまでの表現は((()(()
深さ優先順に次のノードは $A$ であり、子ノードは存在しないので開括弧のみを1個を置く。ここまでの表現は((()(())
以下最後まで省略
深さ優先順に最後に訪問するノードは $H$ であり、開括弧のみを1個を置く。これで図4の最終的な表現((()(())(()))()())となる

上記の手順でDFUDS表現の構築がイメージできたでしょうか？DFUDS表現では図4のように各ノードが深さ優先順に括弧列の連続する部分列として表現されます。先頭に開括弧を1つ置くことで全体として開括弧と閉括弧の数が等しくなりバランスしています。

まとめ

今回は根付き順序木に対する代表的な3つの簡潔表現であるLOUDS、BP、DFUDSについて紹介しました。表現方法についてのみで具体的な演算が出てこなかったため、異なる表現方法があるとこの嬉しさ、楽しさを感じるのは難しかったかもしれません。次回以降では具体的な演算についても紹介し、そのあたりのことを感じていただければと思います。

Retrieva TECH BLOG

簡潔データ構造第３回: 順序木に対する簡潔データ構造 (導入編)

順序木に対する簡潔データ構造

LOUDS表現

BP表現

DFUDS表現

まとめ