トライ (データ構造) 応用

ウィキペディア

トライ (データ構造)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/06 14:51 UTC 版)

応用

他のデータ構造の代替

既に述べたようにトライ木は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) となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。

全文検索

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