アルゴリズム・データ構造図鑑 · 入門

トライ:共通の接頭辞を共有する探索木

文字列の長さに沿って探索し、完全一致と接頭辞検索を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 文字をたどってキーを表す
  2. 接頭辞があることと単語があること
  3. 文字集合とメモリを設計する
  4. 圧縮と利用場面
  5. この記事をロゲイアに質問する理解を確かめる

文字をたどってキーを表す

トライは、文字列の接頭辞を共有して保存する木構造です。辺を一文字に対応させる単純な形では、根からc、a、tと進む経路がcatを表します。catとcarはcaまでの経路を共有します。検索では、比較対象の文字列を何度も先頭から比較する代わりに、キーの次の文字に対応する辺を選びます。辺の選択を一定時間で行えるという仮定の下で、長さLのキーの検索はO(L)です。

接頭辞があることと単語があること

catとcarを登録したトライには、cとaをたどる経路があります。しかしcaという単語を登録したとは限りません。完全一致検索には、そのノードでキーが終了することを示す印や値が必要です。caから始まる語を列挙する場合は、そのノードの先を探索してcatやcarを集めます。接頭辞ノードへ到達するコストと、結果をすべて出力するコストは別で、結果が多ければ列挙時間も増えます。

文字集合とメモリを設計する

各ノードに全アルファベット分の子参照を持つ配列表現なら、辺の選択は簡単ですが、使わない参照の領域が増えます。存在する辺だけを辞書や木で保持する表現では、空間と辺探索コストの関係が変わります。Unicodeを扱う場合は、バイト、コードポイント、表示上の文字のどれを一段とするかも重要です。大文字小文字や正規化の扱いを決めないと、見た目が似たキーが別の経路になる場合があります。

圧縮と利用場面

子が一つだけ続く経路をまとめる圧縮トライでは、ノードや参照の数を抑えられます。その分、辺の途中まで一致した場合やキーを途中へ挿入する処理を考える必要があります。トライは補完候補、接頭辞による辞書検索、ビット列を使う経路探索などに向いています。ただし短いキーの完全一致だけならハッシュ表が簡単なこともあります。検索件数だけでなく、接頭辞の共有度、文字集合、出力件数を比較します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