trie の単純検索 (prefix マッチ)｜コードで実践

trie の単純検索 (prefix マッチ)

このレッスンで分かること

trie の真価は 同じ trie で大量の検索を捌く こと

trie (トライ木) は 文字列の集合を効率よく検索する ためのツリー型データ構造です

単語 cat、car、dog を持つ trie は次の形になります

trie の単純検索とは

単語の集合に対して trie を構築し、与えられたプレフィックスで始まる単語が存在するかを判定する関数を実装する。trie の基本構造とプレフィックスマッチを学ぶ。

trie (トライ木) は 文字列の集合を効率よく検索する ためのツリー型データ構造です。各ノードが 1 文字を表し、ルートからたどることで単語を構成します。prefix 検索 辞書検索 オートコンプリート IP ルーティング などで広く使われます。名前は retrieval（検索）の途中から取られており、発音が "tree" と同じためツリー構造と混同されやすいですが re + tree の合成語ではありません。

本レッスンでは、単語リスト words と検索プレフィックス prefix を受け取り、「prefix で始まる単語が words の中に 1 つでも存在するか」 を true / false で返す関数を作ります。素朴に書くと O(W * L) ですが、trie を使えば prefix の長さ L だけで判定できます。

trie は 文字の枝分かれ をそのままツリーに落とす。共通プレフィックスを共有するのでメモリ効率も良い。

trie の構造

単語 cat、car、dog を持つ trie は次の形になります。

diagram (will load when visible)

図のポイント (テキスト併記)

ルートから c -> a -> t とたどると cat に到達します

ルートから c -> a -> t とたどると cat に到達します。同じく c -> a -> r で car、d -> o -> g で dog。c -> a までは cat と car で共有されており、これが trie の 省メモリ性 の源です。

プレフィックス検索は ルートからプレフィックスの各文字をたどれるかどうか を見るだけ。ca ならルート → c → a までたどれれば成功です。途中で枝がなければ失敗。

実装の方針

本レッスンでは単純化のため、map (辞書) のネストで trie を表します。

Python

trie = {
  'c': {'a': {'t': {}, 'r': {}}},
  'd': {'o': {'g': {}}},
}

各ノードは「次の文字 → 子ノード」の辞書。終端マークは省略しても、プレフィックス検索だけならOK。

Python での実装

Python

def hasPrefix(words, prefix):
    trie = {}
    for word in words:
        node = trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
    node = trie
    for ch in prefix:
        if ch not in node:
            return False
        node = node[ch]
    return True

前半で trie を構築し、後半でプレフィックスをたどります。たどれなくなった時点で False、最後までたどれたら True。

JavaScript での実装

JavaScript

function hasPrefix(words, prefix) {
  const trie = {};
  for (const word of words) {
    let node = trie;
    for (const ch of word) {
      if (!(ch in node)) node[ch] = {};
      node = node[ch];
    }
  }
  let node = trie;
  for (const ch of prefix) {
    if (!(ch in node)) return false;
    node = node[ch];
  }
  return true;
}

計算量は構築が O(全単語の合計文字数)、検索が O(プレフィックスの長さ)。素朴な検索 words.some(w => w.startsWith(prefix)) は O(W * L) ですが、構築済み trie なら検索は 文字数だけ で済みます。

trie が活きる場面

検索フォームの オートコンプリート
辞書アプリの インクリメンタルサーチ
IP アドレスの 最長一致 ルーティング
文字列の 共通プレフィックス 抽出

trie の真価は 同じ trie で大量の検索を捌く こと。1 回の検索だけなら線形スキャンで十分。

空文字列のプレフィックス

プレフィックスが空文字列 "" の場合、どんな単語でもマッチします (空文字列はすべての文字列のプレフィックス)。本レッスンの実装でも、空のループは即 True を返すので問題なく処理できます。

よくある間違い

1 つ目は 終端マーク (例: $) を忘れる こと。「完全一致」も判定したいなら終端マークが必要です。今回はプレフィックス検索だけなので不要。2 つ目は in の対象を間違える。Python の ch in node は辞書のキーを見ますが、JS で ch in node と書くときも同じくキーを見ます。配列の includes と混同しないよう注意。3 つ目は node = trie のリセット忘れ。構築フェーズと検索フェーズで別の node 変数を使うか、検索の前に node = trie に戻すことを忘れない。

やってみよう

単語の 完全一致 を判定する hasWord を書いてみる。終端マークを使う or trie のキー集合に空ノードを置く。
検索を 重複して大量に行う ケースで、線形スキャン vs trie の速度差を実感する。
trie ノードに count を持たせ、プレフィックスから始まる単語数を返す countPrefix を実装する。

trie は 文字列を木で扱う 発想の入り口。再帰 辞書 クロージャ の総合演習にもなる。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は Union-Find (連結成分数) で、Union-Find (連結成分数) を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

trie の prefix 検索の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. trie の prefix 検索とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

trie の単純検索 (prefix マッチ)