Boyer-Moore-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Boyer-Moore-Algorithmus ist ein String-Matching-Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text einen bestimmten Teiltext (Muster) zu finden und wurde 1977 von Bob Boyer und J Strother Moore entwickelt.
Das Muster wird am Anfang linksbündig unter den Text geschrieben und dann von rechts nach links Zeichen für Zeichen mit dem Text verglichen. Sobald ein Mismatch auftritt, berechnen zwei Heuristiken wie weit das Suchmuster nach rechts verschoben werden kann.
"Bad-Character-Heuristik": Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes überein ("Bad-Character"), wird im Muster nach dem letzten Vorkommen dieses Bad-Characters gesucht und das Muster soweit verschoben, bis beide Buchstaben übereinander liegen. Existiert dieser Bad-Character nicht im Muster wird das Muster um seine volle Länge nach rechts verschoben. Es kann vorkommen, dass die Bad-Character-Heuristik eine Verschiebung des Musters nach links vorschlägt.
"Good-Suffix-Heuristik": Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Suffix des Musters mit dem Text überein und tritt danach aber ein Mismatch auf, wird das Muster soweit nach rechts geschoben, bis ein Teilwort des Musters wieder auf das Suffix passt. Existiert das Suffix kein zweites Mal im Muster, wird das Muster um seine volle Länge nach rechts verschoben.
Es kommt vor, dass die beiden Heuristiken unterschiedliche Verschiebungen berechnen. Der Algorithmus wählt immer das Maximum der beiden Vorschläge, um das Muster nach rechts zu verschieben.
Um das Vorgehen effizient zu gestalten, wird für beide Heuristiken in einem Vorverarbeitungsschritt jeweils eine Sprungtabelle errechnet. Die Sprungtabelle für die Bad-Character-Heuristik enthält für jedes im Suchmuster vorkommende Zeichen den Abstand von der Position des letzten Vorkommens im Suchmuster bis zum Ende des Suchmusters. Die Tabelle für die Good-Suffix-Heuristik enthält für jedes Teilmuster (von hinten aus gesehen) den Abstand vom Ende des Musters, ab dem es wieder im Muster vorkommt. Eine detailliertere Beschreibung des Algorithmus findet sich im entsprechenden Artikel in der englischen Wikipedia.
Inhaltsverzeichnis |
[Bearbeiten] Beispiel "Bad-Character-Heuristik"
String: Hoola-Hoola girls like Hooligans
Suchpattern: Hooligan
Hoola-Hoola girls like Hooligans Hooligan
Das letzte Zeichen stimmt nicht mit dem letzten des Suchpatterns überein, also kann man das Suchpattern bis zum ersten "o" (von hinten gelesen) verschieben:
Hoola-Hoola girls like Hooligans
Hooligan
Hooligan
Hooligan
Das "r" im String kommt im Pattern überhaupt nicht vor. Das ermöglicht das Verschieben um die komplette Länge des Suchstrings, da hier absolut ausgeschlossen ist, dass das Pattern an einer Stelle matcht.
Hoola-Hoola girls like Hooligans Hooligan Hooligan Hooligan Hooligan Hooligan
gefunden.
[Bearbeiten] Beispiel "Good-Suffix-Heuristik"
String: reinesupersauersupesupersupe
Suchpattern: supersupe
reinesupersauersupesupersupe supersupe
Nur die letzten 4 Buchstaben stimmen überein ("supe"), dieses Suffix kommt im Pattern ganz am Anfang vor, also können das Pattern bis dorthin verschieben:
reinesupersauersupesupersupe
supersupe
Nur der letzte Buchstabe "e" stimmt überein, wir können das Pattern bis zum nächsten Auftreten von "e" in supersupe verschieben:
reinesupersauersupesupersupe
supersupe
Nur die letzten Buchstaben "ersupe" stimmen überein, was an keiner anderen Stelle im Pattern mehr auftritt. Allerdings tritt "supe" sowohl am Ende von "ersupe" und am Anfang des Pattern's auf.
reinesupersauersupesupersupe
supersupe
"e" und "r" stimmen nicht überein, wir verschieben bis zu nächstren "r"
reinesupersauersupesupersupe
supersupe
gefunden.
In der Praxis wendet der Algorithmus beide Regeln an und nutzt immer die Regel, die das Pattern am weitesten springen lässt, für die "Gute Regel" sowie für die "Schlechte Regel" erstellt man zu Beginn der Suche jeweils eine Sprungtabelle (siehe Beispielcode).
Es ist leicht zu sehen, dass der Boyer-Moore-Algorithmus am effizientesten arbeitet, wenn er ein Zeichen vorfindet, das im Suchpattern überhaupt nicht vorkommt. Dies ist sehr wahrscheinlich bei einem relativ kleinen Pattern und einem grossen Alphabet, was ihn für einen solchen Fall besonders geeignet macht. In diesem Fall arbeitet der Algorithmus mit einer Effizienz von 
Vergleichen, ansonsten besitzt dieser Algorithmus eine Komplexität von 
.
[Bearbeiten] Beispielcode in C
Wer genau hinschaut sieht, dass im folgenden Quellcode das anlegen der "Gute Regel"-Tabelle (next[]) hier im (unwahrscheinlichen) schlechtesten Fall in 
geschieht, was bei nicht zu grossen Patterns vernachlässigbar ist. Die Suche nach dem Suffix für die "Schlechte Regel"-Tabelle lässt sich beispielsweise über den KMP-Algorithmus machen, was hier aber der Übersichtlichkeit wegen vermieden wird. Damit liegt folgender Algorithmus in 
.
Lässt man sich die Anzahl der benötigten Vergleiche ausgeben, so sind dies bei einem großen Alphabet erstaunlich wenige und der Boyer-Moore Algorithmus ist beispielsweise dem Knuth-Morris-Pratt-Algorithmus vorzuziehen.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int skip[UCHAR_MAX];
char * boyerMoore(char * p /* pattern */, char * s) {
int i, j, k;
int plen = strlen(p), slen = strlen(s);
int * next;
if (plen > slen) return NULL;
/* calc skip table ("bad rule") */
for (i = 0; i <= UCHAR_MAX; i++) skip[i] = plen;
for (i = 0; i < plen; i++) skip[(int)p[i]] = plen - i - 1;
/* calc next table ("good rule") */
next = (int*)malloc((plen+1) * sizeof(int));
for (j = 0; j <= plen; j++) {
for (i = plen - 1; i >= 1; i--) {
for (k = 1; k <= j; k++) {
if (i - k < 0) goto matched;
if (p[plen - k] != p[i - k]) goto nexttry;
}
goto matched;
nexttry: ;
}
matched: next[j] = plen - i;
}
plen--;
i = plen; /* position of last p letter in s */
while (i < slen) {
j = 0; /* matched letter count */
while (j <= plen) {
if (s[i - j] == p[plen - j]) {
j++;
continue;
}
i += skip[(int)s[i - j]] > next[j] ? skip[(int)s[i - j]] : next[j];
goto newi;
}
return s + i - plen;
newi: ;
}
return NULL;
}
int main() {
char * s = "ababbbcabaabbbabababbbababbba";
char * p = "ababbba";
char * found = boyerMoore(p,s);
while (found != NULL) {
printf("%.7s found @ position %d\n", found, found - s + 1);
found = boyerMoore(p,found + 1);
}
return 0;
}
[Bearbeiten] Literatur
- Robert S. Boyer, J. Strother Moore: A Lemma Driven Automatic Theorem Prover for Recursive Function Theory. IJCAI 1977: 511-519
