トライ (データ構造)

トライ木やプレフィックス木とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックスがあり、ルートには空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。

キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。

トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジに対応する記号はその順序が暗黙のうちに決定される。

キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。

トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。

trie という名称は "retrieval"が語源であるため、"tree" と同じ発音を用いる。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。

1. 利点と欠点
--------

2分探索木と比較したトライ木の主な利点:

キー検索が高速である。長さ //m// のキー検索の時間計算量は最悪でも O である。2分探索木での時間計算量は O である。ただし//n// は木を構成するノード数である。トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。
多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーがノードを共有するためである。
トライ木は最も長いプレフィックスとマッチするよう探索を進められるので、最も長いプレフィックスが共通なキーを効率的に捜せる。また、そのような共通プレフィックスに対応したノードに新たな値を格納できる。
トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある。トライ木の欠点:

トライ木はキーの順序を与えるが、辞書順でなければならない。
トライ木は入力ノード数に対して深さが極めて大きくなりうる。例えば、少数の非常に長い文字列を格納するトライ木などである。
トライ木のアルゴリズムは単純な2分探索木よりも複雑である。
データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる。

トライ木はキーの長さが可変でキー検索が失敗する場合があるとき、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。

2. 性能の定量化
---------

トライ木の探索時間は、キー文字列の長さが一定であれば O とみなせるが、厳密には異なる。キーが //N// 個あるとき、文字の種類が //k// なら、最も長いキーは //logkN// 文字がその長さの下限となる。このことから、トライ木の探索時間は厳密には Ω であり、これは2分探索と同じである。

この結果は必ずしもトライ木の利点を否定するものではない。トライ木の高速性の利点は各ノードでの比較が高速である点にある。2分探索での一回の比較は比較対象の短いほうを //m// 文字としたとき O が最悪時間となる。一方トライ木では各ノードでの比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。というのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うため、比較時間が長くなってしまうからである。

3. 応用
-----

3.1. 他のデータ構造の代替
---------------

既に述べたようにトライ木は2分探索木に比較して様々な利点がある。トライ木はハッシュテーブルの代替としても使用でき、次のような利点がある:

理論上、平均検索性能は同じだが、実測するとトライ木の方が速い。
ハッシュテーブルの検索の最悪時間は O である。
キーの衝突が発生しない。
ハッシュ関数を用意する必要がない。
トライ木ではキーの辞書順を自動的に生成できる。トライ木をハッシュテーブルの代替として使用した際の欠点は次の通り:

格納されている全キーを文字列として取り出すのが簡単ではない。
ハッシュテーブルよりもメモリ効率が悪い。
ハッシュテーブルはプログラミング言語に最初から用意されているが、トライ木はそうではない。

3.2. 辞書表現
---------

トライ木の典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている。トライ木の利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。しかし、単に辞書の単語を格納するだけなら、非輪状決定性有限オートマトンのほうがメモリ効率がよい。

トライ木はスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。

3.3. 擬似コード
----------

以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、children は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。 function find { if  { # 基本ケース。キーが空文字列の場合 return is node terminal? } else { # 再帰ケース c = first character in key # キーが空でないので、その1文字目を取り出す tail = key minus the first character # 1文字目を除いた文字列 child = node.children[c] # 文字コードが配列キーとなる if  { # 子がないので再帰できないがキーは空になっていない return false } else { return find } } }

3.4. ソート
--------

辞書順にキー文字列をソートする処理は次のようにトライ木で実現される:

全キーをトライ木に挿入する。
深さ優先探索のような決まった順序でトライ木から全キーを取り出す。これは一種の基数ソートである。

トライ木を使って N 個のキーのソートを N 個のプロセッサで行うと、その時間は Ω となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。

3.5. 全文検索
---------

特殊なトライ木としてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックスでインデックス付けを行うことができる。

4. 実装の工夫
--------

トライ木を表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。

基本的な方法は、ノードにを格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。

4.1. 二重連鎖木
----------

別の方法は、ノードにの3つ組みを格納する方法である。つまり二重連鎖木である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。

4.2. 三分探索木
----------

更に別の方法は、子供の集合を2分探索木で表現する方法である。この場合、トライ木は三分探索木になる。

4.3. ダブル配列
----------

1989年に青江順一がダブル配列を利用する方法を発表した。トライ木は決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト・ベース・次・チェックの4つの配列で表現できる。トライ木の場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。 check[base[s] + c] = s next[base[s] + c] = t 動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。 check[base[s] + c] = s base[s] + c = t すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。

ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタをたどって行かないといけないが、ダブル配列では一発で遷移できる。

実装としては Theppitak Karoonboonyanan が libdatrie を公開している。

5. 整数を格納するトライ木
--------------

5.1. 二分トライ木
-----------

二分トライ木やビット単位トライ木とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する。

高速化のためのテクニックとして、下記の２つの方法が使える。

葉ノードは子が無く、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O でたどれるようになる。
jumpポインタをノードに付け、一気に葉ノードまでジャンプする。

5.2. x-高速トライ木
-------------

x-高速トライ木は、検索キーとして与えられた整数以上の値をもつ、キーに最も近い葉ノードを得る操作を高速にできるようにした二分トライ木のバリエーションである。通常の二分トライ木との相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側のひとつしか持たない時に格納される、その中間ノード下で最大値をもつ葉ノードへのリンクを持つことである。。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がOとなる。1982年に Dan E. Willard が発表した。

5.3. y-高速トライ木
-------------

y-高速トライ木とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O 個ずつに分けて入れる。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O となり、x-高速トライ木より改善する。また、追加・削除の時間計算量が O になる。1982年に Dan E. Willard が x-fast trie と同時に発表した。

6. 関連項目
-------

基数木
三分探索木
決定性有限オートマトン
Judy配列
探索

7. 参考文献
-------

R. de la Briandais: //File Searching Using Variable Length Keys//. Proceedings of the Western Joint Computer Conference, 1959, pages 295–298.
E. Fredkin: //Trie Memory//. Communications of the ACM, 3:490-499, Sept. 1960.
Donald Knuth. //The Art of Computer Programming//, Volume 3: //Sorting and Searching//, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.3: Digital Searching, pp.492–512.

8. 外部リンク
--------

[1]
[2] by Lloyd Allison
[3]