木構造

2024年11月13日 #BTree #Trie

1. 概要

木構造 (tree structure) はデータを階層的に表現するためのデータ構造である。ノード (頂点) とエッジ (辺) で構成されるグラフ構造の一種だが、閉路を持たない DAG である。

1. 概要
2. AVL 木
3. van Emde Boas 木
4. トライ
5. 参照

2. AVL 木

AVL 木 (AVL tree) [1] はすべてのノードについて左右の部分木の高さの差が 1 以下であるという条件を保つ二分探索木である。1962 年に Adelson-Velsky と Landis によって提案された最初の自己平衡二分探索木として知られ、名称は 2 人の姓に由来する。

二分探索木は挿入される順序によっては一方向に伸びた連結リストと変わらない形になり、その場合の探索は $O(n)$ に劣化する。AVL 木はノードの挿入や削除のたびに木の形を修正することで、格納されている要素数を $n$ として木の高さを常に $O(\log n)$ に保ち、探索・挿入・削除のいずれも $O(\log n)$ で実行できることを保証する。

2.1. 平衡条件と木の高さ

あるノードの左部分木の高さと右部分木の高さの差を平衡係数 (balance factor) と呼ぶ。AVL 木の平衡条件は「すべてのノードの平衡係数が $-1$ , $0$ , $+1$ のいずれかである」ことと言い換えられる。各ノードは自身の平衡係数、あるいは部分木の高さを保持しておき、更新操作のたびに再計算する。

この条件がどの程度の高さを保証するかは、逆に「高さ $h$ の AVL 木が持ちうる最小のノード数 $N(h)$ 」を考えると分かりやすい。ノード数が最小になるのは根の一方の部分木の高さが $h-1$ 、他方が平衡条件ぎりぎりの $h-2$ となる場合であるから、 $N(h) = N(h-1) + N(h-2) + 1$ という漸化式が成り立つ。これはフィボナッチ数列と同じ増え方であり、ここから木の高さは $h \lt 1.44 \log_2 (n+2)$ で抑えられることが導かれる。つまり最悪の場合でも、完全に平衡した二分木の高さの 1.44 倍を超えない。

2.2. 回転による平衡の回復

挿入や削除によって平衡条件が崩れた場合は、回転 (rotation) と呼ばれる操作によって部分木の形を組み替える。回転は親子関係を付け替えるだけの局所的な操作であり、二分探索木の条件である「左部分木 < ノード < 右部分木」の順序関係を保ったまま木の高さを 1 段減らす。

右回転 (ノード y を軸として x を引き上げる)

       y                    x
      / \                  / \
     x   C      ──→       A   y
    / \                      / \
   A   B                    B   C

  中間順巡回は A x B y C のまま変わらない

平衡が崩れる形は、不均衡なノードから見てどちら側の部分木が深いかによって 4 通りに分類される。左の子の左部分木が深い場合 (LL) は右回転、右の子の右部分木が深い場合 (RR) は左回転の 1 回で回復する。一方、左の子の右部分木が深い場合 (LR) は左の子を左回転して LL の形にしてから右回転する、という 2 回の回転が必要になる。右の子の左部分木が深い場合 (RL) も同様である。

挿入の場合、崩れた平衡は最初に見つかった不均衡なノードに対して 1 回 (二重回転を数えても 2 回) の回転を施すだけで回復する。これに対して削除の場合は、回転によって部分木の高さそのものが減るため、その影響が親へと伝播し、根に向かって平衡条件の確認を繰り返す必要がある。このため削除では最悪 $O(\log n)$ 回の回転が発生しうる。

2.3. 他の平衡二分探索木との比較

AVL 木の平衡条件は赤黒木のそれよりも厳しく、同じ要素数に対して木の高さが低くなる。このため探索は AVL 木の方が高速である一方、平衡を保つために必要な回転の回数は多くなる。読み出しが支配的な用途では AVL 木が、挿入や削除が頻繁な用途では赤黒木が選ばれることが多い。

