In der Informatik, Schnur-Suche-Algorithmen, hat manchmal Schnur genannt, die Algorithmen vergleicht, sind eine wichtige Klasse von Schnur-Algorithmen, die versuchen, einen Platz zu finden, wo eine oder mehrere Schnuren (auch genannt Muster) innerhalb einer größeren Schnur oder Textes gefunden werden.

Lassen Sie Σ ein Alphabet (begrenzter Satz) sein. Formell sind beide das Muster und der gesuchte Text Vektoren von Elementen von Σ. Der Σ kann ein übliches menschliches Alphabet (zum Beispiel, die Briefe A durch Z im lateinischen Alphabet) sein. Andere Anwendungen können binäres Alphabet (Σ = {0,1}) oder DNA-Alphabet (Σ = {A, C, G, T}) in bioinformatics verwenden.

In der Praxis, wie die Schnur verschlüsselt wird, kann die ausführbaren Schnur-Suchalgorithmen betreffen. Insbesondere, wenn eine variable Breite-Verschlüsselung im Gebrauch dann ist, ist es (Zeit langsam, die zu N proportional ist), um den N-ten Charakter zu finden. Das wird viele der fortgeschritteneren Suchalgorithmen bedeutsam verlangsamen. Eine mögliche Lösung ist, nach der Folge von Codeeinheiten statt dessen zu suchen, aber das Tun kann so falsche Matchs erzeugen, wenn die Verschlüsselung nicht spezifisch entworfen wird, um es zu vermeiden.

Grundlegende Klassifikation

Die verschiedenen Algorithmen können durch die Zahl von Mustern klassifiziert werden, die jeder verwendet.

Einzelne Muster-Algorithmen

Lassen Sie M die Länge des Musters sein und n die Länge des auffindbaren Textes sein zu lassen.

Asymptotische Zeiten werden mit O, Ω, und Θ Notation ausgedrückt

Der Schnur-Suchalgorithmus von Boyer-Moore ist der Standardabrisspunkt für die praktische Schnur-Suchliteratur gewesen.

Algorithmen mit dem begrenzten Satz von Mustern

• Aho-Corasick Schnur, die Algorithmus vergleicht
• Algorithmus von Commentz-Walter
• Schnur von Rabin-Karp sucht Algorithmus

Algorithmen mit der unendlichen Zahl von Mustern

Natürlich können die Muster nicht in diesem Fall aufgezählt werden. Sie werden gewöhnlich durch eine regelmäßige Grammatik oder regelmäßigen Ausdruck vertreten.

Andere Klassifikation

Andere Klassifikationsannäherungen sind möglich. Eine der allgemeinsten Gebrauch-Aufbereitung als Hauptkriterien.

Naive Schnur-Suche

Die einfachste und am wenigsten effiziente Weise zu sehen, wo eine Schnur in einem anderen vorkommt, soll jeden Platz überprüfen, der es eins nach dem anderen sein konnte, um zu sehen, ob es dort ist. So zuerst sehen wir, ob es eine Kopie der Nadel im ersten Charakter des Heuschobers gibt; wenn nicht, wir achten zu sehen, ob es eine Kopie der Nadel gibt, die am zweiten Charakter des Heuschobers anfängt; wenn nicht, wir sehen Start-auf den dritten Charakter und so weiter aus. Im normalen Fall müssen wir nur auf einen oder zwei Charaktere für jede falsche Position schauen zu sehen, dass es eine falsche Position ist, so im durchschnittlichen Fall nimmt das O (n + m) Schritte, wo n die Länge des Heuschobers ist und M die Länge der Nadel ist; aber im Grenzfall, nach einer Schnur wie "aaaab" in einer Schnur wie "aaaaaaaaab" suchend, nimmt es O (nm) Schritte.

Zustandsautomat hat Suche gestützt

In dieser Annäherung vermeiden wir denselben Weg zurückzuverfolgen, indem wir einen deterministischen begrenzten Automaten (DFA) bauen, der Schnuren anerkennt, die die gewünschte Suchschnur enthalten. Diese sind teuer, um zu bauen — sie werden gewöhnlich mit dem powerset Aufbau — aber sehr schnell geschaffen, um zu verwenden. Zum Beispiel erkennt der DFA gezeigt nach rechts das Wort "MAMI" an. Diese Annäherung wird oft in der Praxis verallgemeinert, um nach willkürlichen regelmäßigen Ausdrücken zu suchen.

Stummel

Knuth-Morris-Pratt schätzt einen DFA, der Eingänge mit der Schnur anerkennt, als eine Nachsilbe zu suchen, fängt Boyer-Moore an, vom Ende der Nadel zu suchen, so kann es gewöhnlich vorn eine ganze Nadel-Länge an jedem Schritt springen. Baeza-Yates geht das nach, ob die vorherigen j Charaktere ein Präfix der Suchschnur waren, und deshalb zur krausen Schnur-Suche anpassungsfähig ist. Der bitap Algorithmus ist eine Anwendung von Annäherung von Baeza-Yates.

Index-Methoden

Suchen Sie schneller Algorithmen basieren auf der Aufbereitung des Textes. Nach dem Gebäude eines Teilkette-Index, zum Beispiel ein Nachsilbe-Baum oder Nachsilbe-Reihe, können die Ereignisse eines Musters schnell gefunden werden. Als ein Beispiel kann ein Nachsilbe-Baum rechtzeitig gebaut werden, und alle Ereignisse eines Musters können rechtzeitig gefunden werden (wenn die Alphabet-Größe als eine Konstante angesehen wird).

Andere Varianten

Einige Suchmethoden, zum Beispiel trigram Suche, sind beabsichtigt, um eine "Nähe"-Kerbe zwischen der Suchschnur und dem Text aber nicht einem "Match/Nichtmatch" zu finden. Diese werden manchmal "krause" Suchen genannt.

• R. S. Boyer und J. S. Moore, Ein schneller Schnur-Suche-Algorithmus, Karambolage. ACM 20, (10), 262-272 (1977).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Kapitel 32: Das Schnur-Zusammenbringen, pp.906-932.

Links

• Riesige (aufrechterhaltene) Liste des Musters, das Verbindungen vergleicht
• StringSearch - Hochleistungsmuster, das Algorithmen in Java - Durchführungen von vielen Zusammenbringen-Algorithmen der Schnur in Java (BNDM, Boyer-Moore-Horspool, Boyer Moore Horspool Raita, Shift-Or) vergleicht
• Genaue Schnur, die Algorithmen — Zeichentrickfilm in Java, Detaillieren und C Durchführung von vielen Algorithmen Vergleicht.
• Boyer Moore Raita Thomas