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ückzuführen, dass der Algorithmus keinerlei Information aus gefundenen Übereinstimmungen weiterverwendet, 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 übereingestimmt. 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 übereingestimmt hat. Dann überlappt ein Präfix des Musters an der neuen Position mit dem übereinstimmenden Suffix der alten Position. Die Gutes-Ende-Strategie garantiert, dass alle Zeichen des überlappenden Bereiches übereinstimmen. 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 überlappenden Bereich ein Mismatch gefunden. Der schlechteste Fall des Boyer-Moore-Verfahrens ist jedoch gerade durch viele, sich überlappende Vorkommen des Musters gekennzeichnet.

Algorithmus

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

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

Bei jeder Verschiebung ist das entsprechende k zu bestimmen. Die Verschiebung muss aufgrund der Gutes-Ende-Strategie, Fall 2, zustande gekommen sein. Dieser Fall ist gegeben, wenn die Schiebedistanz d aufgrund der Gutes-Ende-Strategie größer als die letzte Vergleichsposition 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 Wertzuweisung k=d>j? m-d: 0; ist gleichbedeutend 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 unterscheidet 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: 15.02.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Angewandte Informatik

mit Schwerpunkten auf Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

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

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik