How is Aho–Corasick different from just running KMP once per pattern?

Running KMP separately for k patterns over a text of length n costs O(k·n) in the worst case, since each pattern requires its own pass. Aho–Corasick merges all patterns into one automaton and scans the text exactly once, costing O(n + m + z) regardless of how many patterns there are, which is far faster when searching for hundreds or thousands of patterns simultaneously.

What exactly is a failure link, and why is it needed?

A failure link from node v points to the trie node representing the longest proper suffix of v's string that is still a prefix of some pattern. When the automaton can't extend the current match with the next character, it follows failure links instead of restarting from the root, so no input character is ever re-read — this is what keeps the scan linear in the text length.

Can Aho–Corasick find overlapping matches, like both "he" and "hers" ending near the same position?

Yes. Because each trie node stores a merged output set gathered by following failure links up to the root (the dictionary suffix chain), a single state can report multiple patterns that are suffixes of one another or that simply end at the same text position, so all overlapping and nested matches are reported correctly.

Where is Aho–Corasick used in practice?

Beyond its original use in the Unix fgrep utility, it powers antivirus engines matching files against large signature databases, network intrusion detection systems scanning packets for known attack strings, spam and content filters, and bioinformatics tools searching DNA sequences for many short motifs at once.

Home▸アルゴリズム & AI▸Aho–Corasick法 — マルチパターン文字列検索

🔤 Aho–Corasick法 — マルチパターン文字列検索

Build a trie of several patterns plus failure links, then scan text in a single O(n) pass, watching the automaton follow failure links and report every match at once.

アルゴリズム & AI2D上級60 FPS

Aho–Corasick法について

1975年にベル研究所のAlfred V. AhoとMargaret J. Corasickによって考案されたAho–Corasickアルゴリズムは、マルチパターン文字列照合問題を解決します:パターンの辞書とテキストが与えられたとき、単一の線形パスですべてのパターンのすべての出現箇所を見つけます。これは、Knuth–Morris–Pratt(KMP)アルゴリズムを単一パターンから複数パターンへと一般化したもので、すべてのパターンを共有トライ木にマージし、KMPが単一パターンのために失敗関数を計算するのとちょうど同じように、幅優先探索で失敗リンクを計算します。各ノードの失敗リンクは、その文字列の最長真接尾辞であり、かつ何らかのパターンの接頭辞でもあるものを指し、各ノードは失敗リンクをルートまでたどることで集められたマージ済みの「辞書接尾辞」出力集合を持ちます。長さnのテキストをスキャンするコストは、mを結合パターン長、zを報告される一致数とすると、O(n + m + z)にしかなりません。この効率性のため、Aho–Corasickは元祖のfgrep/grep -Fユーティリティ、何千ものマルウェアシグネチャに対してファイルを同時にチェックするウイルス対策シグネチャスキャナー、そして既知の攻撃文字列についてパケットのペイロードをリアルタイムで検査するネットワーク侵入検知システムの基盤となっています。

よくある質問

Aho–CorasickはKMPをパターンごとに1回実行するのと何が違うのですか?

長さnのテキストに対してk個のパターンでKMPを個別に実行すると、各パターンが独自のパスを必要とするため、最悪の場合O(k·n)のコストがかかります。Aho–Corasickはすべてのパターンを1つのオートマトンにマージし、テキストをちょうど1回スキャンするため、パターンの数に関わらずO(n + m + z)のコストで済み、何百、何千ものパターンを同時に検索する場合にはるかに高速です。

失敗リンクとは正確には何で、なぜ必要なのですか?

ノードvからの失敗リンクは、vの文字列の最長真接尾辞であり、かつ何らかのパターンの接頭辞でもあるものを表すトライ木のノードを指します。オートマトンが次の文字で現在の一致を拡張できないとき、ルートから再開する代わりに失敗リンクをたどるため、入力文字が再読み込みされることは決してありません — これがスキャンをテキスト長に対して線形に保つ仕組みです。

Aho–Corasickは「he」と「hers」がほぼ同じ位置で終わるような、重なり合う一致を見つけられますか?

はい。各トライ木のノードは、失敗リンクをルートまでたどることで集められたマージ済みの出力集合(辞書接尾辞の連鎖)を保持しているため、単一の状態が互いの接尾辞であるか、単に同じテキスト位置で終わる複数のパターンを報告できます。そのため、重なり合う一致やネストした一致もすべて正しく報告されます。

Aho–Corasickは実際にはどこで使われていますか?

UnixのfgrepユーティリティでのAho最初の用途に加えて、大規模なシグネチャデータベースに対してファイルを照合するウイルス対策エンジン、既知の攻撃文字列についてパケットをスキャンするネットワーク侵入検知システム、スパム・コンテンツフィルター、そして多くの短いモチーフを一度にDNA配列から検索するバイオインフォマティクスツールの基盤となっています。

⚙ 仕組み

Build a trie of several patterns plus failure links, then scan text in a single O(n) pass, watching the automaton follow failure links and report every match at once.

algorithmsstring matchingtrieautomatoncomputer science

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install