Textsuche
Horspool-Algorithmus
Idee
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.
Vorlauf
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:
- occ(text, x) = 2
- occ(textet, t) = 3
- occ(text, t) = 0
- occ(next, t) = -1
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.
{
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.
Suchalgorithmus
{
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]];
}
}
Literatur
[Hor 80] R.N. Horspool: Practical Fast Searching in Strings. Software - Practice and Experience 10, 501-506 (1980)
[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)
Den Horspool-Algorithmus und weitere Textsuchverfahren (Knuth-Morris-Pratt, Boyer-Moore, ...) finden Sie auch in meinem Buch über Algorithmen.
Weitere
Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
Weiter mit: [Sunday-Algorithmus] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 22.02.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden