アルゴリズム - 6. Trie(接頭辞木)
Trieを使用するタイミング
文字列のコレクションに対して高速な接頭辞ベースの操作が必要な場合にTrieを使用します。"Trie"という名前は"retrieval"(検索)という単語から来ており(「try」のように発音)、1960年にEdward Fredkinによって考案されました。「retrieval」から派生していますが、特に高速な文字列検索と接頭辞マッチング操作のために設計されています。
別名: Trieは一般的に**「接頭辞木(Prefix Tree)」または「デジタル木(Digital Tree)」**とも呼ばれます。「接頭辞木」という名前は特に分かりやすく、木の各ノードがその子孫の共通接頭辞を表すためです。文献によっては「基数木(Radix Tree)」とも呼ばれますが(厳密にはRadix TreeはTrieの空間最適化された変種です)。
単語検証に最もよく使用されますが、以下の用途にも優れています:
- オートコンプリート/候補表示(典型的な使用例 - 共通の接頭辞を持つすべての単語を見つける)
- スペルチェッカー(辞書に単語が存在するかチェック)
- IPルーティングテーブル(最長接頭辞マッチング)
- 電話帳(接頭辞による連絡先検索)
- ワードゲーム(Scrabbleでの単語検証、Boggleでの単語探索)
- 多数の文字列に対する効率的な接頭辞マッチングまたは存在チェックが必要な問題
例題
オートコンプリートシステム: 単語辞書 ["apple", "app", "apricot", "application", "apply", "banana", "band", "bandana"] が与えられたとき、以下の機能を持つ検索システムを実装してください:
- "apple"が有効な単語かどうかを素早くチェックできる
- オートコンプリートのために"app"で始まるすべての単語を見つけることができる
- 辞書に新しい単語を効率的に追加できる
回答: Trieは3つの操作すべてをO(m)時間で処理します。ここでmは単語/接頭辞の長さであり、辞書のサイズに依存しません!
Trieが辞書を保存する方法
以下は、例題の単語がTrieの構造を形成する様子です:
root
/ \
a b
/ |
p a
/|\ |\
p r i n d
| | | | |
l i c a a
| | | | |
[e*] c a [n*] n
| | |
o t [a*]
| |
[t*] i
|
o
|
[n*]
[*] = 単語の終端マーカー
単語: app*, apple*, apricot*, application*, apply*, banana*, band*, bandana*"app"、"apple"、"application"、"apply"がすべて接頭辞"app"を共有しており、それが一度だけ保存されていることに注目してください!
最も重要な洞察
Trieは空間をスピードと引き換えに、共通の接頭辞を共有します - ルートからノードへの各パスが接頭辞を表し、保存されている文字列の数に関係なくO(m)の操作を可能にします。これは、検索している文字のみを走査するためです。
覚えておくべきポイント: Trieの天才的な点は、文字列操作を木の走査に変換することです。文字列全体を繰り返し比較する代わりに、1文字ずつ単一のパスをたどります。各ノードでの決定は単純に「この文字が子として存在するか?」です。この単純な走査により、すべての共通接頭辞を自動的に活用できます。
なぜ"Tree"ではなく"Trie"なのか: 木構造ですが、"Trie"という名前は、接頭辞の共有による効率的な文字列の再trieval(検索)という特殊な目的を強調することで、一般的な木と区別しています。階層的なデータのためだけの木ではなく、文字列操作に特化して最適化された木なのです。
判断フレームワーク
普遍的なTrie判断
すべてのTrie操作は1つの質問に帰結します:
「現在のノードはこの文字の子を持っているか?」
- はい → そのパスをたどる
- いいえ → 作成する(挿入)または結果を返す(検索/接頭辞)
この単一の決定を各文字に対して繰り返すことで、すべてのTrie操作が機能します。
操作の各文字で、この決定に直面します:
- 挿入時: 新しいノードを作成するか、既存のパスをたどるか?
- 検索時: 既存のパスを下っていくか、falseを返すか?
- 接頭辞マッチ時: パスが存在する限り、パスをたどり続ける
コード
設計の選択の説明
function createTrieNode() {
return {
isEndOfWord: false, // Why: 完全な単語と接頭辞を区別する
children: new Map(), // Why: Mapは疎な文字セットを効率的に処理
}; // (使用されない文字のためにメモリを無駄にするarray[26]と比較)
}Trieのコア実装
function Trie() {
const root = createTrieNode();
function insert(word) {
let currentNode = root;
for (const char of word) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Create new path or follow existing?
if (!hasChildWithChar) {
const newNode = createTrieNode();
currentNode.children.set(char, newNode);
}
currentNode = currentNode.children.get(char);
}
// Mark the end of a complete word
currentNode.isEndOfWord = true;
}
function search(word) {
let currentNode = root;
for (const char of word) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Path exists or return false?
if (!hasChildWithChar) {
return false; // Character not found, word doesn't exist
}
currentNode = currentNode.children.get(char);
}
// Found all characters, but is it a complete word?
const isCompleteWord = currentNode.isEndOfWord;
return isCompleteWord;
}
function startsWith(prefix) {
let currentNode = root;
for (const char of prefix) {
const hasChildWithChar = currentNode.children.has(char);
// DECISION FRAMEWORK: Continue traversal or prefix not found?
if (!hasChildWithChar) {
return false;
}
currentNode = currentNode.children.get(char);
}
// If we've traversed the entire prefix, it exists
return true;
}
// Return the public interface
return {
insert,
search,
startsWith,
};
}
// Example usage with our dictionary
const dictionary = Trie();
const words = ["apple", "app", "apricot", "application", "apply"];
for (const word of words) {
dictionary.insert(word);
}
console.log(dictionary.search("apple")); // true
console.log(dictionary.search("app")); // true
console.log(dictionary.search("appl")); // false (not a complete word)
console.log(dictionary.startsWith("app")); // trueステップバイステップ: "app"の挿入
空のTrieに単語"app"を挿入する様子を追跡してみましょう:
開始状態: root (空)
1. 'a'を処理:
- rootは子'a'を持っているか? いいえ
- 'a'の新しいノードを作成
- ノード'a'に移動
状態: root → a
2. 'p'を処理:
- 'a'は子'p'を持っているか? いいえ
- 'p'の新しいノードを作成
- 最初の'p'に移動
状態: root → a → p
3. 'p'を処理:
- 最初の'p'は子'p'を持っているか? いいえ
- 2番目の'p'の新しいノードを作成
- 2番目の'p'に移動
状態: root → a → p → p
4. 単語の終端をマーク:
- 2番目の'p'にisEndOfWord = trueを設定
最終: root → a → p → p[*]高度な操作
接頭辞を持つすべての単語を見つける(オートコンプリート)
// Add this to the Trie function's returned object
function findAllWordsWithPrefix(prefix) {
let currentNode = root;
// First, navigate to the prefix end
for (const char of prefix) {
const hasChildWithChar = currentNode.children.has(char);
if (!hasChildWithChar) {
return []; // Prefix doesn't exist
}
currentNode = currentNode.children.get(char);
}
// Collect all words starting from this node
const results = [];
collectWords(currentNode, prefix, results);
return results;
}
function collectWords(node, currentWord, results) {
const isWord = node.isEndOfWord;
if (isWord) {
results.push(currentWord);
}
// Recursively collect from all children
for (const [char, childNode] of node.children) {
const nextWord = currentWord + char;
collectWords(childNode, nextWord, results);
}
}
// Usage example:
console.log(dictionary.findAllWordsWithPrefix("app"));
// Returns: ["app", "apple", "application", "apply"]よくある実装の落とし穴
-
単語終端マーカーを忘れる:
isEndOfWordがなければ、"app"(完全な単語)と"appl"("apple"に存在する接頭辞)を区別できません -
MapではなくArrayを使用する:
- Array方式:
children = new Array(26)は数文字しか使わない場合、メモリを無駄にします - Map方式:
children = new Map()は実際に存在する文字のみを保存します
- Array方式:
-
空文字列を処理しない: 空文字列がTrieで有効な単語かどうかを事前に決定します。ほとんどの実装では無効として扱います
-
接頭辞の存在と単語の存在を混同する: 私たちのTrieでは"appl"は接頭辞として存在します("apple"へのパス)が、それ自体は単語ではありません
疑問解消
よくある疑問: 「Trieは過度にメモリを使用しないでしょうか? 'a'、'ab'、'abc'、...、'abcdefghijklmnopqrstuvwxyz'のような単語があると、1つの単語のためだけに26のノードを作成することになりますよね!」
視覚的比較: Trie vs 生の文字列ストレージ
"algorithm"、"algorithms"、"algorithmic"、"algorithmically"の保存を分析してみましょう:
Trieなし(生の文字列保存):
- "algorithm" → 9文字
- "algorithms" → 10文字
- "algorithmic" → 11文字
- "algorithmically" → 16文字
合計: 46文字のストレージユニット
Trieあり(接頭辞の共有):
a-l-g-o-r-i-t-h-m (9ノード)
├─ [end] (単語: "algorithm")
├─ s-[end] (1ノード、"algorithms"用)
└─ i-c (2ノード)
├─ [end] (単語: "algorithmic")
└─ a-l-l-y-[end] (4ノード、"algorithmically"用)
合計: 16ノード (9 + 1 + 2 + 4)接頭辞共有の重要な洞察
魔法: 46文字ではなく、"algorithm"が4つの単語すべてで共有されるため、わずか16ノードで済みます!
実世界での効率性 - 英語の単語辞書を考えてみましょう:
- 単語は大きな接頭辞を共有します("run"、"running"、"runner"、"runs")
- 共通のパターンが現れます("pre-"、"un-"、"re-"、"-ing"、"-ed")
- 単語を追加すればするほど、接頭辞の共有が増えます
"pre-"で始まる1000語の例:
- 素朴な保存: 約7000文字("pre"の後平均7文字)
- Trie保存: "pre"に3ノード + 分岐パス(7000よりはるかに少ない)
Trieが実際に空間を無駄にする場合
Trieが非効率的な場合:
- 共通の接頭辞がない: ["xyz", "abc", "qrs"]の保存は完全に別個のパスを作成
- 非常に短い文字列: ノード構造のオーバーヘッドが文字列の長さを超える
- ランダムなデータ: UUIDやハッシュには意味のある接頭辞パターンがない
空間と時間のトレードオフ
Trieの素晴らしさ: 例外的な時間保証のために空間を犠牲にします:
| 操作 | HashMap | Trie |
| --------------- | ---------------------------- | ----------------------------------------- |
| 挿入 | 平均O(m)、最悪O(n×m) | 常にO(m) |
| 検索 | 平均O(m)、最悪O(n×m) | 常にO(m) |
| 接頭辞マッチ | O(n×m) - すべての文字列確認 | O(m) - パスをたどるだけ |
| オートコンプリ | O(n×m) - すべてをスキャン | O(m+k) - 接頭辞にm、結果にk |
n = 文字列の数、m = 文字列の長さ、k = 結果の数保証: Trieはランダムな文字列に対してはより多くのメモリを使用する可能性がありますが、接頭辞操作に対して最高の時間計算量を提供します。自然な接頭辞パターン(単語、URL、ファイルパス)を持つ領域では、時間と空間の両方で効率的です!