Textsuche

Boyer-Moore-Algorithmus

 Inhalt  English version  aufwärts

Idee

Der Algorithmus von Boyer und Moore [BM 77] vergleicht das Muster von rechts nach links mit dem Text. Ist bereits das erste verglichene Textzeichen ein Zeichen, das im Muster überhaupt nicht vorkommt, so kann das Muster um m Positionen hinter dieses Zeichen weiter­geschoben werden. Das folgende Beispiel verdeutlicht diese Situation.

Beispiel:  

0123456789...
abbadabacba
babac
babac

Der erste Vergleich d-c an Position 4 liefert einen Mismatch. Das Textzeichen d kommt im Muster überhaupt nicht vor. Daher kann das Muster an keiner der Positionen 0, ..., 4 über­einstimmen, denn alle zugehörigen Fenster enthalten das d. Das Muster kann bis Position 5 weiter­geschoben werden.

Der günstigste Fall für den Boyer-Moore-Algorithmus tritt also ein, wenn jedesmal beim ersten Vergleich ein Textzeichen gefunden wird, das im Muster nicht vorkommt. Dann benötigt der Algorithmus nur O(n/m) Vergleiche.

 

Schlechtes-Zeichen-Strategie

Die eben beschriebene Vorgehensweise wird als Schlechtes-Zeichen-Strategie (bad character heuristics) bezeichnet. Sie kann auch angewendet werden, wenn das gefundene Zeichen zwar schlecht ist, also zu einem Mismatch führt, aber an anderer Stelle im Muster vorkommt. Dann allerdings kann das Muster nur so weit geschoben werden, bis dieses Vorkommen auf das Textzeichen ausgerichtet ist. Im nächsten Beispiel tritt diese Situation auf.

Beispiel:  

0123456789...
abbababacba
babac
babac

Der Vergleich b-c liefert einen Mismatch. Das Textzeichen b kommt im Muster an Position 0 und an Position 2 vor. Das Muster kann so weit geschoben werden, dass das letzte b des Musters auf das Textzeichen b ausgerichtet ist, also bis Position 2.

 

Gutes-Ende-Strategie

Nicht immer liefert die Schlechtes-Zeichen-Strategie ein gutes Ergebnis. In folgender Situation hat der Vergleich a-b einen Mismatch ergeben. Eine Ausrichtung des letzten Vorkommens des a im Muster auf das a im Text würde eine negative Verschiebung ergeben. Man könnte sich so behelfen, dass man stattdessen um 1 schiebt. Besser ist es, in diesem Fall die größtmögliche Schiebedistanz aus der Struktur des Musters abzuleiten. Die Schiebedistanz richtet sich danach, ob das Suffix, das über­ein­gestimmt hat, noch an anderer Stelle im Muster vorkommt. Diese Vorgehensweise heißt Gutes-Ende-Strategie (good suffix heuristics).

Beispiel:  

0123456789...
abaababacba
cabab
cabab

Das Suffix ab hat bereits über­ein­gestimmt. Das Muster kann so weit geschoben werden, bis das nächste Vorkommen von ab im Muster auf die Textzeichen ab ausgerichtet ist, also bis Position 2.

In folgender Situation hat das Suffix ab bereits über­ein­gestimmt. Es gibt im Muster kein weiteres Vorkommen von ab. Daher kann das Muster hinter das ab geschoben werden, also bis Position 5.

Beispiel:  

0123456789...
abcababacba
cbaab
cbaab

In folgender Situation hat das Suffix bab über­ein­gestimmt. Es gibt im Muster kein weiteres Vorkommen von bab. Aber in diesem Fall kann das Muster nicht wie eben an Position 5 geschoben werden, sondern nur bis Position 3, da ein Präfix des Musters (ab) mit einem Teil des über­einstimmenden Suffixes bab über­einstimmt. Wir bezeichnen diese Situation als Fall 2 der Gutes-Ende-Strategie.

Beispiel:  

0123456789...
aabababacba
abbab
abbab

Das Muster wird jeweils um die längere der beiden Distanzen geschoben, die sich aus der Gutes-Ende- bzw. der Schlechtes-Zeichen-Strategie ergeben.

 

Vorlauf für die Schlechtes-Zeichen-Strategie

Für die Schlechtes-Zeichen-Strategie wird eine Funktion occ benötigt, die für jedes Alphabet­zeichen die Position seines letzten Vorkommens im Muster liefert, bzw. -1, falls das Zeichen im Muster überhaupt nicht vorkommt.

Definition:  Sei A das zugrunde liegende Alphabet.

Die Occurrence-Funktion  occ : A*kreuzA Pfeil ganze Zahlen  ist wie folgt definiert:

Sei p Element A* mit  p = p0 ... pm-1  das Muster und  a Element A ein Alphabet­zeichen. Dann ist

occ(p, a)  =  max{ j  |  pj = a}.

Hierbei wird max(leere Menge) = -1 gesetzt.

Beispiel:   

Das letzte Vorkommen des Zeichens x in dem Wort text ist an Position 2. Das Zeichen t kommt an den Positionen 0 und 3 vor; das letzte Vorkommen ist an Position 3.

Die Occurrence-Funktion für ein bestimmtes Muster p wird in einem Array occ gespeichert, das durch die Alphabet­zeichen indiziert wird. Für jedes Zeichen a Element A enthält occ[a] den entsprechenden Funktionswert occ(p, a).

Folgende Funktion bmInitocc berechnet zu gegebenem Muster p die Occurrence-Funktion.

 

Vorlauf für die Schlechtes-Zeichen-Strategie
void bmInitocc()
{
    int j;
    char a;

    for (a=0; a<alphabetsize; a++)
        occ[a]=-1;

    for (j=0; j<m; j++)
    {
        a=p[j];
        occ[a]=j;
    }
}

 

Es ist in Java möglich, das Array occ durch a vom Typ char zu indizieren, da char ohne explizite Konversion in int umgewandelt wird.

 

Vorlauf für die Gutes-Ende-Strategie

Für die Gutes-Ende-Strategie wird ein Array s benötigt, das für jedes i angibt, um wie viel das Muster geschoben werden kann, wenn ein Mismatch an Position i-1 auftritt, d.h. wenn das an Position i beginnende Suffix über­ein­gestimmt hat. Um diese Schiebedistanz zu bestimmen, sind zwei unter­schied­liche Fälle zu betrachten.

Fall 1:   Das über­einstimmende Suffix kommt noch an anderer Stelle im Muster vor (Bild 1).

Fall 2:   Nur ein Teil des über­einstimmenden Suffixes kommt am Anfang des Musters vor (Bild 2).

Das übereinstimmende Suffix (grau) kommt noch an anderer Stelle im Muster vor
Bild 1:  Das über­einstimmende Suffix (grau) kommt noch an anderer Stelle im Muster vor

 

Ein Teil des übereinstimmenden Suffixes kommt am Anfang des Musters vor
Bild 2:  Ein Teil des über­einstimmenden Suffixes kommt am Anfang des Musters vor
Fall 1:

Die Situation ist ähnlich wie beim Knuth-Morris-Pratt-Vorlauf. Das über­einstimmende Suffix stellt einen Rand eines Suffixes des Musters dar. Zu jedem Suffix des Musters sind also die Ränder zu bestimmen. Benötigt wird jedoch die inverse Zuordnung zwischen einem gegebenen Rand und dem kürzesten Suffix des Musters, das diesen Rand hat.

Zusätzlich ist noch gefordert, dass der Rand sich nicht nach links fortsetzen lässt, denn dann würde es nach Verschiebung des Musters zu einem erneuten Mismatch kommen.

In folgendem ersten Teil des Vorlauf­algorithmus wird ein Array f berechnet. Für ein an Position i beginnendes Suffix des Musters enthält der Eintrag f[i] die Anfangs­position seines breitesten Randes. Für das Suffix ε, das an Position m beginnt, wird f[m] = m+1 gesetzt.

Genau wie beim Knuth-Morris-Pratt-Vorlauf wird ein Rand berechnet, indem geprüft wird, ob sich ein schon berechneter kürzerer Rand fortsetzen lässt.

