エイホ–コラシック法

エイホ–コラシック法は、アルフレッド・エイホとマーガレット・J・コラシックによって1975年に開発された、効率的な文字列探索アルゴリズムです。このアルゴリズムは、与えられたテキストの中から、あらかじめ定義された複数のキーワード（辞書）を同時に検索するのに特化しています。

アルゴリズムの概要

エイホ–コラシック法の最大の特徴は、テキストの長さとキーワードの数に対して計算量が線形であることです。これにより、大量のテキストデータや多くのキーワードを扱う場合でも、高速に検索処理を行うことができます。アルゴリズムは、まず与えられたキーワード群からトライ木と呼ばれるデータ構造を構築します。トライ木は、文字列の接頭辞をノードとして表現した木構造で、各ノードから次の文字に対応する子ノードへと遷移することで、文字列を表現します。

次に、このトライ木に対して、各ノードから最長のサフィックス（接尾辞）に対応するノードへのリンク（サフィックスリンク）を作成します。サフィックスリンクは、検索中に現在のノードでマッチする文字列が見つからなかった場合に、別のマッチングの可能性を探るために使用されます。このサフィックスリンクの存在が、エイホ–コラシック法を効率的にする鍵となります。

検索時には、テキストの先頭から一文字ずつ読み進め、トライ木を辿ります。もしテキストの文字に対応する子ノードがない場合は、サフィックスリンクを辿り、次の可能性を探ります。この処理を繰り返すことで、テキスト中に現れる全てのキーワードを検出できます。もし、トライ木中のあるノードがキーワードの終端を表している場合、そのキーワードが検出されたことになります。

例と動作

例えば、辞書として {a, ab, bc, bca, cab} が与えられたとします。この辞書を元に構築されたトライ木とサフィックスリンクの例を以下に示します。

• - ルートノード：ノードの出発点
• - aノード: 'a'に対応
• - bノード: 'b'に対応
• - abノード: 'ab'に対応
• - bcノード: 'bc'に対応
• - bcaノード: 'bca'に対応
• - cabノード: 'cab'に対応

テキスト'abccab'を検索する場合、以下の手順で処理が進みます。

1. 'a'に対応するノードに移動し、'a'が検出されます。
2. 次に'b'を読み込み、'ab'に対応するノードに移動し、'ab'が検出されます。
3. 次に'c'を読み込み、トライ木には'abc'に対応するノードがないため、サフィックスリンクをたどって'c'に対応するノードを探しますが、それも存在しないためルートノードに戻ります。
4. 'c'に対応するノードがないため、ルートノードに留まります。
5. 次に'c'を読み込み、同様にルートノードに留まります。
6. 'a'を読み込み、'a'に対応するノードに移動し、'a'が検出されます。
7. 最後に'b'を読み込み、'ab'に対応するノードに移動し、'ab'が検出されます。

このように、'abccab'というテキストからは'a'が2回、'ab'が2回検出されます。

実用例

エイホ–コラシック法は、コンピュータウイルスのデータベース検索や、スパムフィルタリング、自然言語処理など、様々な分野で応用されています。特に、パターン辞書が頻繁に更新されるような環境では、オフラインでオートマトンを構築し、それを再利用することで、効率的な検索を可能にします。Unixコマンドのfgrepも、当初はこのアルゴリズムを基盤としていました。

まとめ

エイホ–コラシック法は、複数の文字列パターンを効率的に検索するための強力なアルゴリズムです。その線形計算量と、サフィックスリンクを用いた高速な検索処理は、様々な応用分野で活用されています。

参照

• - 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

もう一度検索