トライ木

出典: フリー百科事典『ウィキペディア（Wikipedia）』

"to", "tea", "ten", "i", "in", "inn" というキー群によるトライ木

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

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

右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。

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

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

[編集] 利点と欠点（2分探索木との比較）

以下に2分探索木と比較したトライ木の主な利点を挙げる:

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

また、トライ木の欠点は次の通り:

トライ木はキーの順序を与えるが、それは辞書式順序でなければならない。
トライ木は状況によっては極めて巨大になる。例えば、少数の非常に長い文字列を格納するトライ木などである（この場合はパトリシア木が適している）。
トライ木のアルゴリズムは単純な2分探索木よりも複雑である。
データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。

トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる（つまり偏りがある）。

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

[編集] 性能の定量化

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

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

[編集] 応用

[編集] 他のデータ構造の代替

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

理論上、平均検索性能は同じだが、実測するとトライ木の方が早い。
ハッシュテーブルの検索の最悪時間は O(N) である。
キーの衝突（コリジョン）が発生しない。
ハッシュ関数を用意する必要がない。
トライ木ではキーの辞書順を自動的に生成できる。

トライ木をハッシュテーブルとして使用した際の欠点は次の通り:

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

[編集] 辞書表現

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

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

[編集] 擬似コード

以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、children は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。

function find(node, key) {
  if (key is an empty string) {  # 基本ケース。キーが空文字列の場合
    return is node terminal?
  } else {  # 再帰ケース
    c = first character in key  # キーが空でないので、その1文字目を取り出す
    tail = key minus the first character  # 1文字目を除いた文字列
    child = node.children[c]  # 文字コードが配列キーとなる
    if (child is null) {  # 子がないので再帰できないがキーは空になっていない
      return false
    } else {
      return find(child, tail)
    }
  }
}

[編集] ソート

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

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

これは一種の基数ソートである。

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

[編集] 全文検索

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

[編集] 関連項目

基数木（パトリシア木）
DAWG
3分探索木
決定性有限オートマトン
Judy配列
探索

[編集] 外部リンク

[編集] 参考文献

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(9):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.

カテゴリ: データ構造

See also ebooksgratis.com: no banners, no cookies, totally FREE.