String-Suchalgorithmen für große Texte mit Java

1. Einleitung

In diesem Artikel werden verschiedene Algorithmen für die Suche nach einem Muster in einem großen Text gezeigt. Wir werden jeden Algorithmus mit dem bereitgestellten Code und dem einfachen mathematischen Hintergrund beschreiben.

Beachten Sie, dass bereitgestellte Algorithmen nicht die beste Möglichkeit sind, eine Volltextsuche in komplexeren Anwendungen durchzuführen. Um die Volltextsuche richtig durchzuführen, können wir Solr oder ElasticSearch verwenden.

2. Algorithmen

Wir beginnen mit einem naiven Textsuchalgorithmus, der am intuitivsten ist und dabei hilft, andere fortgeschrittene Probleme zu entdecken, die mit dieser Aufgabe verbunden sind.

2.1. Hilfsmethoden

Bevor wir beginnen, definieren wir einfache Methoden zur Berechnung von Primzahlen, die wir im Rabin-Karp-Algorithmus verwenden:

public static long getBiggerPrime(int m) { BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random()); return prime.longValue(); } private static int getNumberOfBits(int number) { return Integer.SIZE - Integer.numberOfLeadingZeros(number); } 

2.2. Einfache Textsuche

Der Name dieses Algorithmus beschreibt ihn besser als jede andere Erklärung. Es ist die natürlichste Lösung:

public static int simpleTextSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0; while ((i + patternSize) = patternSize) return i; } i += 1; } return -1; }

Die Idee dieses Algorithmus ist einfach: Durchlaufen Sie den Text und prüfen Sie, ob alle Buchstaben des Musters mit dem Text übereinstimmen, wenn der erste Buchstabe des Musters übereinstimmt.

Wenn m eine Anzahl der Buchstaben im Muster ist und n die Anzahl der Buchstaben im Text ist, ist die zeitliche Komplexität dieser Algorithmen O (m (nm + 1)) .

Das Worst-Case-Szenario tritt im Fall eines Strings mit vielen Teilvorkommen auf:

Text: baeldunbaeldunbaeldunbaeldun Pattern: baeldung

2.3. Rabin Karp Algorithmus

Wie oben erwähnt, ist der Algorithmus für die einfache Textsuche sehr ineffizient, wenn Muster lang sind und viele wiederholte Elemente des Musters vorhanden sind.

Die Idee des Rabin Karp-Algorithmus besteht darin, mithilfe von Hashing ein Muster in einem Text zu finden. Zu Beginn des Algorithmus müssen wir einen Hash des Musters berechnen, der später im Algorithmus verwendet wird. Dieser Vorgang wird als Fingerabdruckberechnung bezeichnet. Eine ausführliche Erklärung finden Sie hier.

Das Wichtige am Vorverarbeitungsschritt ist, dass seine Zeitkomplexität O (m) ist und die Iteration durch Text O (n) benötigt, was die Zeitkomplexität des gesamten Algorithmus O (m + n) ergibt .

Code des Algorithmus:

public static int RabinKarpMethod(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; long prime = getBiggerPrime(patternSize); long r = 1; for (int i = 0; i < patternSize - 1; i++) { r *= 2; r = r % prime; } long[] t = new long[textSize]; t[0] = 0; long pfinger = 0; for (int j = 0; j < patternSize; j++) { t[0] = (2 * t[0] + text[j]) % prime; pfinger = (2 * pfinger + pattern[j]) % prime; } int i = 0; boolean passed = false; int diff = textSize - patternSize; for (i = 0; i <= diff; i++) { if (t[i] == pfinger) { passed = true; for (int k = 0; k < patternSize; k++) { if (text[i + k] != pattern[k]) { passed = false; break; } } if (passed) { return i; } } if (i < diff) { long value = 2 * (t[i] - r * text[i]) + text[i + patternSize]; t[i + 1] = ((value % prime) + prime) % prime; } } return -1; }

Im schlimmsten Fall beträgt die Zeitkomplexität für diesen Algorithmus O (m (n-m + 1)) . Im Durchschnitt weist dieser Algorithmus jedoch eine zeitliche Komplexität von O (n + m) auf .