Interessant ist hier wiederum auch der Fall, wenn sich ein Rand nicht fortsetzen lässt, denn dies bedeutet eine aussichts­reiche Verschiebung des Musters bei einem Mismatch. Es wird daher die zugehörige Schiebedistanz in ein Array s eingetragen – vorausgesetzt, dass der entsprechende Eintrag nicht schon belegt ist (dies ist dann der Fall, wenn ein kürzeres Suffix schon denselben Rand hatte).

 

Vorlauf für die Gutes-Ende-Strategie Fall 1
void bmPreprocess1()
{
    int i=m, j=m+1;
    f[i]=j;
    while (i>0)
    {
        while (j<=m && p[i-1]!=p[j-1])
        {
            if (s[j]==0) s[j]=j-i;
            j=f[j];
        }
        i--; j--;
        f[i]=j;
    }
}

 

Eine Visualisierung der Ausführung dieses Algorithmus steht in [3] zur Verfügung. Das folgende Beispiel zeigt die Belegung für das Array f und die bis hierhin berechneten Einträge im Array s.

Beispiel:  

i:01234567
p:abbabab
f:56456778
s:00002041

Das an Position 2 beginnende Suffix babab hat als breitesten Rand bab, dieser beginnt an Position 4. Daher ist f[2] = 4. Das an Position 5 beginnende Suffix ab hat als breitesten Rand ε, dieser beginnt an Position 7. Daher ist f[5] = 7.

Für die Belegung des Arrays s sind die Ränder maßgebend, die sich nicht nach links fortsetzen lassen.

Das an Position 2 beginnende Suffix babab hat den Rand bab, dieser beginnt an Position 4. Dieser Rand lässt sich nicht fortsetzen, denn es ist p[1]ungleichp[3]. Die Differenz 4 – 2 = 2 ist daher die Schiebedistanz, wenn bab über­ein­gestimmt hat und dann ein Mismatch auftritt. Somit ist s[4] = 2.

Das an Position 2 beginnende Suffix babab hat auch noch den Rand b, dieser beginnt an Position 6. Auch dieser Rand lässt sich nicht fortsetzen. Daher wird die Schiebedistanz 6 – 2 = 4 an Position 6 eingetragen.

Der Eintrag s[7] = 1 kommt zustande, weil das an Position 6 beginnende Suffix b den an Position 7 beginnenden Rand ε hat und sich dieser nicht fortsetzen lässt.

Fall 2:

Der Eintrag f[0] enthält die Anfangs­position des breitesten Randes des ganzen Musters. In obigem Beispiel also 5, da der Rand ab an Position 5 beginnt. Tritt das "gute Ende", also das über­einstimmende Suffix des Musters nicht an anderer Stelle im Muster auf, wie eben in Fall 1 dargestellt, so kann das Muster so weit geschoben werden, wie es sein Rand zulässt. Maßgebend ist dabei jeweils der breiteste Rand, sofern er nicht breiter als das über­einstimmende Suffix ist.

Im folgenden zweiten Teil des Vorlauf­algorithmus werden alle noch freien Einträge des Arrays s belegt. Eingetragen wird zunächst überall die Anfangs­position des breitesten Randes des Musters, diese ist j = f[0]. Ab Position i = j wird auf den nächst­schmaleren Rand f[j] umgeschaltet usw.

Vorlauf für die Gutes-Ende-Strategie Fall 2
void bmPreprocess2()
{
    int i, j;
    j=f[0];
    for (i=0; i<=m; i++)
    {
        if (s[i]==0) s[i]=j;
        if (i==j) j=f[j];
    }
}

 

Eine Visualisierung der Ausführung dieses Algorithmus steht in [3] zur Verfügung. Folgendes Beispiel zeigt die endgültige Belegung des Arrays s.

Beispiel:  

i:01234567
p:abbabab
f:56456778
s:55552541

Der gesamte Vorlauf­algorithmus des Boyer-Moore-Verfahrens besteht aus der Berechnung der Occurrence-Funktion und den beiden eben betrachteten Teilen.

Boyer-Moore-Vorlauf
void bmPreprocess()
{
    int[] f=new int[m+1];
    bmInitocc();
    bmPreprocess1();
    bmPreprocess2();
}

 

Such­algorithmus

Der Such­algorithmus vergleicht die Zeichen des Musters von rechts nach links mit dem Text. Bei vollständiger Über­ein­stimmung wird das Muster anschließend so weit geschoben, wie es sein Rand zulässt. Nach einem Mismatch wird das Muster um das Maximum der Werte geschoben, die sich aus der Gutes-Ende- und der Schlechtes-Zeichen-Strategie ergeben.

 

Boyer-Moore-Such­algorithmus
void bmSearch()
{
    int i=0, j;
    while (i<=n-m)
    {
        j=m-1;
        while (j>=0 && p[j]==t[i+j]) j--;
        if (j<0)
        {
            report(i);
            i+=s[0];
        }
        else 
            i+=Math.max(s[j+1], j-occ[t[i+j]]);
    }
}

 

Analyse

Unter der Bedingung, dass das Muster im Text nicht oder nur eine konstante Anzahl von Malen vorkommt, führt der Boyer-Moore-Algorithmus in der Suchphase im schlechtesten Fall O(n) Vergleiche durch. Der Beweis hierfür ist allerdings recht schwierig.

Im allgemeinen Fall sind Θ(n·m) Vergleiche erforderlich, etwa wenn das Muster am und der Text an ist. Durch eine geringfügige Modifikation des Algorithmus lässt sich die Anzahl der Vergleiche aber auch im allgemeinen Fall auf O(n) begrenzen.

Ist das Alphabet groß im Vergleich zu Länge des Musters, benötigt der Algorithmus im Durchschnitt O(n/m) Vergleiche. Dies ist der Fall, weil die Schlechtes-Zeichen-Strategie häufig Verschiebungen um m ergibt.

 

Zusammenfassung

Der Boyer-Moore-Algorithmus verwendet zwei Strategien, um bei einem Mismatch die größtmögliche Verschiebung des Musters zu bestimmen: die Schlechtes-Zeichen-Strategie und die Gutes-Ende-Strategie. Beide Strategien können Verschiebungen um m bewirken: die Schlechtes-Zeichen-Strategie, wenn das erste verglichene Textzeichen nicht im Muster vorkommt und die Gutes-Ende-Strategie, wenn die über­einstimmenden Textzeichen nicht an anderer Stelle im Muster vorkommen.

Der Vorlauf für die Gutes-Ende-Strategie ist recht schwierig zu verstehen und zu implementieren. Daher findet man gelegentlich Versionen des Boyer-Moore-Algorithmus, in denen die Gutes-Ende-Strategie schlicht weggelassen wird. Die Begründung ist, dass die Schlechtes-Zeichen-Strategie ausreichend sei und die Gutes-Ende-Strategie nicht viele Vergleiche einspare.

Dies stimmt jedoch nur bei großen Alphabeten. Will man sich der Einfachheit halber auf die Schlechtes-Zeichen-Strategie beschränken, so sind der Horspool-Algorithmus und der Sunday-Algorithmus geeigneter.

 

Literatur

[BM 77]R.S. Boyer, J.S. Moore: A Fast String Searching Algorithm. Communications of the ACM, 20, 10, 762-772 (1977)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Verfahren von Boyer-Moore und andere Textsuch­verfahren, so etwa die Verfahren von Knuth-Morris-Pratt, Horspool und Sunday finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Sortieren, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortier­algorithmen.

[Weitere Informationen]

Buch  
[1]http://www-igm.univ-mlv.fr/~lecroq/string/  
[2]http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/stringmatchingclasses/BmStringMatcher.java  
Boyer-Moore-Algorithmus als Java-Programm
[3]http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/bmPreprocess.xls  
Vorlauf für die Gutes-Zeichen-Strategie als Visualisierung in Excel

 

 

Weiter mit: [Modifizierter Boyer-Moore-Algorithmus] [Horspool-Algorithmus] oder up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 22.02.2001   Updated: 05.09.2012
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik