Boyer-Moore-Algorithmus

Der Boyer-Moore-Algorithmus ist ein String-Matching-Algorithmus. Der Algorithmus wird dazu genutzt, um in einem Text T einen bestimmten Teiltext (Muster M) zu finden und wurde 1977 von Robert S. Boyer und J Strother Moore entwickelt.

Inhaltsverzeichnis

Algorithmus

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. In diesem Fall wird um eine Position nach rechts geschoben.
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.

Beispiele

Bad-Character-Heuristik

String: Hoola-Hoola girls like Hooligans

Suchmuster: Hooligan

Hoola-Hoola girls like Hooligans
Hooligan

Das letzte Zeichen stimmt nicht mit dem letzten des Suchmusters überein, also kann man das Suchmuster bis zum ersten „o“ (von hinten gelesen) verschieben:

Hoola-Hoola girls like Hooligans
Hooligan
     Hooligan
       Hooligan

Das „r“ im String kommt im Muster überhaupt nicht vor. Das ermöglicht das Verschieben um die komplette Länge des Suchstrings, da hier absolut ausgeschlossen ist, dass das Muster an einer Stelle matcht.

Hoola-Hoola girls like Hooligans
Hooligan
     Hooligan
       Hooligan
               Hooligan
                       Hooligan

Muster wurde gefunden.

Der Boyer-Moore-Algorithmus arbeitet am effizientesten, wenn er ein Zeichen vorfindet, das im Suchmuster nicht vorkommt. Die Bad-Character-Regel kommt dann zum Tragen. Dies ist sehr wahrscheinlich bei einem relativ kleinen Muster und einem großen Alphabet, was ihn für einen solchen Fall besonders geeignet macht. In diesem Fall arbeitet der Algorithmus mit einer Effizienz von O\left(\frac{n}{m}\right) Vergleichen, ansonsten besitzt dieser Algorithmus eine Komplexität von O\left(n + m\right).

Good-Suffix-Heuristik

String: reinesupersauersupesupersupe

Suchmuster: supersupe

reinesupersauersupesupersupe
supersupe

Nur die letzten 4 Buchstaben stimmen überein („supe“). Dieses Suffix kommt im Muster ganz am Anfang vor, also kann man das Muster bis dorthin verschieben:

reinesupersauersupesupersupe
     supersupe

Nur der letzte Buchstabe „e“ stimmt überein. Wir können das Muster bis zum nächsten Auftreten von „e“ in supersupe verschieben:

reinesupersauersupesupersupe
          supersupe

Nur die letzten Buchstaben „ersupe“ stimmen überein, welche an keiner anderen Stelle im Muster mehr auftreten. Allerdings tritt das Suffix „supe“ sowohl am Ende von „ersupe“ als auch am Anfang des Musters auf.

reinesupersauersupesupersupe
               supersupe

„e“ und „r“ stimmen nicht überein, wir verschieben um eine Position. Dieser Fall tritt mehrmals hintereinander auf:

reinesupersauersupesupersupe
                supersupe
reinesupersauersupesupersupe
                 supersupe
reinesupersauersupesupersupe
                  supersupe
reinesupersauersupesupersupe
                   supersupe

Muster wurde gefunden. Zusammen mit der „Bad-Character-Heuristik“ könnten die letzten 3 Iterationen übersprungen werden, da wir bis zum nächsten „r“ im Muster verschieben können.

Beispielcode in C

In der Praxis wendet der Algorithmus beide Regeln an und nutzt immer die Regel, die das Muster 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 „skip table“ und „next table“ im Code).

Im folgenden Quellcode geschieht das Anlegen der „Gute Regel“-Tabelle (next[]) im (unwahrscheinlichen) schlechtesten Fall in O\left(m^2\right), was bei nicht zu großen Mustern zu vernachlässigen 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 O\left(n + m^2\right).

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>
 
 
char * boyerMoore(char * p /* pattern */, char * s) {
 
    int plen = strlen(p), slen = strlen(s);
 
    if (plen > slen) {
        return NULL;
    }
 
    int skip[UCHAR_MAX+1];
    int i, j, k, * next;
 
    /* calc skip table („bad rule“) */
    for (i = 0; i <= UCHAR_MAX; i++) {
         skip[i] = plen;
    }
 
    for (i = 0; i < plen; i++) {
         skip[(unsigned char)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) {
                    break;
                }
                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++;
            } else {
                i += skip[(unsigned char)s[i - j]] > next[j] ? skip[(unsigned char)s[i - j]] - j : next[j];
                goto newi;
            }
        }
        free(next);
        return s + i - plen;
newi:
        ;
    }
    free(next);
    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;
}

Literatur

  • Robert S. Boyer; J Strother Moore : A fast string searching algorithm. CACM 20 (Issue 10): 762-772 (Onlineversion; PDF; 1.19 MB)
  • Robert S. Boyer, J Strother Moore: A Lemma Driven Automatic Theorem Prover for Recursive Function Theory. IJCAI 1977: 511-519 (Onlineversion; PDF; 240 KB)

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Knuth-Morris-Pratt — Der Knuth Morris Pratt Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Ronald Pratt benannt und ist ein String Matching Algorithmus. Seine asymptotische Laufzeit ist linear in der Länge des Musters (auch Suchbegriff,… …   Deutsch Wikipedia

  • String-Matching-Algorithmus — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Karp-Rabin-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • Knuth-Morris-Pratt-Algorithmus — Der Knuth Morris Pratt Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Ronald Pratt benannt und ist ein String Matching Algorithmus. Seine asymptotische Laufzeit ist linear in der Länge des Musters (auch Suchbegriff,… …   Deutsch Wikipedia

  • Rabin-Karp-Algorithmus — Der Rabin Karp Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von… …   Deutsch Wikipedia

  • String-Matching-Algorithmen — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • String Matching — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Suchmaske — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Textsuche — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. String Matching Algorithmen, etwa Zeichenketten Übereinstimmungs… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”