|
エイホ–コラシック法エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである[1]。 概要エイホ–コラシック法は、入力テキストについて有限の文字列群（辞書）の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい（つまり、辞書が 大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字列（例えば （例えばコンピュータウイルスのデータベースのように）パターン辞書が更新されると、オフラインでオートマトンの構築がなされ、それを今後使用するよう格納する。この場合、実行時の計算量は入力の長さとマッチすべきエントリ数に対して線形である。 UNIXのコマンド fgrep は本来エイホ-コラシック法に基づいていた。 例 以下にエイホ–コラシック法で指定された辞書から構築されたデータ構造を示す。各行に書かれているのは、トライ木でのノードで、列の並びで上から下にノードの経路ができている。'-' が付いているノードは辞書にはない中間的なノードで、'+' が付いているノードは辞書にある。
各段階で、現在のノードを調べて、次の文字に対応する子ノードを探す。もしなければ、サフィックスの子ノードを探す。さらになければ、サフィックスのサフィックスの子ノードを…といった形で、最終的にルートノードにたどり着くまで探していく。 入力文字列 abccab を上記の辞書を使って検索すると次のようになる:
一般に、辿るべき辞書サフィックスリンクは複数ある。つまり、辞書にある単語で入力された文字が最後にある単語はひとつではない。 参照
外部リンク
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||