Schneller Algorithmus für die Suche nach Teilzeichenfolgen in einer Zeichenfolge
Ich hätte gerne einen effizienten Algorithmus (oder eine Bibliothek), mit der ich in Java nach Teilzeichenfolgen in einer Zeichenfolge suchen kann.
Was ich gerne machen würde ist:
Eine Eingabezeichenfolge gegeben -INSTR:
"BCDEFGH"
Und eine Reihe von Kandidaten-Strings -CAND:
"AB", "CDE", "FG", "H", "IJ"
Finde irgendeinCAND Zeichenfolgen, die als Teilzeichenfolgen in übereinstimmenINSTR
In diesem Beispiel würde ich "CDE", "FG" und "H" (aber nicht "AB" und "IJ")
Es könnte viele tausend Kandidaten-Strings geben (in CAND), aber was noch wichtiger ist, ich werde diese Suche viele Millionen Mal durchführen, also muss es SCHNELL sein.
Ich würde gerne mit Char-Arrays arbeiten. Ich bin auch nicht an architektonischen Lösungen wie der Verteilung der Suche interessiert - nur an der effizientesten Funktion / dem effizientesten Algorithmus, um sie lokal auszuführen.
Außerdem sind alle Zeichenfolgen in CAND und INSTR relativ klein (<50 Zeichen) - d. H. Die Zielzeichenfolge INSTR ist im Verhältnis zu den Kandidatenzeichenfolgen NICHT lang.
Aktualisieren Ich hätte erwähnen sollen, dass die Menge der CAND-Zeichenfolgen über alle Werte von INSTR hinweg unveränderlich ist.
Aktualisieren Ich muss nur wissen, dass es ein Match gab - und ich muss nicht wissen, was das Match war.
Endgültiges Update Aufgrund der einfachen Implementierung habe ich mich für AhoCorsick und Rabin-Karp entschieden. Da ich Muster mit variabler Länge habe, habe ich einen modifizierten Rabin-Karp verwendet, der die ersten n Zeichen jedes Musters enthält, wobei n die Länge des kleinsten Musters ist und N dann die Länge meines fortlaufenden Teilstringsuchfensters. Für den Aho Corsick habe ich verwendetdiese
In meinem Test suchte ich nach 1000 Mustern in Zeitungsartikeln aus zwei Dokumenten, gemittelt über 1000 Iterationen usw. ... Normalisierte Zeiten für die Fertigstellung waren:
AhoCorsick: 1
RabinKarp: 1.8
Naive Suche (Überprüfen Sie jedes Muster und verwenden Sie string.contains): 50
* Einige Ressourcen, die die in den Antworten unten genannten Algen beschreiben:
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html
http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf