文字列処理 の記事

トライ木（Trie）入門 - 接頭辞検索とオートコンプリートを支えるデータ構造

文字列の集合を扱うデータ構造トライ木（Trie / prefix tree）を解説します。ノードと子への枝、終端フラグという構造、挿入・検索・接頭辞検索の素朴な実装、文字列長Lに比例するO(L)という計算量とハッシュテーブルとの違い、オートコンプリート・T9予測変換・IPルーティングの最長prefix一致・スペルチェッカー・辞書式順序での列挙といった応用、圧縮トライ（radix tree / PATRICIA trie）とAho-Corasickアルゴリズムとの関係、各言語の標準ライブラリ事情まで、実際に動くPythonコードで整理します。