ただしこれらはいずれも 1 つのノードが 2 つの子しか持たない二分木であり、木の高さがそのままノードの参照回数となる。ノード 1 つの参照コストが大きい外部記憶では、1 ノードあたりの子の数を増やして高さを下げる B 木系の構造が用いられる。

3. van Emde Boas 木

van Emde Boas 木 (vEB; ファン・エムデ・ボアス木) [2] は大規模な整数集合に対して高速な存在判定、範囲検索、前後検索などを行うことのできるデータ構造である。キー範囲が事前に決まっている全体集合 (universe) での優先度付きキューや集合操作を効率的に実行する。整数の全体集合 $\{0,1,\ldots,n-1\}$ に対して、挿入、削除、検索、先行値 (一つ先の要素)、後続値 (一つ後の要素)、最小値、最大値の取得といった操作を $O(\log\log n)$ 時間で実行できる。これは従来の平衡二分木やヒープの $O(\log n)$ 時間を大幅に改善した。

この構造は全体集合を $\sqrt{n}$ 個のクラスタに分割し、各クラスタは再帰的に同じように分割されたツリー構造を持つ。具体的にはサイズ $n$ の全体集合 $U$ に対して、値となる整数を上位と下位のちょうど半分に分割し (つまり上位 $\sqrt{n}$ ビットと下位 $\sqrt{n}$ ビットに分割し)、上位を下層クラスタのインデックス、下位を下層を再帰的に検索するパラメータとして使用する。

Figure 1 は $n=256$ (8 ビット) の van Emde Boas 木に値 162 を挿入する例である。まず、162 = 0b10100010 は上位 4 ビット 10 = 0b1010 と下位 4 ビット 2 = 0b0010 に分割され、第一階層 ${\rm vEB}_{256}$ のクラスタ 10 へ値 2 で進む。第2階層 ${\rm vEB}_{16}$ では値 2 = 0b0010 を上位 2 ビット 0 = 0b00 と下位 2 ビット 2 = 0b10 に分割し、クラスタ 0 へ値 2 で進む。この操作を葉まで繰り返し、最終的に存在を表す true を設定する。

Figure 1. van Emde Boas 木での挿入操作。末端をブール値ではなく値を格納できるようにすれば Key-Value 型に拡張できる。

各ノードが、そのノードの配下に含まれる値の最小値と最大値を記録しているため、ある値の一つ前の値 (predecessor) と一つ後の値 (successor) も効率よく検索することができる。Figure 2 は $n=256$ の van Emde Boas 木において、値 169 = 0b10101001 の先行値と後続値を求める例である。探索する値そのものが木に格納されている必要はない。

後続値の探索では、まず 169 の上位ビットから所属するクラスタを求め、下位ビットをそのクラスタ内での値として扱う。ここでクラスタが保持している最大値と下位ビットを比較し、下位ビットの方が小さければ後続値は同じクラスタ内に存在することが確定するため、そのクラスタを再帰的に探索する。そうでなければ後続値は別のクラスタにあるため、要素を持つクラスタの集合を記録した summary を辿って次に要素を持つクラスタを見つけ、そのクラスタの最小値を返す。いずれの場合も再帰は一方向にしか進まないため $O(\log\log n)$ で完了する。

Figure 2. 値 169 に対する先行値 162 と後続値 227 の探索経路、および後続値を求める ${\rm successor}()$ の擬似コード。各ノードが保持する最小値と最大値によって、部分木を降りる前にその中に答えが存在するかを判定できる。

4. トライ

トライ (trie; 接頭辞木、プレフィックス木) [3] は文字列をキーとする集合や連想配列を表現するための木構造である。名称は retrieval に由来する。

