データサイエンスとデータベース

Aho-Corasickアルゴリズムで文字列検索を征服する

文字列を操作してパターンを見つけることは、データサイエンスの基本的なタスクであり、プログラマーにとっては一般的なタスクです。

効率的な文字列アルゴリズムは、多くのデータサイエンスプロセスで重要な役割を果たします。それらはしばしばそのようなプロセスを実用化するのに十分実行可能にするものです。



効率的な文字列探索問題のためのAho-Corasickアルゴリズム



この記事では、大量のテキストのパターンを見つけるための最も強力なアルゴリズムの1つであるAho-Corasickアルゴリズムについて学習します。このアルゴリズムは、 トライのデータ構造 （「試行」と発音）検索パターンを追跡し、簡単な方法を使用して、テキストバブル内の特定のパターンセットのすべての出現を効率的に検索します。

ApeeScape Engineering Blogの以前の記事では、同じ問題の文字列検索アルゴリズムが示されていました。この記事で採用されているアプローチは、計算の複雑さを向上させます。



Knuth-Morris-Pratt（KMP）アルゴリズム

テキスト内の複数のパターンを効率的に検索する方法を理解するには、まず、特定のテキスト内の単一のパターンを見つけるという、より簡単な問題に取り組む必要があります。

長さの大きなテキストブロブがあるとします N と長さのパターン（テキストで見つけたい） M 。このパターンの単一のオカレンス、またはすべてのオカレンスを検索する場合、次の計算の複雑さを実現できます。 O（N + M） KMPアルゴリズムを使用します。

プレフィックス機能

KMPアルゴリズムは、探しているパターンのプレフィックス関数を計算することによって機能します。プレフィックス関数は、パターン内の各プレフィックスの代替位置を事前に計算します。



検索パターンをSというラベルの付いた文字列として定義しましょう。各部分文字列S [0..i]、ここでi> = 1について、この文字列の最大プレフィックスが見つかります。これは、この文字列のサフィックスでもあります。このプレフィックスの長さをマークしますP [i]。

「abracadabra」パターンの場合、プレフィックス関数は次のバッキング位置を生成します。

インデックス（i） 0 1 2 3 4 5 6 7 8 9 10
キャラクター に b r に c に d に b r に
プレフィックス長（P[i]） 0 0 0 1 0 1 0 1 2 3 4

プレフィックス関数は、パターンの興味深い特徴を識別します。

例として、パターンの特定の接頭辞「abracadab」を取り上げましょう。このプレフィックスのプレフィックス関数の値は2です。これは、このプレフィックス「abracadab」の場合、長さ2のプレフィックスと完全に一致する長さ2のサフィックスがあることを示します（つまり、パターンは「ab」で始まり、プレフィックスは「ab」で終わります）。また、これはこのプレフィックスの最長一致です。

実装

これは、任意の文字列のプレフィックス関数を計算するために使用できるC＃関数です。

public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // matriz con valores de función de prefijo result[0] = 0; // la función de prefijo siempre es cero para el primer símbolo (su caso degenerado) int k = 0; // valor actual de la función de prefijo para (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // hemos encontrado el prefijo más largo - caso 1 result[i] = k; // almacenar este resultado en la matriz } resultado de devolución; }

この関数を少し長いパターンで実行すると、「abcdabcabcdabcdab」は次のようになります。

インデックス（i） 0 1 2 3 4 5 6 7 8 9 10 十一 12 13 14 15 16
キャラクター に b c d に b c に b c d に b c d に b
プレフィックス関数（P[i]） 0 0 0 0 1 2 3 1 2 3 4 5 6 7 4 5 6

計算の複雑さ

ネストされたループが2つありますが、プレフィックス関数の複雑さは単純です。 O（M） 、 どこ M パターンの長さです S 。

組織のゲシュタルト原則を彼らのイラストと一致させます。

これは、ループがどのように機能するかを調べることで簡単に説明できます。

iを通る外側のループのすべての反復それらは3つのケースに分けることができます：

  1. 増加k 1つに。ループは1回の反復を完了します。

  2. kのゼロ値は変更しません。ループは1回の反復を完了します。

  3. kの正の値を変更または減少させることはありません。

最初の2つのケースは最大で実行できます M 回。

3番目のケースでは、P (s, i) = k1を定義しましょう。およびP (s, i + 1) = k2, k2 <= k1。これらの各ケースの前には、k1 - k2が出現する必要があります。最初のケースの。減少カウントはk1 - k2 + 1を超えません。そして合計で私達は 2 * M 反復。

2番目の例の説明

2番目のパターンパターン「abcdabcabcdabcdab」を見てみましょう。プレフィックス関数がそれを段階的に処理する方法は次のとおりです。

  1. 空の部分文字列と長さ1の部分文字列 'a'の場合、プレフィックス関数の値はゼロに設定されます。 （k = 0）

  2. 部分文字列「ab」を見てください。 kの現在の値はゼロであり、文字「b」は文字「a」と等しくありません。ここでは、前のセクションの2番目のケースがあります。 kの値ゼロのままで、部分文字列「ab」のプレフィックス関数の値もゼロです。

  3. 部分文字列「abc」と「abcd」についても同じです。これらの部分文字列の接尾辞でもある接頭辞はありません。それらの値はゼロのままです。

  4. 次に、興味深いケースである部分文字列「abcda」を見てみましょう。 kの現在の値まだゼロですが、部分文字列の最後の文字が最初の文字と一致します。これにより、s [k] == s [i]の条件がトリガーされます。ここで、k == 0および i == 4。配列のインデックスはゼロで、k最大長プレフィックスの次の文字のインデックスです。これは、サフィックスでもある部分文字列の最大長のプレフィックスが見つかったことを意味します。 kの新しい値である最初のケースがあります。は1であるため、プレフィックス関数の値 P（ 'abcda'） 一つです。

  5. 同じケースは、次の2つの部分文字列でも発生します。 P（“ abcdab”）= 2 Y P（“ abcdabc”）= 3 。ここでは、文字列を文字ごとに比較して、テキスト内のパターンを探しています。パターンの最初の7文字が、処理されたテキストの約7つの連続する文字と一致しているが、8番目の文字が一致していないとします。次に何が起こるべきですか？単純な文字列一致の場合、7文字を返し、パターンの最初の文字から比較プロセスを再開する必要があります。プレフィックス関数の値（ここでは P（“ abcdabc”）= 3 ）3文字のサフィックスはすでに3文字のテキストと一致していることがわかっています。また、テキスト内の次の文字が「d」の場合、パターンの一致する部分文字列とテキスト内の部分文字列の長さが4に増加します（「abcd」）。それどころか、 P（“ abc”）= 0 パターンの最初の文字から比較プロセスを開始します。ただし、重要なことは、テキスト処理中に戻らないことです。

  6. 次の部分文字列は「abcdabca」です。上記の部分文字列では、プレフィックス関数は3に等しかった。これは、k = 3がゼロより大きく、同時にプレフィックスの次の文字（s [k] = s [3] = 'd'）とサフィックスの次の文字（s [i] = s [7] ='a'）の間に不一致があります。これは、s [k]! =S [i]の条件をアクティブにし、接頭辞「abcd」を文字列の接尾辞にすることはできないことを意味します。 kの値を減らす必要があります可能であれば、上記のプレフィックスを使用して比較します。前に説明したように、配列のインデックスはゼロで、kプレフィックスからチェックする次の文字のインデックスです。現在一致しているプレフィックスの最後のインデックスはk - 1です。現在一致しているプレフィックスk = resultado [k - 1]のプレフィックス関数の値を取得します。私たちの場合（3番目の場合）、最大プレフィックスの長さはゼロに短縮され、次の行では1に増加します。これは、「a」が最大プレフィックスであり、サブストリングのサフィックスでもあるためです。

    node.jsは何に使用されますか

  7. （ここでは、より興味深いケースに到達するまで計算プロセスを続けます。）

  8. 次の部分文字列の処理を開始します： 'abcdabcabcdabcd'。 kの現在の値7です。上記の「abcdabca」と同様に、不一致が発生しました。文字「a」（7番目の文字）が文字「d」と等しくないため、部分文字列「abcdabca」を文字列のサフィックスにすることはできません。これで、「abcdabc」（3つ）のプレフィックス関数からすでに計算された値を取得し、一致するものがあります。プレフィックス「abcd」は文字列のサフィックスでもあります。その最大プレフィックスと部分文字列のプレフィックス関数の値は4です。これは、kの現在の値だからです。

  9. パターンが終了するまでこのプロセスを続けます。

つまり、両方のサイクルで3M回の反復しか必要ありません。これは、複雑さがO（M）であることを示しています。メモリ使用量もO（M）です。

KMPアルゴリズムの実装

public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calcular la función de prefijo para una cadena de patrón // La idea es la misma que en la función de prefijo descrita anteriormente, pero ahora // estamos comparando prefijos de texto y patrón. // El valor del prefijo de longitud máxima de la cadena del patrón que se encontró // en el texto: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // Si ocurrió una coincidencia, aumenta la longitud de la longitud máxima // prefijo. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // Si la longitud del prefijo tiene la misma longitud que la cadena del patrón, // significa que hemos encontrado una subcadena coincidente en el texto. if (maxPrefixLength == s.Length) { // Podemos devolver este valor o realizar esta operación. int idx = i - s.Length + 1; // Obtenga el prefijo de longitud máxima anterior y continúe la búsqueda. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

上記のアルゴリズムは、テキストを1文字ずつ繰り返し処理し、パターンとテキスト内の連続する文字のシーケンスの両方の最大プレフィックスを増やしようとします。失敗した場合、テキストの前の位置に戻ることはありません。パターンで見つかった部分文字列の最大プレフィックスがわかっています。このプレフィックスは、この見つかった部分文字列のサフィックスでもあり、検索を続行できます。

この関数の複雑さはプレフィックス関数の場合と同じであるため、全体的な計算が複雑になります。 O（N + M） と O（M） メモリ。

雑学クイズ：String.IndexOf ()およびString.Contains () .NET Frameworkには、内部で同じ複雑さのアルゴリズムがあります。

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

ここで、複数のパターンに対して同じことを行います。

パターンがあるとしましょう M 長さの L1 、 L2 、...、 Lm 。長さのテキスト内の辞書からすべてのパターン一致を見つける必要があります N 。

簡単な解決策は、最初の部分から任意のアルゴリズムを取得し、それを** M **回実行することです。私たちは複雑さを持っています O（N + L1 + N + L2 +…+ N + Lm） 、つまり （M * N + L） 。

深刻なテストを行うと、このアルゴリズムは無効になります。

最も一般的な1,000語の英語の単語をパターンとして辞書を取り、それを使用してトルストイの「戦争と平和」の英語版を検索するには、かなり時間がかかります。この本は300万文字以上あります。

英語で最も一般的な10,000語を使用すると、アルゴリズムの実行速度は約10倍遅くなります。明らかに、これより大きい入力では、実行時間も長くなります。

これは、Aho-Corasickアルゴリズムがその魔法を働かせる場所です。

Aho-Corasickアルゴリズムの複雑さは O（N + L + Z） 、 どこ と 一致の数です。このアルゴリズムはによって発明されました アルフレッド・エイホ Y マーガレットJ.コラシック 1975年。

実装

ここではトライが必要であり、上記のプレフィックス関数と同様のアイデアをアルゴリズムに追加します。辞書全体のプレフィックス関数値を計算します。

トライの各頂点には、次の情報が格納されます。

public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Enlaces a los vértices secundarios en el trie: // Clave: Un solo caracter // Valor: El ID del vértice public Hashtable Children; // Indica que una palabra del diccionario termina en este vértice public bool Leaf; // Enlace al vértice padre public int Parent; // Char que nos mueve desde el vértice padre al vértice actual public char ParentChar; // Enlace de sufijo del vértice actual (el equivalente de P [i] del algoritmo KMP) public int SuffixLink; // Enlace al vértice de hoja de la palabra de longitud máxima que podemos hacer con el prefijo actual public int EndWordLink; // Si el vértice es la hoja, guardamos el ID de la palabra public int WordID; }

二次リンクを実装する方法はいくつかあります。アルゴリズムの複雑さは O（N + L + Z） アレイの場合、ただしこれには追加のメモリ要件があります O（L * q） 、ここでqはアルファベットの長さです。これは、ノードが持つことができる子の最大数であるためです。

でいくつかの構造を使用する場合 O（ログ（q）） その要素へのアクセスには、追加のメモリ要件があります。 O（L） 、しかし完全なアルゴリズムの複雑さは O（（N + L）* log（q）+ Z） 。

ハッシュテーブルの場合、 O（L） 追加のメモリ、およびアルゴリズム全体の複雑さは O（N + L + Z） 。

このチュートリアルでは、漢字などのさまざまな文字セットでも機能するため、ハッシュテーブルを使用します。

頂点の構造はすでにあります。次に、頂点のリストを定義し、トライのルートノードを開始します。

public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

次に、すべてのパターンをトライに追加します。このために、トライに単語を追加するメソッドが必要です。

public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i

この時点で、すべてのパターンワードがデータ構造に含まれています。これには、の追加メモリが必要です O（L） 。

次に、すべてのサフィックスリンクと辞書入力リンクを計算する必要があります。

明確でわかりやすくするために、ルートからリーフまでトライを実行し、KMPアルゴリズムで行ったのと同様の計算を行いますが、KMPアルゴリズムとは異なり、最大プレフィックス長も同じ部分文字列の接尾辞です。次に、現在の部分文字列の最大長の接尾辞を見つけます。これは、トライ内のパターンの接頭辞でもあります。この関数の値は、見つかったサフィックスの長さではありません。現在の部分文字列の最大サフィックスの最後の文字へのリンクになります。これは、頂点のリンク接尾辞が意味するものです。

レベルごとに頂点を処理します。そのために、私はアルゴリズムを使用します 幅で検索（BFS） ：

振幅探索アルゴリズムによって処理されるトライ

そして、以下はこのクロスオーバーの実装です：

public void PrepareAho() { Queue vertexQueue = new Queue(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

そして、以下はメソッドですCalcSuffLink各頂点の接尾辞バインディング（つまり、トライ内の各部分文字列の接頭辞関数値）を計算するには：

public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Procesamiento de hijos de la raíz (subcadenas de un caracter) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Los casos anteriores son casos degenerados en cuanto al cálculo de la función del prefijo; // el valor siempre es 0 y los enlaces al vértice raíz. // Para calcular el sufijo link para el vértice actual, necesitamos el sufijo // enlace para el padre del vértice y el personaje que nos movió a la // vértice actual. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // Desde este vértice y su subcadena comenzaremos a buscar el máximo // prefijo para el vértice actual y su subcadena. while (true) { // Si hay una ventaja con el carácter necesario, actualizamos nuestro enlace de sufijo // y abandonar el ciclo if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // De lo contrario, estamos saltando por enlaces de sufijo hasta que lleguemos a la raíz // (equivalente a k == 0 en el cálculo de la función de prefijo) o encontramos un // mejor prefijo para la subserie actual. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // Cuando completamos el cálculo del enlace de sufijo para el actual // vertex, debemos actualizar el enlace al final de la palabra de longitud máxima // que se puede producir a partir de la subcadena actual. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

この方法の複雑さは** O（L）**です。子コレクションの実装に応じて、複雑さは** O（L * log（q））**になる可能性があります。

複雑度テストは、KMPアルゴリズムの複雑度プレフィックス関数テストに似ています。

次の画像を見てみましょう。これは辞書のトライの表示です{abba, cab, baba, caab, ac, abac, bac}すべての情報を計算して：

モノのインターネット家電

abba、cab、baba、caab、ac、abac、およびbacで構成される辞書のトライ

トライの境界線は濃い青、サフィックスのリンクは水色、辞書のサフィックスは緑です。辞書エントリに対応するノードは青色で強調表示されます。

そして今、もう1つの方法が必要です。検索するテキストのブロックを処理することです。

public int ProcessString(String text) { // Estado actual del valor int currentState = root; // Valor de resultado apuntado int result = 0; for (int j = 0; j

そして、これで使用できるようになりました。

入力には、パターンのリストがあります。

List patterns;

そして、テキストを検索します。

string text;

そしてここでそれをすべて一緒に接着する方法：

// Inicia la estructura trie. Como parámetro opcional podemos poner el aproximado // tamaño del trie para asignar memoria solo una vez para todos los nodos. Aho ahoAlg = new Aho(); for (int i = 0; i

そしてそれはです！これで、このシンプルで強力なアルゴリズムがどのように機能するかがわかりました。

エイホ-コラシックは本当に柔軟性があります。検索パターンは単語だけである必要はありませんが、文全体またはランダムな文字列を使用できます。

パフォーマンス

アルゴリズムは、Intel Corei7-4702MQでテストされました。

テストでは、2つの辞書を使用しました。英語で最も一般的な1,000語と、英語で最も一般的な10,000語です。

これらすべての単語を辞書に追加し、各辞書で機能するデータ構造を準備するには、アルゴリズムにそれぞれ55ミリ秒と135ミリ秒が必要でした。

アルゴリズムは、実際の本の長さが100〜1.3秒以内に300〜400万文字を処理しましたが、約3,000万文字の本の場合は9.6秒かかりました。

Aho-Corasickアルゴリズムを並列化する

Aho-Corasickアルゴリズムと並行して実行することは、まったく問題ではありません。

Aho-Corasickアルゴリズムは、特定のテキストの4つの部分で並行して実行されます。

大きなテキストは複数のチャンクに分割でき、複数のスレッドを使用して各チャンクを処理できます。各スレッドは、ディクショナリに基づいて生成されたトライにアクセスできます。

フラグメント間の境界で分割されている単語はどうですか？この問題は簡単に解決できます。

しましょう N 私たちの大きなテキストの長さであり、 S はフラグメントのサイズであり、 L 辞書で最大のパターンの長さである。

これで、簡単なトリックを使用できます。たとえば、[S * (i - 1), S * i + L - 1]をとって、最後にオーバーラップしてピースを分割します。ここで、iチャンクのインデックスです。パターンマッチを取得すると、現在のマッチの開始インデックスを簡単に取得でき、このインデックスがオーバーラップのないチャンクの範囲内にあることを確認できます[S * (i - 1), S * i - 1]。

用途の広い文字列検索アルゴリズム

Aho-Corasickアルゴリズムは、あらゆる入力に対して最高の複雑さを提供し、多くの追加メモリを必要としない強力な文字列結合アルゴリズムです。

このアルゴリズムは、スペルチェッカー、スパムフィルター、検索エンジン、バイオインフォマティクス/ DNAシーケンス検索などのさまざまなシステムでよく使用されます。実際、毎日使用できる人気のあるツールの中には、このアルゴリズムを舞台裏で使用しているものがあります。

KMPアルゴリズム自体のプレフィックス関数は、単一パターンマッチングの複雑さを線形時間に減らす興味深いツールです。 Aho-Corasickアルゴリズムは同様のアプローチに従い、トライデータ構造を使用して複数のパターンに対して同じことを行います。

Aho-Corasickアルゴリズムに関するこのチュートリアルがお役に立てば幸いです。

生産的なデザイン批評のためのヒント

設計プロセス

生産的なデザイン批評のためのヒント
.NETCore-ワイルドでオープンソース化。マイクロソフト、どうしてそんなに時間がかかったの？

.NETCore-ワイルドでオープンソース化。マイクロソフト、どうしてそんなに時間がかかったの？

データサイエンスとデータベース