Ich habe versucht, Verschiebungsregeln im Boyer-Moore String-Suchalgorithmus zu verstehen, habe sie aber nicht verstanden. Ich lese hier auf wikipedia , aber das ist zu komplex!
Es wird sehr hilfreich sein, wenn jemand die Regel auf einfache Weise auflistet.
Im Boyer-Moore-Algorithmus beginnen Sie, Musterzeichen mit Textzeichen am Ende des Musters zu vergleichen. Wenn Sie eine Abweichung finden, haben Sie eine Konfiguration vom Typ
%Vor%Die schlechte Zeichenverschiebung bedeutet nun, dass das Muster so verschoben wird, dass das Textzeichen der Fehlanpassung mit dem letzten Vorkommen dieses Zeichens im Anfangsteil des Musters (Muster minus letztes Musterzeichen) übereinstimmt ), wenn es ein solches Vorkommen gibt, oder eine Position vor dem Muster, wenn das nicht übereinstimmende Zeichen überhaupt nicht im Anfangsteil des Musters erscheint.
Das könnte eine Verschiebung nach links sein, wenn die Situation
ist %Vor%so dass allein garantiert keinen Fortschritt.
Die andere Verschiebung, die gute Suffixverschiebung , richtet den übereinstimmenden Teil des Textes, m , mit dem rechten Vorkommen dieser Zeichenfolge im Muster aus, dem ein anderes Zeichen vorausgeht ( Wenn das übereinstimmende Suffix auch ein Präfix des Musters ist) als das übereinstimmende Suffix m des Musters - wenn es ein solches Vorkommen gibt.
Also zum Beispiel
%Vor% würde zu einer guten Suffixverschiebung von vier Positionen führen, da der gefundene Teil m = abcfabc in dem Muster vier Stellen vor dem Suffix-Vorkommen vorkommt und ihm dort ein anderes Zeichen vorangestellt ist ( x statt f ) als in der Suffix-Position.
Wenn das übereinstimmende Teil in dem Muster nicht vollständig vorkommt, dem ein anderes Zeichen als das Suffix vorangestellt ist, richtet die gute Suffixverschiebung ein Suffix des übereinstimmenden Teils des Textes mit einem Präfix des Musters aus, wobei maximale Überlappung gewählt wird. zB
%Vor%Die gute Suffix-Verschiebung verschiebt das Muster immer nach rechts, was den Fortschritt garantiert.
Dann werden bei jeder Nichtübereinstimmung die Fortschritte der schlechten Zeichenverschiebung und der guten Suffixverschiebung verglichen, und die größere wird gewählt. Es wird von Christian Charras und Thierry Lecroq, hier näher erläutert mit vielen anderen String-Suchalgorithmen.
Für das Beispiel, das Sie in den Kommentaren erwähnt haben,
%Vor% Das übereinstimmende Suffix ist MPLE und das nicht übereinstimmende Textzeichen ist I . Die schlechte Zeichenverschiebung sucht also nach dem letzten Vorkommen von I im Anfangsteil des Musters. Es gibt keine, so dass eine schlechte Zeichenverschiebung das Muster verschiebt, so dass das nicht übereinstimmende I eins vor dem Start des Musters ist
%Vor%
und die gute Suffix-Verschiebung sucht nach dem rechtshöchsten Vorkommen von MPLE im Muster nicht , dem ein A vorangestellt ist, oder dem längsten Suffix von MPLE , das ein Präfix des Musters ist . Es gibt kein vollständiges Auftreten des übereinstimmenden Teils in dem Muster vor dem Suffix, so dass das längste Suffix des übereinstimmenden Teils, das auch ein Präfix des Musters ist, die gute Suffixverschiebung bestimmt. In diesem Fall sind die zwei Suffixe des übereinstimmenden Teils, die Präfixe des Musters sind, die Einzelzeichenfolge E und die leere Zeichenfolge. Die längste ist offensichtlich die nichtleere Zeichenfolge, daher richtet die gute Suffixverschiebung das ein Zeichen umfassende Suffix E im übereinstimmenden Teil des Textes mit dem einstelligen Präfix des Musters
Die gute Suffixverschiebung verschiebt das Muster weiter nach rechts, so dass dies die gewählte Verschiebung ist.
Dann gibt es eine unmittelbare Nichtübereinstimmung an der letzten Musterposition, und dann richtet die schlechte Zeichenverschiebung die P im Text auf die P im Muster aus (und die gute Suffixverschiebung muss überhaupt nicht berücksichtigt werden, wenn die Nichtübereinstimmung tritt bei dem letzten Musterzeichen auf, da sie in diesem Fall niemals eine größere Verschiebung als die schlechte Zeichenverschiebung erzeugen würde.
Dann haben wir das komplette Spiel.
In der Variante mit dem Muster TXAMPLE findet die gute Suffixverschiebung heraus, dass kein nicht leeres Suffix des übereinstimmenden Teils ein Präfix des Musters ist (und das vollständig übereinstimmende Teil im Muster nicht vorangestellt von A ), so richtet die gute Suffixverschiebung das leere Suffix des übereinstimmenden Teils des Textes (die Grenze zwischen dem E und dem Leerzeichen) mit dem leeren Präfix des Musters (der Leerer String vor dem T ), was zu
(im nächsten Schritt werden die beiden L s durch die schlechte Zeichenverschiebung ausgerichtet und die nächste Fehlanpassung im nachfolgenden Schritt tritt bei der anfänglichen T des Musters auf).
Es gibt eine gute Visualisierung hier.
(BEARBEITEN: Es gibt auch eine sehr gute Erklärung mit beiden Beispielen und einem Beispiel, wie man die Vorverarbeitungsschritte implementiert. hier .)
Allgemeine Regeln:
Was ich gerade beschrieben habe, ist die Regel "Schlechtes Zeichen". Die Regel "Good Suffix" bietet eine weitere Möglichkeit zum Verschieben; Was auch immer weiter geht, ist derjenige, den Sie nehmen sollten. Es ist durchaus möglich, den Algorithmus ohne die Regel für gute Suffixe zu implementieren, aber es wird weniger effizient sein, sobald die Indizes aufgebaut sind.
Die Good-Suffix-Regel erfordert, dass Sie auch wissen, wo die einzelnen Teilzeichenfolgen mit mehreren Zeichen des Musters zu finden sind. Wenn Sie eine Nichtübereinstimmung treffen (wie immer von rechts nach links), verschiebt die Verschiebung mit gutem Suffix das Muster zu einem Punkt, an dem die Buchstaben, die schon gefunden haben, wieder übereinstimmen. Wenn das übereinstimmende Teil im Muster eindeutig ist, wissen Sie, dass Sie den ganzen Weg überspringen können, denn wenn es nicht zusammenpasst, wenn es mit dem einzigen Vorkommen übereinstimmt, kann es unmöglich mit einem übereinstimmen anderer Teil des Musters.
Betrachten wir zum Beispiel die folgende Situation:
Ich habe hier zwei Möglichkeiten:
und ich sollte nehmen, was immer ich weiter verschieben kann.
Wenn Sie immer noch verwirrt sind, versuchen Sie eine spezifischere Frage zu stellen; es ist schwer klar zu sein, wenn wir nicht wissen, wo du feststeckst.
Es gibt zwei Heuristiken: Bat-Symbol-Heuristik und gute Muster-Heuristik.
Zuerst wissen Sie, Nadel Vergleich beginnt von seinem Ende. Also, wenn Zeichen passen nicht Nadel verschoben so zumindest Vergleich Charakter im Heuhaufen würde Nadel passen. Z.B. Die Nadel ist "ABRACADABRA", und der aktuelle Charakter im Heuhaufen ist "B" und passt nicht zum letzten "A" und entspricht auch nicht dem vorherigen "R", also ist eine Verschiebung um eins sinnlos, es wird keine Übereinstimmung geben. Aber "B" entspricht dem 2ten vom Endezeichen in der Nadel. Also würden wir die Nadel um mindestens 2 Positionen verschieben. Wenn der aktuelle Charakter im Heuhaufen mit keiner Nadel übereinstimmt, muss die Nadel über das aktuelle Zeichen hinaus verschoben werden. Mit anderen Worten, wir verschieben das Muster, bis das aktuelle Zeichen im Heuhaufen dem Zeichen in der Nadel entspricht, oder die ganze Nadel wird verschoben.
Der Betrag der Verschiebung wird berechnet und in einem Array gespeichert. Für "ABRACADABRA" wäre das: ['R'] = 1, ['B'] = 2, ['D'] = 4, usw.
%Vor%Zweitens, wenn gefunden gefunden für mindestens "ABRA" im Heuhaufen (aber keine vollständige Übereinstimmung) Nadel kann verschoben werden, so dass nächste "ABRA" wird übereinstimmen.
Der Betrag der Verschiebung für den angepassten Teil wird ebenfalls vorberechnet: e. G. ['A'] = 3, ['RA'] = 11, ['BRA'] = 11, ['ABRA'] = 7, ['DABRA'] = 7 ...
%Vor%Dies ist keine vollständige Erklärung aller Eckfälle, sondern die Grundidee des Algorithmus.
Tags und Links algorithm string-search boyer-moore