TextsucheHorspool-Algorithmus | ![]() ![]() |
Der Boyer-Moore-Algorithmus verwendet zwei Strategien, um die Verschiebung des Musters bei einem Mismatch zu bestimmen: die Schlechtes-Zeichen- und die Gutes-Ende-Strategie. Von Horspool [Hor 80] stammt die Idee, nur die Schlechtes-Zeichen-Strategie zu verwenden, jedoch nicht das Zeichen heranzuziehen, das zu einem Mismatch geführt hat, sondern stets das ganz rechte Zeichen des Textfensters.
Beispiel:
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(a) Boyer-Moore | (b) Horspool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Das Suffix ab hat übereingestimmt, der Vergleich c-a ergibt einen Mismatch. Der Boyer-Moore-Algorithmus (a) ermittelt die Schiebedistanz nach der Schlechtes-Zeichen-Strategie aufgrund des letzten Vorkommens von c. Der Horspool-Algorithmus (b) ermittelt die Schiebedistanz aufgrund des letzten Vorkommens von b, wobei das Vorkommen des b an der letzten Position des Musters nicht mitzählt.
Auch im Horspool-Algorithmus tritt der günstigste Fall ein, wenn jedes Mal beim ersten Vergleich ein Textzeichen gefunden wird, das im Muster überhaupt nicht vorkommt. Dann benötigt der Algorithmus nur O(n/m) Vergleiche.
Die für die Schlechtes-Zeichen-Strategie benötigte Occurrence-Funktion occ wird geringfügig anders berechnet als beim Boyer-Moore-Algorithmus. Für jedes Alphabetzeichen a ist occ(p, a) die Position seines letzten Vorkommens in p0 ... pm-2, bzw. -1, falls das Zeichen darin überhaupt nicht vorkommt. Das letzte Zeichen pm-1 des Musters wird also nicht mit berücksichtigt.
Beispiel:
Hier ist occ(textet, t) = 3, weil das letzte Vorkommen von t in dem Wort texte an Position 3 ist. Ferner ist occ(text, t) = 0, weil das letzte Vorkommen von t in dem Wort tex an Position 0 ist, und schließlich ist occ(next, t) = -1, weil t in nex überhaupt nicht vorkommt.
Die Occurrence-Funktion für ein bestimmtes Muster p wird in einem Array occ gespeichert, das durch die Zeichen des Alphabets indiziert wird. Für jedes Zeichen a A enthält occ[a] den entsprechenden Funktionswert occ(p, a).
Folgende Funktion horspoolInitocc berechnet zu gegebenem Muster p die Occurrence-Funktion.
void horspoolInitocc() { int j; char a; for (a=0; a<alphabetsize; a++) occ[a]=-1; for (j=0; j<m-1; j++) { a=p[j]; occ[a]=j; } } |
Es folgt der Suchalgorithmus.
void horspoolSearch() { int i=0, j; while (i<=n-m) { j=m-1; while (j>=0 && p[j]==t[i+j]) j--; if (j<0) report(i); i+=m-1; i-=occ[t[i]]; } } |
[Web 1] | http://www-igm.univ-mlv.fr/~lecroq/string/ |
Weiter mit: [Sunday-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
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 Hochschule Flensburg: