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 ü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 im Muster. 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. Der Sunday-Algorithmus (c) ermittelt die Schiebedistanz 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 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.

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 Wahrscheinlichkeit im Text vorkommt. Voraussetzung ist dabei natürlich wiederum, dass die Häufigkeitsverteilung der Textzeichen zumindest annähernd bekannt ist (z.B. die Häufigkeit der Buchstaben in deutschen Texten).

Das folgende Beispiel zeigt die durchgefü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 Suchalgorithmus 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   Datenschutz   ©   Created: 06.04.2001   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
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