二分探索木やハッシュ表がキーをそのままノードに格納するのに対して、トライはキーを 1 文字ずつ辺のラベルに分解し、根から辿った経路そのものがキーを表す構造を取る。したがってノードはキーを保持せず、根からそのノードに至るまでに辿った辺のラベルを連結したものが、そのノードに対応する文字列となる。キーの終端に対応するノードには、そこまでの経路が 1 つのキーを構成することを示す印を付けておく。

キー集合 {car, cart, cat, do, dog} に対するトライ

  (root)
    ├── c ── a ──┬── r ──●── t ──●
    │            │      car     cart
    │            └── t ──●
    │                   cat
    └── d ── o ──●── g ──●
                do      dog

探索はクエリーの文字を先頭から 1 文字ずつ読みながら対応する辺を辿るだけであり、キーの長さを $|k|$ として $O(|k|)$ で完了する。この計算量は木に格納されているキーの総数 $n$ に依存しない。平衡二分探索木の $O(|k| \log n)$ と比べて有利であり、また不一致が判明した時点で打ち切れるため、ハッシュ表のようにキー全体を読む必要もない。

トライのより本質的な利点は、共通の接頭辞を持つキーが木の同じ経路を共有することにある。これによってある接頭辞から始まるキーの集合は 1 つの部分木として表現され、前方一致検索はその部分木を走査するだけの操作になる。さらに、各ノードの子を文字の順序に従って並べておけば深さ優先探索によってキーを辞書順に列挙できる。ハッシュ表では失われるこれらの性質が、トライを文字列辞書の実装として有力にしている。

4.1. 空間効率の問題

素朴なトライの実装上の課題は空間効率にある。各ノードがアルファベット $\Sigma$ の要素数だけの子ポインタ配列を持つ実装では、遷移は $O(1)$ で行える一方、空間計算量は $O(n |\Sigma|)$ となる。ASCII 文字だけでもノードあたり 128 要素の配列が必要であり、その大半は未使用のまま残る。Unicode を扱う場合には現実的でない。

この問題に対しては、各ノードの子を実際に存在する分だけ連結リストやソート済み配列、ハッシュ表で保持する方法がまず考えられる。ただしいずれも空間と遷移速度のトレードオフであり、根に近いノードほど子が多く、葉に近いノードほど子が少ないという偏りにも対応できない。実用的なトライの実装は、次に述べるような構造の変換や表現の工夫によってこの問題を解決している。

4.2. パトリシア木

素朴なトライではキーの文字数だけノードが連なるため、他のキーと分岐しない部分にも中間ノードが並ぶ。上の例では cart の t や dog の g がこれにあたる。子を 1 つしか持たないノードの連鎖を 1 本の辺にまとめ、辺のラベルを 1 文字ではなく文字列とすることでノード数を削減した構造をパトリシア木 (PATRICIA tree) あるいは基数木 (radix tree)、圧縮トライ (compressed trie) と呼ぶ。

この圧縮によって、分岐のないノードが取り除かれ、ノード数はキーの総数 $n$ に対して $O(n)$ に収まる。キーの長さに比例してノードが増えることがなくなるため、長いキーを扱う場合に効果が大きい。

4.3. ダブル配列

ダブル配列 (double array) [4] はトライを base と check という 2 本の整数配列だけで表現する手法である。状態 $s$ から文字 $c$ への遷移先を $t = {\rm base}[s] + c$ として求め、 ${\rm check}[t] = s$ が成り立つときにのみその遷移が有効であると判定する。

遷移が配列の添字計算だけで済むため $O(1)$ で辿ることができ、しかもノードごとの子ポインタ配列を持たないため空間効率も良い。一方で、異なる状態の遷移先が同じ添字に衝突しないように ${\rm base}[s]$ を決める必要があり、構築のコストが高く、キーの動的な追加も苦手である。更新の少ない静的な辞書に向いた表現であり、MeCab や Kuromoji といった形態素解析器の辞書引きに用いられている。

4.4. 簡潔表現

