-
Aho-Corasick法
-
【読み】 エイホ–コラシックホウ
データ解析
【英語】 Aho-Corasick Algorithm
【読み】 エイホ–コラシックホウ
用語解説
エイホ・コラシック法。AC法とも。1975年にアルフレッド・エイホとマーガレット・コラシックによって発表された文字列探索アルゴリズム。入力文字列に対して、利用可能な辞書に登録されている文字列を末尾の一致箇所を記憶し、パターン・マッチング・オートマトン(PMA)を構成して処理することにより探索を行う。計算量は、文字列の長さに対して線形となる。