Textsuche
Sunday-Algorithmus
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:
(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:
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.
{
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:
{
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
Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
Weiter mit: [Skip-Search-Algorithmus] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 06.04.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden