Textsuche

Horspool-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:

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

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

(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 p₀ ... p_m-2, bzw. -1, falls das Zeichen darin überhaupt nicht vorkommt. Das letzte Zeichen p_m-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 Element 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]];
    }
}


[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. [Weitere Informationen]