Aho-Corasickアルゴリズム

Aho-Corasickアルゴリズム

Aho—Corasick オートマトンの図
クラス	文字列検索、文字列マッチング
データ構造	文字列の有限状態機械

コンピュータサイエンスにおいて、アホ・コラシックアルゴリズムは、1975年にアルフレッド・V・アホとマーガレット・J・コラシックによって発明された文字列検索アルゴリズムです。 ^[1]これは、入力テキスト内で有限の文字列セット（「辞書」）の要素を検索する一種の辞書マッチングアルゴリズムです。すべての文字列を同時に一致させます。アルゴリズムの複雑さは、文字列の長さ、検索対象テキストの長さ、および出力一致の数の合計に比例します。すべての一致が見つかるため、すべての部分文字列が一致する場合（例：辞書 = a、aa、aaa、aaaaで入力文字列がaaaaの場合）、一致の数は2 乗^[要出典]になることに注意してください。

非公式には、アルゴリズムは、さまざまな内部ノード間に追加のリンクを持つトライに似た有限状態マシンを構築します。これらの追加の内部リンクにより、失敗した文字列の一致 (たとえば、 cartを含まないがart を含むトライでcartを検索すると、 carで始まるノードで失敗する) から、共通の接尾辞を共有するトライの他のブランチ (たとえば、前のケースでは、 attributeのブランチが最適な横方向の遷移である可能性があります) への高速遷移が可能になります。これにより、オートマトンが文字列の一致間をバックトラックなしで遷移できるようになります。

文字列辞書が事前にわかっている場合 (例:コンピュータ ウイルスデータベース)、オートマトンの構築をオフラインで 1 回実行し、コンパイルされたオートマトンを後で使用するために保存することができます。この場合、実行時間は入力の長さと一致するエントリの数に比例します。

Aho-Corasick 文字列マッチング アルゴリズムは、元のUnix コマンド fgrepの基礎を形成しました。

この例では、次の単語で構成される辞書を検討します: {a、ab、bab、bc、bca、c、caa}。

以下のグラフは、指定された辞書から構築された Aho–Corasick データ構造です。テーブルの各行はトライ内のノードを表し、列パスはルートからノードまでの (一意の) 文字シーケンスを示します。

データ構造には、辞書内の各文字列のプレフィックスごとに 1 つのノードがあります。したがって、(bca) が辞書内にある場合、(bca)、(bc)、(b)、および () のノードが存在します。ノードが辞書内にある場合、そのノードは青色のノードです。それ以外の場合は灰色のノードです。

各ノードから、1 文字を追加することで名前が見つかるノードまで、黒い有向の「子」アークがあります。したがって、(bc) から (bca) まで黒いアークがあります。

各ノードから、グラフ内でそのノードの可能な限り最長の厳密なサフィックスであるノードまで、青い有向「サフィックス」アークがあります。たとえば、ノード (caa) の場合、その厳密なサフィックスは (aa)、(a)、および () です。グラフ内に存在するこれらのうち最長のものは (a) です。したがって、(caa) から (a) への青いアークがあります。青いアークは、ルートから開始して幅優先検索(潜在的なサフィックス ノードは常に下位レベルにあります) を実行することで線形時間で計算できます。訪問したノードの青いアークのターゲットは、その親の青いアークをその最長のサフィックス ノードまでたどり、訪問したノードの文字と一致する文字を持つサフィックス ノードの子を検索することで見つけることができます。文字が子として存在しない場合は、次に長いサフィックス (再び青いアークをたどる) を見つけてから、文字を検索できます。これを、文字（ノードの子として）が見つかるまで、またはルート（常にすべての文字列の接尾辞になります）に到達するまで実行できます。

各ノードから辞書内の次のノードへの緑色の「辞書サフィックス」アークがあり、青いアークをたどることで到達できます。たとえば、(bca) から (a) への緑色のアークがあります。これは、(a) が辞書内の最初のノード (つまり青いノード) であり、青いアークをたどって (ca) に行き、次に (a) に行くと到達できるためです。緑色のアークは、青いノードが見つかるまで青いアークを繰り返したどり、この情報をメモすることで線形時間で計算できます。

各ステップで、現在のノードは子を見つけることによって拡張され、それが存在しない場合はそのサフィックスの子を見つけ、それが機能しない場合はサフィックスのサフィックスの子を見つけるというように続き、最後に何も見られなかった場合はルート ノードで終了します。

アルゴリズムがノードに到達すると、入力テキストの現在の文字位置で終了するすべての辞書エントリが出力されます。これは、そのノードから始めて辞書サフィックス リンクをたどって到達したすべてのノードを印刷することで行われ、辞書サフィックス リンクのないノードに到達するまで続きます。さらに、ノードが辞書エントリである場合は、そのノード自体も印刷されます。

入力文字列abccabを実行すると、次の手順が実行されます。

オリジナルの Aho-Corasick アルゴリズムでは、検索文字列のセットは固定されていると想定されています。このアルゴリズムは、アルゴリズムの適用中に新しい検索文字列が追加されるアプリケーションには直接適用されません。例としては、ユーザーがテキストを読みながら、新しい単語やフレーズを見つけたらハイライトしてインデックスを作成するインタラクティブなインデックス作成プログラムがあります。Bertrand Meyer は、検索中に検索文字列セットを段階的に拡張できる、アルゴリズムの増分バージョンを導入しました。このアルゴリズムでは、オリジナルのアルゴリズムの複雑さは維持されています。^[2]

• Commentz-Walterアルゴリズム

ウィキメディア・コモンズには、Aho-Corasick アルゴリズムに関連するメディアがあります。

• NIST のアルゴリズムとデータ構造の辞書に掲載されている Aho-Corasick (2019-07-15)
• Aho-Corasick アルゴリズム ビジュアライザー