Textsuche

Skip-Search-Algorithmus

 aufwärts

Idee

Hat das Muster p eine Länge von m>1, so ist es im allgemeinen nicht erforderlich, jedes Textzeichen zu inspizieren, wie bereits beim Boyer-Moore-Algorithmus, beim Horspool-Algorithmus und beim Sunday-Algorithmus gesehen. Die folgende Umsetzung dieser Idee führt ebenfalls zu einem im Durchschnitt sublinearen Algorithmus [CLP 98].

Bild 1 zeigt schematisch den Text t, in dem jedes m-te Zeichen markiert ist. Durch dieses Raster kann das Muster p nicht fallen, ohne dass eines der markierten Zeichen berührt ist.

Bild 1: Raster der Weite m
Bild 1: Raster der Weite m

Bild 2 zeigt die Situation, in der das markierte Zeichen ein x ist, das im Muster überhaupt nicht vorkommt. Dann kann das Muster an keiner Position des hellgrau getönten Bereiches beginnen.

Bild 2: Verbotener Bereich für das Muster
Bild 2: Verbotener Bereich für das Muster

Bild 3 zeigt die Situation, in der das markierte Zeichen ein b ist, das im Muster nur einmal vorkommt. Dann kann das Muster nur in der gezeigten Position innerhalb des hellgrau getönten Bereiches über­einstimmen.

Bild 3: Möglichkeit eines Vorkommens
Bild 3: Möglichkeit eines Vorkommens

Wenn das markierte Zeichen im Muster mehrmals vorkommt, kann das Muster innerhalb des grau getönten Bereiches an entsprechend vielen Position über­einstimmen (Bild 4).

Bild 4: Mehrere Möglichkeiten von Vorkommen
Bild 4: Mehrere Möglichkeiten von Vorkommen

Das Such­verfahren stochert also zunächst nur an den dunkelgrau markierten Stellen von Bild 1 im Text herum. Diese markierten Positionen nennen wir Raster­positionen. Nur wenn an der betreffenden Raster­position ein Zeichen steht, das im Muster vorkommt, wird das Muster wie in Bild 3 gezeigt ausgerichtet und verglichen. Kommt das Zeichen mehrere Male im Muster vor, müssen auch noch weitere mögliche Vorkommen geprüft werden.

Vorlauf

Wie beim Boyer-Moore-Algorithmus wird eine Funktion occ benötigt, die für jedes Zeichen des Alphabets die Position seines letzten Vorkommens im Muster liefert, bzw. -1, falls das Zeichen nicht im Muster 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 ent­sprechenden Funktions­wert occ(p, a).

Die Occurrence-Funktion liefert nur das letzte Vorkommen eines Zeichens im Muster p. Alle weiteren Vorkommen stehen in einem Array next der Länge m, und zwar enthält next[i] jeweils das nächste Vorkommen des Zeichens p[i], bzw. -1, falls kein weiteres Vorkommen existiert.

Beispiel:  

j:012345
p:textet
next:-1-1-1013

Für das Zeichen t beispiels­weise liefert die Occurrence-Funktion die Position 5. Das nächste Vorkommen von t liegt bei next[5] = 3. Das darauf folgende Vorkommen von t ist bei next[3] = 0. Ein weiteres Vorkommen von t existiert nicht, daher next[0] = -1.

Folgende Funktion skipInitocc berechnet zu gegebenem Muster p die Occurrence-Funktion, ferner in Zeit O(m) die Einträge in das Array next.

void skipInitocc()
{
    int j;
    char a;

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

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

Suchalgorithmus

Wie beim Sunday-Algorithmus ist es nicht notwendig, die Vergleiche zwischen Muster und Textfenster in einer bestimmten Reihenfolge (z.B. von rechts nach links) auszuführen. Der folgende Such­algorithmus verwendet die Funktion matchesAt, in der die Vergleichs­reihen­folge festgelegt ist.

void skipSearch()
{
    int i, k;
    for (i=m-1; i<n; i+=m)
    {
        k=occ[t[i]];
        while (k>=0 && i-k<=n-m)
        {
            if (matchesAt(i-k)) report(i-k);
            k=next[k];
        }
    }
}

Analyse

Im günstigsten Fall benötigt der Algorithmus O(n/m) Vergleiche, nämlich wenn keines der in Bild 1 markierten Zeichen im Muster vorkommt.

Im schlechtesten Fall, etwa bei der Suche von am in an, sind Θ(n·m) Vergleiche erforderlich.

Für die Analyse des Verhaltens im Durchschnitt wird wiederum eine Wahr­schein­lich­keitsverteilung der Zeichen des Alphabets zugrunde gelegt.

Sei hj die Wahr­schein­lich­keit des Zeichens pj. Mit dieser Wahr­schein­lich­keit muss das Muster wie in Bild 3 dargestellt mit pj an der Raster­position i ausgerichtet und verglichen werden. Für den Vergleich des Musters seien jeweils im Durchschnitt v Zeichen­vergleiche erforderlich.

Die mittlere Anzahl der Vergleiche pro Raster­position ergibt sich also aus der Summe h der hj  (j = 0, ..., m-1), multi­pliziert mit v.

Damit beträgt die Anzahl der Vergleiche im Durchschnitt insgesamt

V   =   n/m · h · v.

Wie in der Analyse des naiven Algorithmus gesehen, ist v unabhängig von m, wenn alle hj < 1 sind. Für h gilt hkleiner gleich1, wenn alle Zeichen des Musters verschieden sind. Auch wenn jedes Zeichen nur eine konstante Anzahl von Malen im Muster vorkommt, gilt noch h Element O(1). In diesen Fällen gilt also V Element O(n/m). Nur wenn ein Zeichen Ω(m)-mal im Muster vorkommt, ist h Element Ω(m), somit sind dann insgesamt V Element Θ(n) Vergleiche erforderlich.

Literatur

[CLP 98]C. Charras, T. Lecroq, J.D. Pehoushek: A Very Fast String Matching Algorithm for Small Alphabets and Long Patterns. Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science 1448, Springer, 55-64 (1998)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den Skip-Search-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:   [Karp-Rabin-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