木の形状そのものをビット列として符号化し、情報理論的な下界に近い空間で表現する手法もある。LOUDS (level-order unary degree sequence) は木を幅優先順に走査しながら各ノードの子の数を単進符号で並べたビット列で表現するもので、 $n$ ノードの木を約 $2n$ ビットで保持できる。

このように表現された木を辿るには、ビット列に対する ${\rm rank}$ (先頭から指定位置までの 1 の個数) と ${\rm select}$ ( $i$ 番目の 1 の位置) を定数時間で求める補助構造が必要になる。これらは簡潔データ構造 (succinct data structure) と呼ばれる分野を構成する。

4.5. FST

トライが共有するのはキーの接頭辞のみであり、walking と running のように接尾辞が共通するキーは別々の経路として保持される。この接尾辞も共有できるように、等価な部分木を 1 つにまとめて木ではなく非巡回グラフとしたものが DAWG (directed acyclic word graph) であり、これに出力を付随させて連想配列として使えるようにしたものが FST (finite state transducer; 有限状態トランスデューサ) である。

FST は状態遷移に出力を伴うオートマトンとみなすことができ、経路上の出力を累積した値がそのキーに対応する値となる。トライよりもさらにコンパクトになりながら辞書順の走査や前方一致検索の性質を保つため、全文検索の語彙目録のような大規模な文字列辞書に適している。Apache Lucene はこの表現を採用している。

4.6. 応用

トライは文字列をキーとする検索が求められる場面で広く用いられている。全文検索エンジンの語彙目録や形態素解析器の辞書のほか、入力途中の文字列から候補を列挙するオートコンプリート、複数のパターンを同時に照合する Aho-Corasick 法などがある。またアルファベットをビットとみなせば任意のバイト列に適用でき、IP ルーティングテーブルの最長前方一致検索にも用いられる。

なお、本ページで先に述べた van Emde Boas 木も、整数をビット列とみなしたときのトライに各ノードの最小値・最大値と補助構造を加えたものと見ることができる。キーを固定長のビット列として上位から順に辿るという点で、両者は同じ着想に基づいている。

5. 参照

ADELSON-VELSKY, Georgy; LANDIS, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences, 1962, 146: 263-266.
VAN EMDE BOAS, Peter. Preserving order in a forest in less than logarithmic time. In: 16th Annual Symposium on Foundations of Computer Science (sfcs 1975). IEEE, 1975. p. 75-84.
FREDKIN, Edward. Trie memory. Communications of the ACM, 1960, 3.9: 490-499.
AOE, Jun-ichi. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, 1989, 15.9: 1066-1077.

木構造

1. 概要

2. AVL 木

2.1. 平衡条件と木の高さ

2.2. 回転による平衡の回復

2.3. 他の平衡二分探索木との比較

3. van Emde Boas 木

4. トライ

4.1. 空間効率の問題

4.2. パトリシア木

4.3. ダブル配列

4.4. 簡潔表現

4.5. FST

4.6. 応用

5. 参照

B-Tree

B+Tree

論文翻訳: Lower Bounds for External Memory Dictionaries

論文翻訳: An Introduction to Bε-trees and Write-Optimization

論文翻訳: PRESERVING ORDER IN A FOREST IN LESS THAN LOGARITHMIC TIME

木構造

1. 概要

Table of Contents

2. AVL 木

2.1. 平衡条件と木の高さ

2.2. 回転による平衡の回復

2.3. 他の平衡二分探索木との比較

3. van Emde Boas 木

4. トライ

4.1. 空間効率の問題

4.2. パトリシア木

4.3. ダブル配列

4.4. 簡潔表現

4.5. FST

4.6. 応用

5. 参照

B-Tree

B+Tree

論文翻訳: Lower Bounds for External Memory Dictionaries

論文翻訳: An Introduction to Bε-trees and Write-Optimization

論文翻訳: PRESERVING ORDER IN A FOREST IN LESS THAN LOGARITHMIC TIME