|
トライ木（）やプレフィックス木（）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。 トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。 キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。 トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。 trie という名称は "retrieval"（探索、検索）が語源であるため、"tree" と同じ発音を用いる（リトゥリーヴァル）。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。 == 利点と欠点（2分探索木との比較）== 以下に2分探索木と比較したトライ木の主な利点を挙げる: * キー検索が高速である。長さ ''m'' のキー検索は最悪で O(''m'') の時間がかかる。2分探索木では O(log ''n'') の時間であり、''n'' は木を構成するノード数である（木の深さに応じた時間がかかり、2分探索木の深さは ''n'' の対数となる）。トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。 * 多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーによってノードが共有されるためである。 * トライ木は最も長いプレフィックスとマッチするので、あるキーと最も長いプレフィックスが共通なキーを効率的に捜すこともできる。そのような共通プレフィックスに対応したノードに新たに値を格納することもできる。 * トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある（平衡2分探索木参照）。 また、トライ木の欠点は次の通り: * トライ木はキーの順序を与えるが、それは辞書式順序でなければならない。 * トライ木は状況によっては極めて巨大になる。例えば、少数の非常に長い文字列を格納するトライ木などである（この場合はパトリシア木が適している）。 * トライ木のアルゴリズムは単純な2分探索木よりも複雑である。 * データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。 トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる（つまり偏りがある）。 トライ木はキーの長さが可変でキー検索が失敗する場合があるとき（そのキー文字列がキーとされていない場合）、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である（図の例で言えば、"i" のノードと "in" のノードをまとめる）。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「トライ木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Trie 」があります。 スポンサード リンク
|