Zusätzlich gibt es eine Monte-Carlo-Version dieses Algorithmus, die schneller ist, aber zu falschen Übereinstimmungen führen kann (falsch positive Ergebnisse).

2.4 Knuth-Morris-Pratt-Algorithmus

Im Algorithmus für die einfache Textsuche haben wir gesehen, wie langsam der Algorithmus sein kann, wenn viele Teile des Textes mit dem Muster übereinstimmen.

Die Idee des Knuth-Morris-Pratt-Algorithmus ist die Berechnung der Verschiebungstabelle, die uns die Informationen liefert, wo wir nach unseren Musterkandidaten suchen sollten.

Java-Implementierung des KMP-Algorithmus:

public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; int[] shift = KnuthMorrisPrattShift(pattern); while ((i + patternSize) = patternSize) return i; } if (j > 0) { i += shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i++; j = 0; } } return -1; }

Und so berechnen wir die Verschiebungstabelle:

public static int[] KnuthMorrisPrattShift(char[] pattern) { int patternSize = pattern.length; int[] shift = new int[patternSize]; shift[0] = 1; int i = 1, j = 0; while ((i + j) 
    
      0) { i = i + shift[j - 1]; j = Math.max(j - shift[j - 1], 0); } else { i = i + 1; j = 0; } } } return shift; }
    

Die zeitliche Komplexität dieses Algorithmus beträgt ebenfalls O (m + n) .

2.5. Einfacher Boyer-Moore-Algorithmus

Zwei Wissenschaftler, Boyer und Moore, hatten eine andere Idee. Vergleichen Sie das Muster mit dem Text von rechts nach links anstatt von links nach rechts, während Sie die Verschiebungsrichtung beibehalten:

public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) { int patternSize = pattern.length; int textSize = text.length; int i = 0, j = 0; while ((i + patternSize) <= textSize) { j = patternSize - 1; while (text[i + j] == pattern[j]) { j--; if (j < 0) return i; } i++; } return -1; }

Wie erwartet läuft dies in O (m * n) Zeit. Dieser Algorithmus führte jedoch zur Implementierung des Auftretens und der Übereinstimmungsheuristik, was den Algorithmus erheblich beschleunigt. Mehr finden wir hier.

2.6. Boyer-Moore-Horspool-Algorithmus

Es gibt viele Variationen der heuristischen Implementierung des Boyer-Moore-Algorithmus, und die einfachste ist die Horspool-Variation.

Diese Version des Algorithmus heißt Boyer-Moore-Horspool, und diese Variante löste das Problem der negativen Verschiebungen (wir können das Problem der negativen Verschiebung in der Beschreibung des Boyer-Moore-Algorithmus nachlesen).

Wie beim Boyer-Moore-Algorithmus beträgt die Zeitkomplexität im ungünstigsten Fall O (m * n), während die durchschnittliche Komplexität O (n) beträgt. Die Speicherplatznutzung hängt nicht von der Größe des Musters ab, sondern nur von der Größe des Alphabets (256), da dies der Maximalwert des ASCII-Zeichens im englischen Alphabet ist:

public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) { int shift[] = new int[256]; for (int k = 0; k < 256; k++) { shift[k] = pattern.length; } for (int k = 0; k < pattern.length - 1; k++){ shift[pattern[k]] = pattern.length - 1 - k; } int i = 0, j = 0; while ((i + pattern.length) <= text.length) { j = pattern.length - 1; while (text[i + j] == pattern[j]) { j -= 1; if (j < 0) return i; } i = i + shift[text[i + pattern.length - 1]]; } return -1; }

4. Fazit

In diesem Artikel haben wir verschiedene Algorithmen für die Textsuche vorgestellt. Da mehrere Algorithmen einen stärkeren mathematischen Hintergrund erfordern, haben wir versucht, die Hauptidee unter jedem Algorithmus darzustellen und auf einfache Weise bereitzustellen.

Und wie immer ist der Quellcode auf GitHub zu finden.