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 Ü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 über­ein­gestimmt. Daraufhin wird das Muster aufgrund der Gutes-Ende-Strategie (Fall 2) in die gezeigte Position verschoben. Stimmt das Muster an der neuen Position über­ein, 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 über­ein­gestimmt hat. Dann überlappt ein Präfix des Musters an der neuen Position mit dem über­ein­stimmenden Suffix der alten Position. Die Gutes-Ende-Strategie garantiert, dass alle Zeichen des überlappenden 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 ü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 hinunter­gezä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 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 Wertzuweisung 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 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 Textsuch­verfahren, so etwa die Algorithmen 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  

 

 

Weiter mit:   [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