エイホ-コラシックアルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスではAho –Corasickアルゴリズムは、1975年にAlfredV.AhoとMargaretJ.Corasickによって発明された文字列検索アルゴリズムです。 [1]これは、文字列の有限セットの要素を見つける一種の辞書照合アルゴリズムです。 (「辞書」)入力テキスト内。すべての文字列に同時に一致します。アルゴリズムの複雑さは、文字列の長さ、検索されたテキストの長さ、および出力の一致数に比例します。すべての一致が検出されるため、すべてのサブ文字列が一致する場合、2次の一致数が存在する可能性があることに注意してください(たとえば、dictionary = aaaaaaaaaaおよび入力文字列はaaaaです)。

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

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

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)。緑のアークは、青いノードが見つかるまで青いアークを繰り返しトラバースし、この情報 をメモ化することにより、線形時間で計算できます。

右側の辞書のトライの視覚化。サフィックスのリンクは青色で表示されています。緑色の辞書サフィックスリンク。辞書エントリに対応するノードは青色で強調表示されます。
辞書{a、ab、bab、bc、bca、c、caa}
辞書で サフィックスリンク Dictサフィックスリンク
()
(a) + ()
(ab) + (b)
(b) ()
(ba) (a) (a)
(バブ) + (ab) (ab)
(紀元前) + (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:3、c:3 (ab)接尾辞(b)から子(bc) 現在のノード、Dict接尾辞ノード
(c) ab c:4 (bc)から接尾辞(c)から接尾辞()から子(c) 現在のノード
(ca) b a:5 (c)子供へ(ca) Dict接尾辞ノード
(ab) ab:6 (ca)接尾辞(a)から子(ab) 現在のノード

動的検索リスト

元のAho-Corasickアルゴリズムは、検索文字列のセットが固定されていることを前提としています。アルゴリズムの適用中に新しい検索文字列が追加されるアプリケーションには直接適用されません。例としては、インタラクティブなインデックス作成プログラムがあります。このプログラムでは、ユーザーがテキストを確認し、新しい単語やフレーズを強調表示して、表示されたときにインデックスを作成します。Bertrand Meyerは、アルゴリズムのインクリメンタルバージョンを導入しました。このバージョンでは、元のアルゴリズムの複雑さを維持しながら、検索文字列セットを検索中にインクリメンタルに拡張できます。[2]

も参照してください

参照

  1. ^ Aho、Alfred V .; コラシック、マーガレットJ.(1975年6月)。「効率的な文字列照合:書誌検索の支援」。ACMの通信18(6):333–340。土井10.1145/360825.360855MR0371172 _ S2CID207735784 _
  2. ^ Meyer、Bertrand(1985)。「インクリメンタル文字列照合」(PDF)情報処理レター21(5):219–227。土井10.1016 / 0020-0190(85)90088-2

外部リンク