Textsuche

Sunday-Algorithmus

 English version  aufwärts

Idee

Der Boyer-Moore-Algorithmus verwendet für die Schlechtes-Zeichen-Strategie dasjenige Zeichen des Textes, das zu einem Mismatch geführt hat. Der Horspool-Algorithmus verwendet das ganz rechte Zeichen des Textfensters. Von Sunday [Sun 90] stammt die Idee, das unmittelbar rechts neben dem Textfenster stehende Zeichen zu verwenden, denn dieses ist bei einer Verschiebung des Musters in jedem Fall beteiligt.

Beispiel:  

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

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 im Muster. 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. Der Sunday-Algorithmus (c) ermittelt die Schiebe­distanz aufgrund des letzten Vorkommens von d im Muster. Da d im Muster nicht vorkommt, kann das Muster hinter das d verschoben werden.

 

Auch im Sunday-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.

Anders als beim Boyer-Moore- und beim Horspool-Algorithmus brauchen die Zeichen des Musters beim Sunday-Algorithmus nicht von rechts nach links verglichen zu werden. Sie können in einer beliebigen Reihenfolge verglichen werden; es kann also wie beim nicht ganz so naiven Algorithmus dasjenige Zeichen des Musters als erstes verglichen werden, das mit der geringsten Wahr­schein­lich­keit im Text vorkommt. Voraus­setzung ist dabei natürlich wiederum, dass die Häufigkeits­verteilung der Textzeichen zumindest annähernd bekannt ist (z.B. die Häufigkeit der Buchstaben in deutschen Texten).

Das folgende Beispiel zeigt die durch­geführten Vergleiche, wenn das c des Musters als erstes verglichen wird.

Beispiel:  

0123456789...
abcabdaacba
bcaab
bcaab

Vorlauf

Die für die Schlechtes-Zeichen-Strategie benötigte Occurrence-Funktion occ wird genauso berechnet wie beim Boyer-Moore-Algorithmus.

Folgende Funktion sundayInitocc berechnet zu gegebenem Muster p die Occurrence-Funktion; sie ist identisch mit der Funktion bmInitocc.

void sundayInitocc()
{
    int j;
    char a;

    for (a=0; a<alphabetsize; a++)
        occ[a]=-1;

    for (j=0; j<m; j++)
    {
        a=p[j];
        occ[a]=j;
    }
}

Suchalgorithmus

Unter Verwendung der Funktion matchesAt, die das Muster mit dem jeweiligen Textfenster je nach Implementierung auf bestimmte Art vergleicht, hat der Such­algorithmus folgende Gestalt:

void sundaySearch()
{
    int i=0;
    while (i<=n-m)
    {
        if (matchesAt(i)) report(i);
        i+=m;
        if (i<n) i-=occ[t[i]];
    }
}

 

Es ist notwendig, nach der Anweisung i+=m zu prüfen, ob der Wert von i höchstens n-1 ist, denn es wird anschließend auf t[i] zugegriffen.

Literatur

[Sun 90]D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Verfahren von Sunday und andere Textsuchverfahren, so etwa die Verfahren von Knuth-Morris-Pratt, Boyer-Moore und Horspool 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:   [Skip-Search-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 06.04.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