エイホ–コラシック法

エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである^[1]。

概要

エイホ–コラシック法は、入力テキストについて有限の文字列群（辞書）の各要素を探す辞書式マッチングアルゴリズムの一種である。全パターンのマッチングを一斉に探索するため、そのアルゴリズムの計算量はパターン群の長さに対しても対象テキストの長さに対しても線形であり、さらに見つかったマッチングの数に対しても線形である。全てのマッチングを検出するため、パターン群にサブ文字列があれば、重複して検出される点に注意されたい（つまり、辞書が a, aa, aaa, aaaa で、入力テキストが aaaa の場合など）。

大まかに言えば、このアルゴリズムはトライ木を構築し、サフィックス木的に文字列（例えばabc）を表すノードからその最長サフィックス（接尾部、例えばbc）を表すノードがあればそれへリンクし、さもなくば c を表すノードがあればそれへリンクし、それもなければルートノードにリンクする。このような最長サフィックスへのリンクを全てのノードが持っているため、そのリンクリストを辿ることで全てのマッチングを列挙できる。実行時にはトライ木として働き、最長のマッチングを探すと共に、サフィックスのリンクリストを活用することで計算量を線形に抑えている。辞書にあるノードに到達すると、その単語とそこからリンクされている辞書に含まれるノードが、マッチングした位置と共に出力される。

（例えばコンピュータウイルスのデータベースのように）パターン辞書が更新されると、オフラインでオートマトンの構築がなされ、それを今後使用するよう格納する。この場合、実行時の計算量は入力の長さとマッチすべきエントリ数に対して線形である。

UNIXのコマンド fgrep は本来エイホ-コラシック法に基づいていた。

例

以下にエイホ–コラシック法で指定された辞書から構築されたデータ構造を示す。各行に書かれているのは、トライ木でのノードで、列の並びで上から下にノードの経路ができている。'-' が付いているノードは辞書にはない中間的なノードで、'+' が付いているノードは辞書にある。

辞書 { a, ab, bc, bca, c, caa }
経路	辞書にあるか	サフィックスのリンク	辞書サフィックスのリンク
()	-
(a)	+	()
(ab)	+	(b)
(b)	-	()
(bc)	+	(c)	(c)
(bca)	+	(ca)	(a)
(c)	+	()
(ca)	-	(a)	(a)
(caa)	+	(a)	(a)

各段階で、現在のノードを調べて、次の文字に対応する子ノードを探す。もしなければ、サフィックスの子ノードを探す。さらになければ、サフィックスのサフィックスの子ノードを…といった形で、最終的にルートノードにたどり着くまで探していく。

入力文字列 abccab を上記の辞書を使って検索すると次のようになる:

入力文字列 `abccab` の解析
ノード	残り文字列	出力:現在位置	遷移	出力
()	abccab		ルートから開始
(a)	bccab	a:1	() から子 (a) へ	現在ノード
(ab)	ccab	ab:2	(a) から子 (ab) へ	現在ノード
(bc)	cab	bc:3, c:3	(ab) からサフィックス (b) の子 (bc) へ	現在ノード、辞書サフィックスノード
(c)	ab	c:4	(bc) からサフィックス (c) のサフィックス () の子 (c) へ	現在ノード
(ca)	b	a:5	(c) から子 (ca) へ	辞書サフィックスノード
(ab)		ab:6	(ca) からサフィックス (a) の子 (ab) へ	現在ノード

一般に、辿るべき辞書サフィックスリンクは複数ある。つまり、辞書にある単語で入力された文字が最後にある単語はひとつではない。

参照

^ Aho, Alfred V.; Corasick, Margaret J. (June 1975). “Efficient string matching: An aid to bibliographic search”. Communications of the ACM 18 (6): 333–340. doi:10.1145/360825.360855.

外部リンク

Aho-Corasick string matching in C# by Tomáš Petříček (mirror)
Aho-Corasick entry in NIST's Dictionary of Algorithms and Data Structures
PHP/Javascript Implementation of Aho/Corasick Algorithm
Java Implementation of the Aho-Corasick Algorithm (JDK Version >= 1.2 Needed) - ウェイバックマシン（2008年10月4日アーカイブ分） by Peter Petrov

[1] Aho, Alfred V.; Corasick, Margaret J. (June 1975). “Efficient string matching: An aid to bibliographic search”. Communications of the ACM 18 (6): 333–340. doi:10.1145/360825.360855.

[1]