Boyer-Moore-Algorithmus

FONT SIZE:
fontsize_dec
fontsize_inc
Januar 5, 2017 Liam Assmann B 0 11

In der Informatik ist die Boyer-Moore-Algorithmus eine effiziente String-Suchalgorithmus, der die Standard-Benchmark für die praktische String-Suche Literatur. Es wurde von Robert S. Boyer und J Strother Moore 1977. Der Algorithmus vorverarbeitet die Zeichenkette gesucht wird, aber nicht die Zeichenkette in gesucht entwickelt. Es ist somit für Anwendungen, bei denen das Muster ist viel kürzer als der Text gut geeignet oder hat über mehrere Suchanfragen bestehen bleiben. Der Boyer-Moore-Algorithmus verwendet Informationen, die während der Vorverarbeitung Schritt versammelt, um Abschnitte des Textes zu springen, was zu einer niedrigeren konstanten Faktor als viele andere String-Algorithmen. Im allgemeinen läuft der Algorithmus schneller zunehmender Musterlänge. Das Hauptmerkmal des Algorithmus ist es, auf den Schwanz des Musters anstatt den Kopf passen, und entlang der Text in Sprüngen von mehreren Zeichen überspringen anstatt nach jedes einzelne Zeichen im Text.

Begriffsbestimmungen

Ausrichtungen Muster PAN in Text Anpanman von k = 3 bis k = 8. Eine Übereinstimmung tritt bei k = 5.
  • S bezieht sich auf die Zeichen an der Index i der String S, gerechnet ab 1.
  • S bezieht sich auf den Teilstring von String S ab Index i und endend bei j, inclusive.
  • Ein Präfix von S eine Teil S für ein i in Reihe, wobei n die Länge von S.
  • Das Suffix s eine Teil S für ein i in Reihe, wobei n die Länge von S.
  • Die Zeichenfolge, die für das Muster genannt durchsucht und auf mit dem Symbol P bezeichnet
  • Die Zeichenfolge, die in der Text aufgerufen gesucht und wird mit dem Symbol T. bezeichnet
  • Die Länge von P n ist.
  • Die Länge des T m ist.
  • Eine Ausrichtung der P nach T ist ein Index k in T, so daß das letzte Zeichen des P mit Index k von T. flucht
  • Eine Übereinstimmung oder Auftreten von P erfolgt bei einer Ausrichtung, wenn P entspricht T.

Bezeichnung

Die Boyer-Moore-Algorithmus sucht nach Vorkommen von P in T durch Ausführen einer expliziten Zeichenvergleiche bei verschiedenen Ausrichtungen. Statt einer Brute-Force-Suche aller Ausrichtungen, verwendet Boyer-Moore-Informationen durch Vorverarbeitung P, um so viele wie möglich Ausrichtungen überspringen gewonnen.

Vor der Einführung dieses Algorithmus, der übliche Weg, im Text zu suchen war, um jedes Zeichen des Textes für das erste Zeichen des Musters zu überprüfen. Sobald diese gefunden wurde, die nachfolgenden Zeichen des Textes würde, um die Zeichen des Musters verglichen werden. Wenn keine Übereinstimmung aufgetreten ist dann der Text wieder Zeichen für Zeichen in dem Bemühen, eine Übereinstimmung zu finden überprüft werden. Somit fast jedes Zeichen im Text geprüft werden muss. Die wichtige Erkenntnis in diesem Algorithmus ist, dass, wenn das Ende des Musters wird dem Text verglichen springt dann entlang der Text anstatt zu prüfen, jedes Zeichen des Textes durchgeführt werden. Der Grund, dass dies funktioniert, ist, dass beim Ausrichten der Muster mit dem Text, das letzte Zeichen des Musters wird auf das Zeichen in dem Text verglichen. Wenn die Zeichen nicht übereinstimmen gibt es keine Notwendigkeit, um die Suche nach hinten entlang des Musters. Wenn das Zeichen in dem Text keine der Figuren in dem Muster übereinstimmt, wird das nächste Zeichen zu überprüfen, in der Text n Zeichen weiter entlang des Textes, wobei n die Länge des Musters befindet. Wenn das Zeichen im Muster dann eine partielle Verschiebung des Musters entlang der Text durchgeführt wird, um entlang der passenden Zeichenzeile und der Vorgang wird wiederholt. Die Bewegung entlang der Text in springt Vergleiche anstatt zu prüfen, jedes Zeichen in der Text verringert die Anzahl der Vergleiche, die getroffen werden müssen, die der Schlüssel für die Erhöhung der Effizienz des Algorithmus zu machen.

Formal beginnt der Algorithmus bei Ausrichten k = n, so dass der Beginn der P wird mit dem Start der Zeichen im T. P und T ausgerichtet werden dann verglichen, starten bei Index n in P und K T, Rückwärtsbewegung: die Saiten vom Ende P zum Anfang des P. Die Vergleiche fortzusetzen, bis entweder der Anfang P erreicht wird oder eine Nichtübereinstimmung auftritt, auf der die Ausrichtung nach rechts entsprechend dem maximalen Wert, der durch eine Reihe von Regeln erlaubt verschoben abgestimmt. Die Vergleiche werden wieder in der neuen Ausrichtung durchgeführt wird, und der Prozess wird wiederholt, bis die Ausrichtung über das Ende T, das heisst keine weiteren Übereinstimmungen gefunden werden, verschoben wird.

Die Schaltregeln werden als konstante Zeittabellensuchvorgänge durchgeführt, unter Verwendung von Tabellen während der Vorverarbeitung von P. erzeugt

Umschalt-Regeln

Die schlechten Charakter Regel und die Gutes-Ende-Regel: Eine Verschiebung wird durch die Anwendung sowohl Regeln berechnet. Die eigentliche Verschiebung versetzt ist das Maximum der durch diese Regeln berechneten Verschiebungen.

Das Bad Character Rule

Bezeichnung

Demonstration der schlechten Charakter Regel mit Muster NNAAMAN.

Die schlechte Zeichen der Regel betrachtet die Zeichen in T, bei der die Vergleichsprozess gescheitert. Das nächste Auftreten dieses Zeichen links in P gefunden wird, und eine Verschiebung, die diese Vorkommen im Einklang mit der übereinstimmende Vorkommen in T bringt vorgeschlagen. Wenn die übereinstimmende Zeichen nicht nach links in P auftreten, wird eine Verschiebung vorgeschlagen, dass die Gesamtheit von P über den Punkt der Fehlanpassung bewegt.

Vorverarbeitung

Methoden unterscheiden sich von der genauen Form der Tisch für den schlechten Charakter Regel eingeleitet werden soll, sondern eine einfache Konstantzeit-Lookup-Lösung ist wie folgt: ein 2D-Tabelle, die zuerst von der Index des Zeichens c im Alphabet durch die indiziert ist und die zweite erstellen Index i in dem Muster. Diese Suche wird das Auftreten von c in P mit der nächsthöheren Index j & lt zurückkehren; i oder -1, wenn es kein solches Ereignis. Die vorgeschlagene Verschiebung wird dann i - j, mit O-Lookup-Zeit und O-Raum, unter der Annahme einer endlichen Alphabet der Länge k.

The Good Suffixregel

Bezeichnung

Demonstration des guten Suffixregel mit Muster ANAMPNAM.

Die gute Suffixregel deutlich komplexere sowohl in Konzept und Umsetzung als die schlechten Charakter Regel. Es ist der Grund Vergleiche am Ende des Musters anstatt vorne beginnen, und ist formal somit feststellen:

Vorverarbeitung

Die gute Suffixregel erfordert zwei Tabellen: eine für die Verwendung in den allgemeinen Fall, und eine andere für den Einsatz, wenn entweder der allgemeine Fall lieferte keine sinnvollen Ergebnis oder eine Übereinstimmung auftritt. Diese Tabellen werden jeweils bezeichnet werden L und H. Ihre Definitionen sind wie folgt:

Beide Tische sind konstruierbar in O Zeit und Einsatz O-Raum. Die Ausrichtungsverschiebung für den Index i in P gegeben durch n - L oder N - H H sollte nur verwendet werden, wenn L Null oder eine Übereinstimmung festgestellt worden ist.

Der Galil Rule

Eine einfache, aber wichtige Optimierung der Boyer-Moore wurde weiter von Galil 1979 legte Wie zu verschieben, die Regelangebote Galil mit Beschleunigung der Ist-Vergleiche in jeder Ausrichtung durch Überspringen von Abschnitten, die dafür bekannt sind, entsprechen getan entgegengesetzt. Angenommen, bei einer Ausrichtung k1, P mit T nach unten auf das Zeichen c von T verglichen Dann, wenn P verschoben K2, so daß sein linkes Ende ist zwischen c und k1, in der nächsten Vergleichsphase ein Präfix P müssen die Teil überein T. Wenn also die Vergleiche uns an die Position von T k1, ein Auftreten von P können, ohne explizit den Vergleich Vergangenheit k1 aufgezeichnet werden. Zusätzlich zur Erhöhung der Effizienz des Boyer-Moore, die Galil Regel erweist linearen Zeitausführung im schlimmsten Fall nicht erforderlich.

Leistung

Der Boyer-Moore-Algorithmus, wie in der Originalarbeit vorgestellt hat Worst-Case-Laufzeit O, wenn das Muster nicht im Text erscheinen. Dies wurde zuerst von Knuth, Morris und Pratt 1977 nachgewiesen, gefolgt von Guibas und Odlyzko 1980 mit einer oberen Grenze von 5 m Vergleiche im schlimmsten Fall. Richard Cole gab einen Nachweis mit einer oberen Grenze von 3 m Vergleiche im schlechtesten Fall 1991.

Wenn das Muster sich in dem Text auftreten, Laufzeit des ursprünglichen Algorithmus O im schlimmsten Fall. Dies ist leicht zu sehen, wenn beide Muster und der Text nur aus der gleichen wiederholten Zeichen bestehen. Allerdings Einbeziehung der Galil Regel Ergebnisse in linearen Laufzeit in allen Fällen.

Implementierungen

Verschiedenen Implementierungen existieren in verschiedenen Programmiersprachen. In C ++ bietet steigern die allgemeine Boyer-Moore-Such Umsetzung im Rahmen des Algorithm Bibliothek.

Unten sind ein paar einfache Implementierungen.

Varianten

Der Boyer-Moore-Horspool Algorithmus ist eine Vereinfachung des Boyer-Moore-Algorithmus nur mit dem schlechten Charakter Regel.

Die Apostolico-Giancarlo Algorithmus beschleunigt den Prozess der Überprüfung, ob eine Übereinstimmung bei der gegebenen Ausrichtung durch Überspringen explizite Zeichenvergleiche aufgetreten. Diese nutzt Informationen, die während der Vorverarbeitung des Musters in Verbindung mit Suffix Einstimmungslängen bei jedem Spiel Versuch aufgezeichnet aufgelesen. Speichern Suffix Einstimmungslängen erfordert eine zusätzliche Tabelle gleich groß, um den Text gesucht.

(0)
(0)
Kommentare - 0
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha