Textsuche

Horspool-Algorithmus

 English version  aufwärts

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 heran­zuziehen, das zu einem Mismatch geführt hat, sondern stets das ganz rechte Zeichen des Textfensters.

Beispiel:  

0123456789...
abcabdaacba
bcaab
bcaab
      
0123456789...
abcabdaacba
bcaab
bcaab
 
(a)   Boyer-Moore(b)   Horspool
 

Das Suffix ab hat überein­gestimmt, der Vergleich c-a ergibt einen Mismatch. Der Boyer-Moore-Algorithmus (a) ermittelt die Schiebe­distanz nach der Schlechtes-Zeichen-Strategie aufgrund des letzten Vorkommens von c. Der Horspool-Algorithmus (b) ermittelt die Schiebe­distanz 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 jedesmal 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 Alphabet­zeichen 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ück­sichtigt.

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 Element A enthält occ[a] den entsprechenden Funktions­wert 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 Such­algorithmus.

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]];
    }
}

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(vertikaler Abstand) Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  
[Web 1]http://www-igm.univ-mlv.fr/~lecroq/string/  

 

Weiter mit:   [Sunday-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 22.02.2001   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

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:

Medieninformatik

Wirtschaftsinformatik