Unter den String-Matching-Suchalgorithmen sind die beiden bekanntesten der KMP-Algorithmus (Knuth-Morris-Pratt) und der BM-Algorithmus (Boyer-Moore). Beide Algorithmen haben im schlimmsten Fall lineare Suchzeiten. In der Praxis ist der KMP-Algorithmus jedoch nicht viel schneller als die einfachste C-Bibliotheksfunktion strstr(), während der BM-Algorithmus häufig drei- bis fünfmal schneller ist als der KMP-Algorithmus (nicht persönlich praktiziert). Allerdings ist der BM-Algorithmus noch nicht der schnellste Algorithmus. Hier ist ein Suchalgorithmus, der Sunday-Algorithmus, der schneller ist als der BM-Algorithmus.
Die Idee des Sunday-Algorithmus ist der Idee schlechter Zeichen im BM-Algorithmus sehr ähnlich. Der einzige Unterschied besteht darin, dass der Sunday-Algorithmus, nachdem er keine Übereinstimmung gefunden hat, das Zeichen eine Position hinter dem aktuellen Teil der Zielzeichenfolge einnimmt, die der Musterzeichenfolge entspricht, um eine fehlerhafte Zeichenübereinstimmung durchzuführen. Wenn festgestellt wird, dass die Übereinstimmung fehlschlägt, wird beurteilt, ob das Zeichen am aktuellen Offset + Länge der Musterzeichenfolge + 1 (angenommen die K-Position) in der übergeordneten Zeichenfolge in der Musterzeichenfolge vorhanden ist. Wenn es vorhanden ist, richten Sie die Position am Zeichen in der Musterzeichenfolge aus und passen Sie sie dann von Anfang an an. Wenn sie nicht vorhanden ist, verschieben Sie die Musterzeichenfolge nach hinten, richten Sie sie an dem Zeichen bei k+1 der übergeordneten Zeichenfolge aus und schließen Sie sie dann ab übereinstimmen. Wiederholen Sie den obigen Vorgang, bis er gefunden wird oder die übergeordnete Zeichenfolge gefunden wird. Ich habe ein kleines Beispiel geschrieben, um den folgenden Algorithmus zu implementieren.
Im Code sind zwei String-Matching-Algorithmen implementiert, einer ist die Sunday-Methode und der andere ist die gewöhnliche Methode zum Verschieben jeweils eines Bits. Der Effizienzvergleich der beiden wird in der Hauptfunktion angezeigt, beide auf Nanosekundenebene . Die detaillierten Schritte des Algorithmus wurden mit entsprechenden Kommentaren im Code hinzugefügt. Was den BM-Algorithmus betrifft, werden wir ihn das nächste Mal gemeinsam vergleichen und analysieren, wenn er leer ist.
Kopieren Sie den Codecode wie folgt:
import java.util.HashMap;
import java.util.LinkedList;
java.util.List importieren;
java.util.Map importieren;
/**
* @Autor Scott
* @Datum 28. Dezember 2013
* @Beschreibung
*/
öffentliche Klasse SundySearch {
Zeichenfolgentext = null;
String-Muster = null;
int aktuellePos = 0;
/**
* Liste der ersten Zeichenpositionen der übereinstimmenden Teilzeichenfolge
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* Karte der übereinstimmenden Zeichen, zeichnet auf, welche Zeichen in der übereinstimmenden Zeichenfolge enthalten sind, und die letzte Verschiebung jedes Zeichens
*/
Map<Character, Integer> map = new HashMap<Character, Integer>();
public SundySearch(String text, String pattern) {
this.text = text;
this.pattern = Muster;
this.initMap();
};
/**
* Beim Abgleich mit Sonntag wird die Position des letzten Vorkommens jedes Zeichens im Muster in der Reihenfolge von links nach rechts gespeichert.
*/
private void initMap() {
for (int i = 0; i < pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Gewöhnlicher rekursiver String-Abgleich. Wenn der Abgleich fehlschlägt, wird eine Position vorgerückt
*/
public List<Integer> normalMatch() {
//Übereinstimmung fehlgeschlagen, weiter nach unten gehen
if (!matchFromSpecialPos(currentPos)) {
aktuellePos += 1;
if ((text.length() - currentPos) < pattern.length()) {
return matchedPosList;
}
normalMatch();
} anders {
//Erfolgreich übereinstimmen, Standort aufzeichnen
matchedPosList.add(currentPos);
aktuellePos += 1;
normalMatch();
}
return matchedPosList;
}
/**
* Sonntagsabgleich, vorausgesetzt, die Position des K-Zeichens im Text ist: aktueller Offset + Länge der Musterzeichenfolge + 1
*/
public List<Integer> sundayMatch() {
// Wenn keine Übereinstimmung erfolgreich ist
if (!matchFromSpecialPos(currentPos)) {
// Wenn das K-Zeichen in Text nicht in der Musterzeichenfolge vorkommt, überspringen Sie die gesamte Länge der Musterzeichenfolge.
if ((currentPos + pattern.length() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += pattern.length();
}anders {
// Wenn das K-Zeichen in Text in der Musterzeichenfolge vorkommt, richten Sie die Position des K-Zeichens in Text an der Position des letzten K-Zeichens in der Musterzeichenfolge aus.
if ((currentPos + pattern.length() + 1) > text.length()) {
aktuellePos += 1;
} anders {
currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
}
}
// Wenn das Match abgeschlossen ist, die anfängliche Verschiebung aller erfolgreichen Matches zurückgeben.
if ((text.length() - currentPos) < pattern.length()) {
return matchedPosList;
}
sundayMatch();
}anders {
//Wenn die Übereinstimmung erfolgreich ist, gehe ein Bit weiter und vergleiche dann erneut
matchedPosList.add(currentPos);
aktuellePos += 1;
sundayMatch();
}
return matchedPosList;
}
/**
* Überprüfen Sie, ob die Teilzeichenfolge ab dem angegebenen Offset von Text mit Muster übereinstimmt
*/
public boolean matchFromSpecialPos(int pos) {
if ((text.length()-pos) < pattern.length()) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
if (text.charAt(pos + i) == pattern.charAt(i)) {
if (i == (pattern.length()-1)) {
return true;
}
weitermachen;
} anders {
brechen;
}
}
return false;
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("hello ah Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
long begin = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - begin));
begin = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - begin));
}
}