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 übereinstimmen.

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 übereinstimmen (Bild 4).

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

Das Suchverfahren stochert also zunächst nur an den dunkelgrau markierten Stellen von Bild 1 im Text herum. Diese markierten Positionen nennen wir Rasterpositionen. Nur wenn an der betreffenden Rasterposition 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 entsprechenden Funktionswert 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 beispielsweise 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 Suchalgorithmus verwendet die Funktion matchesAt, in der die Vergleichsreihenfolge 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 Wahrscheinlichkeitsverteilung der Zeichen des Alphabets zugrunde gelegt.

Sei hj die Wahrscheinlichkeit des Zeichens pj. Mit dieser Wahrscheinlichkeit muss das Muster wie in Bild 3 dargestellt mit pj an der Rasterposition i ausgerichtet und verglichen werden. Für den Vergleich des Musters seien jeweils im Durchschnitt v Zeichenvergleiche erforderlich.

Die mittlere Anzahl der Vergleiche pro Rasterposition ergibt sich also aus der Summe h der hj  (j = 0, ..., m-1), multipliziert 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   Datenschutz   ©   Created: 22.02.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