トライ — 文字列特化のデータ構造

このトピックを修了すると

トライの構造と動作原理を説明でき、挿入、検索、プレフィックス検索を実装して、オートコンプリートのような機能を作成できます。

問題 — 数万個の単語から検索する

辞書に10万個の単語があります。ユーザーが "pro" と入力すると、"program", "project", "process" などを表示したいとします。

リストを一つずつ比較する場合？10万個 × 文字列比較 = 遅い。ハッシュテーブルは正確なキーのみを検索できるため、プレフィックス検索には適していません。

トライ（Trie、"retrieval" に由来）は、この問題を解決するために作られたデータ構造です。

トライの構造

トライは文字1つに対してノード1つです。同じプレフィックスを共有する単語は、同じパスを辿ります。

text

root
├── a
│   ├── p
│   │   └── p ★ ("app")
│   │       └── l
│   │           └── e ★ ("apple")
│   └── c
│       └── e ★ ("ace")
└── b
    ├── a
    │   └── t ★ ("bat")
    └── e ★ ("be")

★マークは「ここで単語が終了する」という意味です。"app" と "apple" は同じパスを共有し、"app" で一度、"apple" で一度終了します。

実装 — ノード

python

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

各ノードは、子ノードの辞書 (children) と単語終了のフラグ (is_end) を持ちます。

挿入

python

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

python

trie = Trie()
for word in ["app", "apple", "ace", "bat", "be"]:
    trie.insert(word)

文字を一つずつ辿り、パスがない場合は新しいノードを作成します。最後の文字で is_end = True とマークします。

検索

python

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

python

print(trie.search("app"))    # True
print(trie.search("ap"))     # False — "ap" で終わる単語はない
print(trie.search("apple"))  # True
print(trie.search("bat"))    # True
print(trie.search("bad"))    # False

パスを辿る途中で存在しない場合は False。最後まで辿り着いたが is_end がない場合は False（プレフィックスであり、完全な単語ではない）。

プレフィックス検索 — オートコンプリートの核心

python

def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
    
    results = []
    self._collect(node, prefix, results)
    return results

def _collect(self, node, prefix, results):
    if node.is_end:
        results.append(prefix)
    for char, child in node.children.items():
        self._collect(child, prefix + char, results)

python

print(trie.starts_with("a"))    # ["app", "apple", "ace"]
print(trie.starts_with("ap"))   # ["app", "apple"]
print(trie.starts_with("b"))    # ["bat", "be"]
print(trie.starts_with("z"))    # []

プレフィックスまで辿り、その下にあるすべての完全な単語を収集します。検索エンジンのオートコンプリート、IDE のコード補完がこの原理です。

時間計算量

演算	時間計算量	比較（ハッシュテーブル）
挿入	O(m)	O(m)
正確な検索	O(m)	O(m)
プレフィックス検索	O(m + k)	❌ 不可能

m = 文字列の長さ、k = プレフィックスの下にある結果の数。

正確な検索のパフォーマンスはハッシュテーブルと似ていますが、プレフィックスベースの検索はトライでのみ可能です。ハッシュテーブルは "pro" で始まるすべてのキーを検索するには、全件調査を行う必要があります。

メモリのトレードオフ

トライの欠点はメモリの使用量です。各ノードは辞書を持ち、英小文字のみでも最大 26 個の子ポインタが必要です。

これを改善した変形：

Compressed Trie（Radix Tree）：子が1つしかないノードを結合してパスを圧縮
Ternary Search Tree：二分探索木と混合してメモリを節約

実務では、ほとんどのライブラリが最適化を処理するため、原理を理解していれば十分です。

実務での活用

用途	説明
検索オートコンプリート	Google, IDE のコード補完
スペルチェック	入力された単語が辞書にあるか確認
IPルーティング	ネットワークプレフィックスのマッチング（最長プレフィックスマッチ）
T9キーパッド	数字→文字変換後の候補単語検索

削除の実装

python

def delete(self, word):
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False
            node.is_end = False
            return len(node.children) == 0
        
        char = word[depth]
        if char not in node.children:
            return False
        
        should_remove = _delete(node.children[char], word, depth + 1)
        if should_remove:
            del node.children[char]
            return not node.is_end and len(node.children) == 0
        return False
    
    _delete(self.root, word, 0)

単語を削除する際、その単語だけが持つノード（他の単語と共有しない）のみを削除します。"apple" を削除しても、"app" に必要なノードはそのまま残ります。

カウンティングトライ

挿入回数を記録すると、単語頻度辞書になります。

python

class CountTrie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.count = getattr(node, 'count', 0) + 1
    
    def count(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return 0
            node = node.children[char]
        return getattr(node, 'count', 0) if node.is_end else 0

検索クエリの頻度集計、オートコンプリートのランキング決定などに活用されます。

Python でのシンプルなトライの代替手段

トライを直接実装しなくても、dict のネスト構造で同様の効果を得ることができます。

python

from collections import defaultdict

def make_trie(words):
    trie = lambda: defaultdict(trie)
    root = trie()
    for word in words:
        node = root
        for c in word:
            node = node[c]
        node['$'] = True
    return root

t = make_trie(["app", "apple", "bat"])
print("app" in str(t))  # True

ただし、starts_with などのプレフィックス機能が必要な場合は、クラスベースの実装の方がきれいです。コーディングテストでは、クラスの実装が標準です。

トライは「プレフィックスを共有する文字列の集合」を扱うすべての場所に適しています。

BioPlayground

トライ — 文字列に特化したデータ構造

トライ — 文字列特化のデータ構造

このトピックを修了すると

問題 — 数万個の単語から検索する

トライの構造

実装 — ノード

挿入

検索

プレフィックス検索 — オートコンプリートの核心

時間計算量

メモリのトレードオフ

実務での活用

削除の実装

カウンティングトライ

Python でのシンプルなトライの代替手段

💬 質問・コメント