Der Boyer-Moore Algorithmus verwendet wie der KPM das Preprocessing. Allerdings zwei davon.
Zuerst wird das Preprocessing für die "Bad-Character-Rule" (schlechteste Buchstaben Heuristik) und - mit Hilfe der N-Boxes - für die "Good-Suffix-Rule" (beste Buchstaben Heuristik) durchgeführt. Dann beginnt der eigentliche Suchvorgang. Auffallend hierbei ist,
dass das Suchmuster immer von links nach rechts gescannt wird.
Die Schlechter-Buchstabe-Heuristik untersucht, ob das Zeichen im Text, das als erstes nicht mehr mit den Suchmustern übereingestimmt hat, an einer anderen Stelle im Suchmuster vorkommt und schlägt eine entsprechende Schrittweite vor.
Die Gutes-Suffix-Heuristik hingegen untersucht, ob das Suffix des Suchmuster, das mit dem Text übereingestimmt hat, an einer anderen Stelle im Suchmuster vorkommt und schlägt eine entsprechende Schrittweite vor.
Tritt also während des Vergleiches von Suchmuster und Text ein "Mismatch" auf, so wird mit
der "Bad-Character-" als auch mit der "Good-Suffix-Rule" berechnet, wie weit das Suchmuster nach rechts springen darf. Das Maximum von beiden wird dann für den Sprung genommen.
Hier nochmals der Boyer-Moore-Algorithmus in der Zusammenfassung.......
- überprüfe das Muster von links nach rechts
- bei Nichtübereinstimmung verschiebe das Muster um MAXIMAL(Bad-Character-Rule(i),Good-Suffix-Rule(j)) Positionen. i ist dabei die aktuelle Position im Text und j die Position im Muster.
Hierzu nun ein Beispielsablauf des Boyer-Moore-Algorithmuses........
| a | b | c | c | a | b | c | d | a | a | b | c | d | a | |
| 1. | a | b | c | d | ||||||||||
| 2. | a | b | c | d | ||||||||||
| 3. | a | b | c | d | ||||||||||
| 4. | a | b | c | d | ||||||||||
| 5. | a | b | c | d | ||||||||||
| 6. | a | b | c | d | ||||||||||
| 7. | a | b | c | d | ||||||||||
| 8. | a | b | c | d |
Auf den ersten Blick könnte man meinen er bräuchte in diesem Beispiel
mehr Zeichenvergleiche als der KPM-Algorithmus im Kapitel zuvor. Aber zählt man
nach, wird man feststellen, das beide gleich viel Zeichen vergleichen.
Sicherlich hängt das Ergebnis von der Länge des Suchtextes ab. Aber dazu mehr
im nächsten Kapitel. Wir wollen uns nun den Boyer-Moore in Algorithmus ansehen....
/*Download:booyer.c*/ #include <stdio.h> #include <stdlib.h> #include <string.h> void boyer_moore(char *pat,char *text) { int i,table[256]; int len=strlen(pat); int len_text = strlen(text); int ptct,count; for(i=0;i<256;i++)table[i]=len; for(i=0;i<len;i++)table[pat[i]]=len-(i+1); ptct=len-1; while(ptct<len_text) { count=0; while(count<len) { if(text[ptct-count]!=pat[len-1-count])break; else count++; } if(count==len) { printf("Gefunden an Pos. %d\n",ptct); ptct+=len; } else ptct+=table[text[ptct-count]]; } } int main() { boyer_moore("ex", "a example extra text"); return 0; } |
Boyer Moore:
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bm.htm
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
http://ivs.cs.uni-magdeburg.de/~dumke/EAD/Skript45.html
Ein Java-Applet welches alle drei vorgestellten String-Matchings simuliert (Top):
www.dcc.ufmg.br/~cassia/smaa/index.html
