|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
エイホ–コラシック法（）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである。 == 概要 == エイホ–コラシック法は、入力テキストについて有限の文字列群（辞書）の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい（つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など）。大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字列（例えば abc）を表すノードからその最長サフィックス（接尾部、例えばbc）を表すノードがあればそれへリンクし、さもなくば c を表すノードがあればそれへリンクし、それもなければルートノードにリンクする。このような最長サフィックスへのリンクを全てのノードが持っているため、そのリンクリストを辿ることで全てのマッチングを列挙できる。実行時にはトライ木として働き、最長のマッチングを探すと共に、サフィックスのリンクリストを活用することで計算量を線形に抑えている。辞書にあるノードに到達すると、その単語とそこからリンクされている辞書に含まれるノードが、マッチングした位置と共に出力される。（例えばコンピュータウイルスのデータベースのように）パターン辞書が更新されると、オフラインでオートマトンの構築がなされ、それを今後使用するよう格納する。この場合、実行時の計算量は入力の長さとマッチすべきエントリ数に対して線形である。 UNIXのコマンド fgrep は本来エイホ-コラシック法に基づいていた。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「エイホ–コラシック法」の詳細全文を読む スポンサード リンク
|