Textsuche

Modifizierter Boyer-Moore-Algorithmus

Der Boyer-Moore-Algorithmus benötigt im schlechtesten Fall Θ(n·m) Vergleiche, etwa bei der Suche des Musters a^m in dem Text aⁿ. 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:

0	1	2	3	4	5	6	7	8	...
b	a	a	a	a	b	a	a	a	b	c	a
a	a	b	a	a
			a	a	b	a	a

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.

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 k größer gleich 0, 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); } } }

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;.

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 a^m und der Text aⁿ 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.

[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.