Textsuche

Modifizierter Boyer-Moore-Algorithmus

 aufwärts

Idee

Der Boyer-Moore-Algorithmus benötigt im schlechtesten Fall Θ(n·m) Vergleiche, etwa bei der Suche des Musters am in dem Text an. Dies ist darauf zurück­zuführen, dass der Algorithmus keinerlei Information aus gefundenen Über­ein­stimmungen weiter­verwendet, wenn er das Muster verschiebt. Hierdurch kommen überflüssige Vergleiche zustande.

Beispiel:  

012345678...
baaaabaaabca
aabaa
aabaa

Der Vergleich a-b ergibt einen Mismatch; das Suffix aa hat überein­gestimmt. Daraufhin wird das Muster aufgrund der Gutes-Ende-Strategie (Fall 2) in die gezeigte Position verschoben. Stimmt das Muster an der neuen Position überein, werden die beiden a's an den Positionen 3 und 4 des Textes erneut verglichen.

Eine Verschiebung aufgrund der Gutes-Ende-Strategie (Fall 2) ist immer dann möglich, wenn ein Rand des Musters überein­gestimmt hat. Dann überlappt ein Präfix des Musters an der neuen Position mit dem über­einstimmenden Suffix der alten Position. Die Gutes-Ende-Strategie garantiert, dass alle Zeichen des über­lappenden Bereiches über­einstimmen. Beim Vergleich des Musters an der neuen Position brauchen daher diese Zeichen nicht noch einmal verglichen zu werden.

Diese Situation tritt allerdings nur auf, wenn ein Vorkommen des Musters an der neuen Position vorliegt. Ansonsten wird bereits vor dem über­lappenden Bereich ein Mismatch gefunden. Der schlechteste Fall des Boyer-Moore-Verfahrens ist jedoch gerade durch viele, sich überlappende Vorkommen des Musters gekenn­zeichnet.

Algorithmus

Der Boyer-Moore-Algorithmus ist so zu modifizieren, dass in der inneren While-Schleife der Index j nicht grund­sätzlich bis 0 hinunter­gezählt wird, sondern nur bis zu einem gewissen kgrößer gleich0, wobei k die Breite des über­lappenden Bereiches ist.

Folglich ist das Kriterium dafür, dass ein Vorkommen gefunden worden ist, nunmehr (j < k).

Bei jeder Verschiebung ist das ent­sprechende k zu bestimmen. Die Verschiebung muss aufgrund der Gutes-Ende-Strategie, Fall 2, zustande gekommen sein. Dieser Fall ist gegeben, wenn die Schiebe­distanz d aufgrund der Gutes-Ende-Strategie größer als die letzte Vergleichs­position j ist. Dann ergibt sich k als m-d. Anderenfalls muss, wie im originalen Boyer-Moore-Algorithmus, k = 0 gesetzt werden.

Modifizierter Boyer-Moore-Algorithmus
void bmSearchModified()
{
    int j, i=0, k=0, d;

    while (i<=n-m)
    {
        j=m-1;
        while (j>=k && p[j]==t[i+j]) j--;
        if (j<k)
        {
            report(i);
            i+=s[0];
            k=m-s[0];
        }

        else
        {
            d=s[j+1];
            k=d>j? m-d: 0;
            i+=Math.max(j-occ[t[i+j]], d);
        }
    }
}

 

Die bedingte Wert­zuweisung k=d>j? m-d: 0; ist gleich­bedeutend mit if (d>j) k=m-d; else k=0;.

Analyse

Wenn das Muster im Text nicht vorkommt, dann wird die innere While-Schleife des Algorithmus immer aufgrund eines Mismatches abgebrochen und nie deswegen, weil j < k wird. Dann unter­scheidet sich das Verhalten des modifizierten Algorithmus nicht vom originalen Algorithmus.

Es werden dagegen Vergleiche eingespart, wenn sich ein Vorkommen des Musters in der oben beschriebenen Weise mit dem vorherigen Fenster überlappt. Der Extremfall ist, wenn etwa das Muster am und der Text an ist. Der modifizierte Algorithmus führt in diesem Fall exakt n Vergleiche durch, während der originale Algorithmus (n-m+1)·m  Element  Θ(n·m) Vergleiche benötigt.

Literatur

[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den modifizierten Boyer-Moore-Algorithmus und weitere Textsuchverfahren, so etwa die Algorithmen von Knuth-Morris-Pratt, Horspool und Sunday finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Horspool-Algorithmus]   oder   up

 

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


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik