Erobern Sie die Zeichenfolgensuche mit dem Aho-Corasick-Algorithmus

Strings zu manipulieren und darin nach Mustern zu suchen, sind grundlegende Aufgaben in der Datenwissenschaft und eine typische Aufgabe für jeden Programmierer.

Effiziente String-Algorithmen spielen in vielen Data-Science-Prozessen eine wichtige Rolle. Oft sind sie es, die solche Verfahren für den praktischen Einsatz praktikabel machen.

In diesem Artikel lernen Sie einen der leistungsfähigsten Algorithmen zum Suchen nach Mustern in großen Textmengen kennen: den Aho-Corasick-Algorithmus. Dieser Algorithmus verwendet eine Trie-Datenstruktur (ausgesprochen „try“), um Suchmuster zu verfolgen, und verwendet eine einfache Methode, um effizient alle Vorkommen eines bestimmten Satzes von Mustern in einem beliebigen Textfleck zu finden.

Ein früherer Artikel im Toptal Engineering Blog demonstrierte einen Zeichenfolgensuchalgorithmus für dasselbe Problem. Der in diesem Artikel verfolgte Ansatz bietet eine verbesserte Berechnungskomplexität.

Der Knuth-Morris-Pratt (KMP)-Algorithmus

Um zu verstehen, wie wir effizient nach mehreren Mustern in einem Text suchen können, müssen wir uns zunächst einem einfacheren Problem zuwenden: der Suche nach einem einzelnen Muster in einem bestimmten Text.

Angenommen, wir haben einen großen Textklumpen der Länge N und ein Muster (nach dem wir im Text suchen möchten) der Länge M . Unabhängig davon, ob wir nach einem einzelnen Vorkommen dieses Musters oder nach allen Vorkommen suchen möchten, können wir mit dem KMP-Algorithmus eine Rechenkomplexität von O(N + M) erreichen.

Präfix-Funktion

Der KMP-Algorithmus funktioniert, indem er eine Präfixfunktion des gesuchten Musters berechnet. Die Präfix-Funktion berechnet vorab eine Fallback-Position für jedes Präfix des Musters.

Definieren wir unser Suchmuster als Zeichenfolge mit der Bezeichnung S . Für jeden Teilstring S[0..i] , wobei i >= 1 , finden wir das maximale Präfix dieses Strings, das auch das Suffix dieses Strings ist. Wir bezeichnen die Länge dieses Präfixes mit P[i] .

Für das Muster „Abrakadabra“ würde die Präfixfunktion die folgenden Fallback-Positionen erzeugen:

Die Präfixfunktion identifiziert ein interessantes Merkmal des Musters.

Nehmen wir als Beispiel ein bestimmtes Präfix des Musters: „abracadab“. Der Präfixfunktionswert für dieses Präfix ist zwei. Dies zeigt an, dass es für dieses Präfix „abracadab“ ein Suffix der Länge zwei gibt, das genau mit dem Präfix der Länge zwei übereinstimmt (dh das Muster beginnt mit „ab“ und das Präfix endet mit „ab“.) Außerdem ist dies die längste derartige Übereinstimmung für dieses Präfix.

Implementierung

Hier ist eine C#-Funktion, die verwendet werden kann, um die Präfixfunktion für eine beliebige Zeichenfolge zu berechnen:

 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 < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 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; }

Wenn Sie diese Funktion mit einem etwas längeren Muster „abcdabcabcdabcdab“ ausführen, wird Folgendes erzeugt:

Rechenkomplexität

Trotz der Tatsache, dass es zwei verschachtelte Schleifen gibt, beträgt die Komplexität der Präfixfunktion nur O(M) , wobei M die Länge des Musters S ist.

Dies lässt sich leicht erklären, indem man beobachtet, wie die Schleifen funktionieren.

Alle Iterationen der äußeren Schleife durch i können in drei Fälle unterteilt werden:

1. Erhöht k um eins. Die Schleife schließt eine Iteration ab.

2. Ändert den Nullwert von k nicht. Die Schleife schließt eine Iteration ab.

3. Ändert oder verringert einen positiven Wert von k nicht.

Die ersten beiden Fälle können höchstens M Mal ausgeführt werden.

Für den dritten Fall definieren wir P(s, i) = k1 und P(s, i + 1) = k2, k2 <= k1 . Jedem dieser Fälle sollten k1 - k2 Vorkommen des ersten Falls vorausgehen. Die Anzahl der Abnahmen überschreitet nicht k1 - k2 + 1 . Und insgesamt haben wir nicht mehr als 2 * M Iterationen.

Erläuterung des zweiten Beispiels

Schauen wir uns das zweite Beispielmuster „abcdabcabcdabcdab“ an. So verarbeitet es die Präfixfunktion Schritt für Schritt:

1. Bei einem leeren Teilstring und dem Teilstring „a“ der Länge eins wird der Wert der Präfixfunktion auf Null gesetzt. ( k = 0 )

2. Sehen Sie sich den Teilstring „ab“ an. Der aktuelle Wert von k ist Null und das Zeichen „b“ ist nicht gleich dem Zeichen „a“. Hier haben wir den zweiten Fall aus dem vorherigen Abschnitt. Der Wert von k bleibt auf Null und der Wert der Präfixfunktion für die Teilzeichenfolge „ab“ ist ebenfalls Null.

3. Dasselbe gilt für die Teilstrings „abc“ und „abcd“. Es gibt keine Präfixe, die gleichzeitig Suffixe dieser Teilzeichenfolgen sind. Der Wert für sie bleibt bei Null.

4. Sehen wir uns nun einen interessanten Fall an, den Teilstring „abcda“. Der aktuelle Wert von k ist immer noch Null, aber das letzte Zeichen unseres Teilstrings stimmt mit seinem ersten Zeichen überein. Dies löst die Bedingung s[k] == s[i] aus, wobei k == 0 und i == 4 . Das Array ist nullindiziert, und k ist der Index des nächsten Zeichens für das Präfix mit maximaler Länge. Das bedeutet, dass wir das Präfix mit maximaler Länge für unseren Teilstring gefunden haben, der auch ein Suffix ist. Wir haben den ersten Fall, wo der neue Wert von k eins ist und somit der Wert der Präfixfunktion P(„abcda“) eins ist.

5. Derselbe Fall tritt auch für die nächsten beiden Teilstrings auf, P(„abcdab“) = 2 und P(„abcdabc“) = 3 . Hier suchen wir nach unserem Muster im Text und vergleichen Zeichenfolgen Zeichen für Zeichen. Nehmen wir an, die ersten sieben Zeichen des Musters stimmen mit etwa sieben aufeinanderfolgenden Zeichen des verarbeiteten Textes überein, aber beim achten Zeichen stimmt es nicht überein. Was soll als nächstes passieren? Bei naivem String-Matching sollten wir sieben Zeichen zurückgeben und den Vergleichsprozess erneut mit dem ersten Zeichen unseres Musters beginnen. Mit dem Präfix-Funktionswert (hier P(“abcdabc”) = 3 ) wissen wir, dass unser dreistelliges Suffix bereits mit drei Zeichen Text übereinstimmt. Und wenn das nächste Zeichen im Text „d“ ist, wird die Länge des übereinstimmenden Teilstrings unseres Musters und des Teilstrings im Text auf vier erhöht („abcd“). Andernfalls ist P(„abc“) = 0 und wir beginnen den Vergleichsprozess ab dem ersten Zeichen des Musters. Wichtig ist aber, dass wir während der Bearbeitung des Textes nicht zurückkommen.

6. Der nächste Teilstring ist „abcdabca“. In der vorherigen Teilzeichenfolge war die Präfixfunktion gleich drei. Das bedeutet, dass k = 3 größer als Null ist und gleichzeitig haben wir eine Diskrepanz zwischen dem nächsten Zeichen im Präfix ( s[k] = s[3] = "d" ) und dem nächsten Zeichen im Suffix ( s[i] = s[7] = "a" ). Das bedeutet, dass wir die Bedingung s[k] != s[i] ausgelöst haben und dass das Präfix „abcd“ nicht das Suffix unseres Strings sein kann. Wir sollten den Wert von k verringern und nach Möglichkeit das vorherige Präfix zum Vergleich nehmen. Wie wir oben beschrieben haben, ist das Array nullindiziert, und k ist der Index des nächsten Zeichens, das wir anhand des Präfixes prüfen. Der letzte Index des aktuell übereinstimmenden Präfixes ist k - 1 . Wir nehmen den Wert der Präfixfunktion für das aktuell übereinstimmende Präfix k = result[k - 1] . In unserem Fall (dem dritten Fall) wird die Länge des maximalen Präfixes auf Null verringert und dann in der nächsten Zeile auf eins erhöht, da „a“ das maximale Präfix ist, das auch das Suffix unseres Teilstrings ist.

7. (Hier setzen wir unseren Berechnungsprozess fort, bis wir einen interessanteren Fall erreichen.)

8. Wir beginnen mit der Verarbeitung des folgenden Teilstrings: „abcdabcabcdabcd“. Der aktuelle Wert von k ist sieben. Wie bei „abcdabca“ oben sind wir auf eine Nichtübereinstimmung gestoßen: Da das Zeichen „a“ (das siebte Zeichen) nicht gleich dem Zeichen „d“ ist, kann der Teilstring „abcdabca“ nicht das Suffix unseres Strings sein. Jetzt bekommen wir den bereits berechneten Wert der Präfix-Funktion für „abcdabc“ (drei) und jetzt haben wir eine Übereinstimmung: Präfix „abcd“ ist auch das Suffix unseres Strings. Sein maximales Präfix und der Wert der Präfixfunktion für unseren Teilstring ist vier, weil das der aktuelle Wert von k wurde.

9. Wir setzen diesen Prozess bis zum Ende des Musters fort.

Kurz gesagt: Beide Zyklen benötigen nicht mehr als 3 M Iterationen, was die Komplexität von O(M) beweist. Die Speichernutzung ist ebenfalls O(M).

Implementierung des KMP-Algorithmus

 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 < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 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; }

Der obige Algorithmus durchläuft den Text Zeichen für Zeichen und versucht, das maximale Präfix sowohl für unser Muster als auch für eine Reihe aufeinanderfolgender Zeichen im Text zu erhöhen. Im Falle eines Scheiterns kehren wir nicht zu einer früheren Position im Text zurück. Wir kennen das maximale Präfix des gefundenen Teilstrings des Musters; dieses Präfix ist auch das Suffix dieses gefundenen Teilstrings und wir können die Suche einfach fortsetzen.

Die Komplexität dieser Funktion ist die gleiche wie die für die Präfixfunktion, wodurch die gesamte Berechnungskomplexität O(N + M) mit O(M) Speicher wird.

Wissenswertes: Die Methoden String.IndexOf() und String.Contains() im .NET-Framework haben einen Algorithmus mit der gleichen Komplexität unter der Haube.

Der Aho-Corasick-Algorithmus

Jetzt wollen wir dasselbe für mehrere Muster tun.

Angenommen, es gibt M Muster der Längen L1 , L2 , …, Lm . Wir müssen alle Übereinstimmungen von Mustern aus einem Wörterbuch in einem Text der Länge N finden.

Eine triviale Lösung wäre, einen beliebigen Algorithmus aus dem ersten Teil zu nehmen und ihn M -mal auszuführen. Wir haben die Komplexität O(N + L1 + N + L2 + … + N + Lm) , dh O(M * N + L) .

Jeder ernst genug Test tötet diesen Algorithmus.

Ein Wörterbuch mit den 1.000 häufigsten englischen Wörtern als Muster zu nehmen und damit die englische Version von Tolstois „Krieg und Frieden“ zu durchsuchen, würde eine ganze Weile dauern. Das Buch ist über drei Millionen Zeichen lang.

Wenn wir die 10.000 häufigsten englischen Wörter nehmen, arbeitet der Algorithmus etwa 10-mal langsamer. Offensichtlich verlängert sich bei Eingaben, die größer als diese sind, auch die Ausführungszeit.

