TextsucheModifizierter
| ![]() |
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:
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 k0, 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;.
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 Θ(n·m) Vergleiche benötigt.
Weiter mit: [Horspool-Algorithmus] oder
![]() |
![]() |
![]() |
Informatik in Flensburg studieren...
Neu gestaltetes Studienangebot:
Bachelor-Studiengang
Angewandte Informatik
mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.
Ihr Abschluss
nach 7 Semestern:
Bachelor of Science
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 Hochschule Flensburg: