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

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]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

この関数を少し長いパターン「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 。

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

javascriptの日付を文字列に変更

iを介したすべての外部ループの反復3つのケースに分けることができます：

  1. 増加k一つ。ループは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'） 1であります。

  5. 同じケースが次の2つの部分文字列にも発生します。 P（“ abcdab”）= 2 そして 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 = result[k - 1]のプレフィックス関数の値を取得します。この場合（3番目の場合）、最大プレフィックスの長さはゼロに減少し、次の行では1まで増加します。これは、「a」がサブストリングのサフィックスでもある最大プレフィックスであるためです。

    llc ansまたはc法人です

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

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

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

つまり、どちらのサイクルも3 M回の反復しか必要としないため、複雑さがO（M）であることがわかります。メモリ使用量もO（M）です。

KMPアルゴリズムの実装

public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. 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） 、つまり O（M * N + L） 。

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

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

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

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

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

実装

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

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

public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

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

でいくつかの構造を使用する場合 O（log（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; } // Processing children of the root (one character substrings) 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; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. 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) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j

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

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

List patterns;

そして検索テキスト：

string text;

そして、これを接着する方法は次のとおりです。

// Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i

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

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

パフォーマンス

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

テストのために、私は2つの辞書を取りました：1,000の最も一般的な英語の単語と10,000の最も一般的な英語の単語。

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

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

Aho-Corasickアルゴリズムの並列化

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

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

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

チャンク間の境界で単語が分割されるのはどうですか？この問題は簡単に解決できます。

しましょう 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アルゴリズムに関するこのチュートリアルがお役に立てば幸いです。

効率的なアプローチ-無駄のないUXMVPを設計する方法

Uxデザイン

効率的なアプローチ-無駄のないUXMVPを設計する方法
請求の抽出：GraphQL内部API最適化の物語

請求の抽出：GraphQL内部API最適化の物語

バックエンド