Hier entfaltet der Aho-Corasick-Algorithmus seine Wirkung.

Die Komplexität des Aho-Corasick-Algorithmus ist O(N + L + Z) , wobei Z die Anzahl der Übereinstimmungen ist. Dieser Algorithmus wurde 1975 von Alfred V. Aho und Margaret J. Corasick erfunden.

Implementierung

Hier brauchen wir einen Versuch, und wir fügen unserem Algorithmus eine ähnliche Idee wie die oben beschriebenen Präfixfunktionen hinzu. Wir werden Präfixfunktionswerte für das gesamte Wörterbuch berechnen.

Jeder Scheitelpunkt im Trie speichert die folgenden Informationen:

 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; }

Es gibt mehrere Möglichkeiten, untergeordnete Verknüpfungen zu implementieren. Der Algorithmus hat im Fall eines Arrays eine Komplexität von O(N + L + Z) , aber dies hat einen zusätzlichen Speicherbedarf von O(L * q) , wobei q die Länge des Alphabets ist, da dies der Fall ist die maximale Anzahl von Kindern, die ein Knoten haben kann.

Wenn wir eine Struktur mit O(log(q))- Zugriff auf ihre Elemente verwenden, haben wir einen zusätzlichen Speicherbedarf von O(L) , aber die Komplexität des gesamten Algorithmus ist O((N + L) * log(q) +Z) .

Im Fall einer Hash-Tabelle haben wir O(L) zusätzlichen Speicher, und die Komplexität des gesamten Algorithmus beträgt O(N + L + Z) .

Dieses Tutorial verwendet eine Hash-Tabelle, da diese auch mit anderen Zeichensätzen, zB chinesischen Schriftzeichen, funktioniert.

Wir haben bereits eine Struktur für einen Knoten. Als Nächstes definieren wir eine Liste von Scheitelpunkten und initialisieren den Wurzelknoten des Tries.

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

Dann fügen wir alle Muster zum Trie hinzu. Dazu brauchen wir eine Methode, um dem Trie ein Wort hinzuzufügen:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

An diesem Punkt befinden sich alle Musterwörter in der Datenstruktur. Dies erfordert einen zusätzlichen Speicher von O(L) .

Als nächstes müssen wir alle Suffix-Links und Wörterbucheintrag-Links berechnen.

Um es klar und einfach verständlich zu machen, werde ich unseren Trie von der Wurzel bis zu den Blättern durchlaufen und ähnliche Berechnungen durchführen, wie wir sie für den KMP-Algorithmus gemacht haben, aber im Gegensatz zum KMP-Algorithmus, wo wir die maximale Länge finden Präfix, das auch das Suffix desselben Teilstrings war, finden wir jetzt das Suffix mit maximaler Länge des aktuellen Teilstrings, das auch das Präfix eines Musters im Trie ist. Der Wert dieser Funktion ist nicht die Länge des gefundenen Suffixes; es wird der Link zum letzten Zeichen des maximalen Suffix der aktuellen Teilzeichenfolge sein. Das meine ich mit dem Suffix-Link eines Scheitelpunkts.

Ich werde Scheitelpunkte nach Ebenen verarbeiten. Dafür werde ich einen Breitensuchalgorithmus (BFS) verwenden:

Und unten ist die Implementierung dieser Traversierung:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); 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]); } } }

Und unten ist die CalcSuffLink Methode zum Berechnen des Suffix-Links für jeden Scheitelpunkt (d. h. der Präfix-Funktionswert für jede Teilzeichenfolge im Trie):

 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; }

Die Komplexität dieser Methode ist O(L) ; Abhängig von der Implementierung der untergeordneten Sammlung kann die Komplexität O(L * log(q)) sein.

Der Komplexitätsnachweis ähnelt der Präfixfunktion des Komplexitätsnachweises im KMP-Algorithmus.

