Trie(トライ木) — 同じ書き出しは道を共有する

スマホで「ca」と打つと「cat」「car」「card」がサッと候補に出ます。膨大な単語の中から、毎回すべてを調べていたら間に合いません。これを高速にこなすのが Trie(トライ木)。単語を1文字ずつ枝に分けて並べた木で、同じ書き出しの単語は途中まで道を共有します。

嬉しいのは2つ。同じ接頭辞を持つ単語が枝を共有するのでムダがないこと。そして検索が「単語の長さぶん、根から下るだけ」で済むこと(登録数がいくら増えても変わりません)。下の図1で、単語を挿入して木を育て、文字列を検索してみてください。

「道を共有する」のが効く理由

図1で cat → car → card の順に挿入してみてください。cat で3つのノードができますが、car を足すと c→a はすでにある道を再利用して、新しく増えるのは r の1つだけ。card も d が1つ増えるだけです。単語が増えても、共通の書き出しぶんは1度しか持たない —— これがメモリの節約と、接頭辞検索(オートコンプリート)の速さにつながります。

検索も明快です。cat を探すなら根から c→a→t と3歩下るだけ。途中で進む先の枝が無ければ、その時点で「登録されていない」と確定します(図1の cab)。たどり着いた先が単語の終端マーク(●)を持てば単語として登録済み、マークが無ければ ca のように「途中の通過点」=接頭辞でしかない、と区別できます。探す手間は登録単語数ではなく探す文字列の長さだけで決まります。

まとめ

Trie は「単語を1文字ずつ枝に展開し、共通の書き出しは道を共有する」木です。だから登録が増えてもムダが少なく、検索は文字列の長さぶん根から下るだけ。途中で枝が切れれば即「無い」と分かり、終端マークの有無で「単語」か「ただの接頭辞」かを区別できます。オートコンプリートや辞書、IPルーティングの最長一致など、「書き出しでまとめて絞り込みたい」場面の土台になっています。