Trie(トライ)とは?効率的な文字列検索をするデータ構造

スポンサーリンク
Trie(トライ)とは?効率的な文字列検索をするデータ構造 データ構造

Trie(トライ)とは

Trieとは、

木構造を使い、効率的な文字列検索をするためのデータ構造

です。

 

Trieでは各ノードが1文字を保持する形の木になっています。

単語の最後の1文字のノードには印をつけておくことで、その単語が存在しているかを管理しています。

下の例では、「dog」は存在しているが、「do」は存在していません。

Trieの例

 

基本的な操作

挿入

単語をTrieに挿入する際には、文字ごとにノードを追加していきます。

例えば「card」を挿入する際には、「c」「a」「r」「d」がの並びが存在するか順番に確認していき、足りないノードを追加します。

そのため共通の接頭辞を共有することができます。

Trieの挿入

 

検索

単語がTrieに存在するかを調べるには、文字ごとにノードを辿っていきます。

もし最後まで辿る事ができて、最後のノードに末尾のフラグがあれば、その単語が存在すると判断できます。

 

実装(Python)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end_of_word

Trieを試しに使ってみます。

trie = Trie()
trie.insert("dog")
print(trie.search("dog"))  # True
print(trie.search("do"))  # False
True
False

 

Trieの応用例

Trieは以下のような場面でよく使われるアルゴリズムです。

  • オートコンプリート機能
    • 入力途中の単語の候補を効率的に検索
  • 辞書検索
    • 単語リストから高速に検索を行う
  • スペルチェック
    • 存在しない単語を検出
  • IPルーティング
    • ネットワークプレフィックスの管理

 

HashMapとTrieの比較

TrieとHashMap(ハッシュテーブル)はどちらも文字列検索に使われますが、それぞれにメリット・デメリットがあります。

HashMapで十分なケース

完全一致だけを検索したい場合は、 平均O(1)で動作するHashMapの方が効率的な場合が多いです。

hash_map = {"apple": 1, "banana": 2, "cherry": 3}
print("apple" in hash_map)  # True

TrieのO(N)よりも高速な場合が多いです。

 

HashMapでは不十分なケース

例えば「ap」で始まる単語を全て検索したい場合、HashMapでは全探索する必要があります。

一方でTrieなら「ap」までたどれば、底から全ての単語を効率的に取得できます。

 

参考文献

トライ – Wikipedia

コメント

タイトルとURLをコピーしました