Schauen wir uns das folgende Bild an. Dies ist eine Visualisierung des Trie für das Wörterbuch { abba, cab, baba, caab, ac, abac, bac } mit all seinen berechneten Informationen:

Trie-Kanten sind tiefblau, Suffix-Links sind hellblau und Wörterbuch-Suffix-Links sind grün. Knoten, die Wörterbucheinträgen entsprechen, sind blau hervorgehoben.

Und jetzt brauchen wir nur noch eine Methode – die Verarbeitung eines Textblocks, den wir durchsuchen möchten:

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

Und jetzt ist dies einsatzbereit:

Bei der Eingabe haben wir eine Liste von Mustern:

 List<string> patterns;

Und Suchtext:

 string text;

Und so wird es zusammengeklebt:

 // 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 < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

Und das ist es! Sie wissen jetzt, wie dieser einfache, aber leistungsstarke Algorithmus funktioniert!

Aho-Corasick ist wirklich flexibel. Suchmuster müssen nicht nur Wörter sein, sondern wir können ganze Sätze oder zufällige Zeichenketten verwenden.

Leistung

Der Algorithmus wurde auf einem Intel Core i7-4702MQ getestet.

Für Tests habe ich zwei Wörterbücher genommen: Die 1.000 häufigsten englischen Wörter und die 10.000 häufigsten englischen Wörter.

Um alle diese Wörter dem Wörterbuch hinzuzufügen und die Datenstruktur für die Arbeit mit jedem der Wörterbücher vorzubereiten, benötigte der Algorithmus 55 ms bzw. 135 ms.

Der Algorithmus verarbeitete echte Bücher mit einer Länge von 3-4 Millionen Zeichen innerhalb von 1,0-1,3 Sekunden, während es für ein Buch mit rund 30 Millionen Zeichen 9,6 Sekunden dauerte.

Parallelisierung des Aho-Corasick-Algorithmus

Parallel zum Aho-Corasick-Algorithmus zu gehen ist überhaupt kein Problem:

Ein großer Text kann in mehrere Chunks unterteilt werden und mehrere Threads können verwendet werden, um jeden Chunk zu verarbeiten. Jeder Thread hat Zugriff auf den generierten Trie basierend auf dem Wörterbuch.

Was ist mit Wörtern, die an der Grenze zwischen Chunks aufgeteilt werden? Dieses Problem kann leicht gelöst werden.

Sei N die Länge unseres großen Textes, S die Größe eines Blocks und L die Länge des größten Musters im Wörterbuch.

Jetzt können wir einen einfachen Trick anwenden. Wir teilen Chunks mit etwas Überlappung am Ende, indem wir zum Beispiel [S * (i - 1), S * i + L - 1] nehmen, wobei i der Index des Chunks ist. Wenn wir eine Musterübereinstimmung erhalten, können wir leicht den Startindex der aktuellen Übereinstimmung abrufen und einfach überprüfen, ob dieser Index ohne Überschneidungen innerhalb des Chunk-Bereichs liegt, [S * (i - 1), S * i - 1] .

Ein vielseitiger String-Suchalgorithmus

Der Aho-Corasick-Algorithmus ist ein leistungsstarker String-Matching-Algorithmus, der die beste Komplexität für jede Eingabe bietet und nicht viel zusätzlichen Speicher benötigt.

Der Algorithmus wird häufig in verschiedenen Systemen verwendet, z. B. Rechtschreibprüfung, Spamfilter, Suchmaschinen, Bioinformatik/DNA-Sequenzsuche usw. Tatsächlich verwenden einige beliebte Tools, die Sie möglicherweise täglich verwenden, diesen Algorithmus hinter den Kulissen.

Die Präfixfunktion des KMP-Algorithmus an sich ist ein interessantes Werkzeug, das die Komplexität des Single-Pattern-Matching auf die lineare Zeit reduziert. Der Aho-Corasick-Algorithmus folgt einem ähnlichen Ansatz und verwendet eine Trie-Datenstruktur, um dasselbe für mehrere Muster zu tun.

Ich hoffe, Sie fanden dieses Tutorial zum Aho-Corasick-Algorithmus hilfreich.