文字をたどってキーを表す
トライは、文字列の接頭辞を共有して保存する木構造です。辺を一文字に対応させる単純な形では、根からc、a、tと進む経路がcatを表します。catとcarはcaまでの経路を共有します。検索では、比較対象の文字列を何度も先頭から比較する代わりに、キーの次の文字に対応する辺を選びます。辺の選択を一定時間で行えるという仮定の下で、長さLのキーの検索はO(L)です。
接頭辞があることと単語があること
catとcarを登録したトライには、cとaをたどる経路があります。しかしcaという単語を登録したとは限りません。完全一致検索には、そのノードでキーが終了することを示す印や値が必要です。caから始まる語を列挙する場合は、そのノードの先を探索してcatやcarを集めます。接頭辞ノードへ到達するコストと、結果をすべて出力するコストは別で、結果が多ければ列挙時間も増えます。
文字集合とメモリを設計する
各ノードに全アルファベット分の子参照を持つ配列表現なら、辺の選択は簡単ですが、使わない参照の領域が増えます。存在する辺だけを辞書や木で保持する表現では、空間と辺探索コストの関係が変わります。Unicodeを扱う場合は、バイト、コードポイント、表示上の文字のどれを一段とするかも重要です。大文字小文字や正規化の扱いを決めないと、見た目が似たキーが別の経路になる場合があります。
圧縮と利用場面
子が一つだけ続く経路をまとめる圧縮トライでは、ノードや参照の数を抑えられます。その分、辺の途中まで一致した場合やキーを途中へ挿入する処理を考える必要があります。トライは補完候補、接頭辞による辞書検索、ビット列を使う経路探索などに向いています。ただし短いキーの完全一致だけならハッシュ表が簡単なこともあります。検索件数だけでなく、接頭辞の共有度、文字集合、出力件数を比較します。