Textsuche

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

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

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 ∈ 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.

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.

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.

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 a^m in aⁿ, sind Θ(n·m) Vergleiche erforderlich.

Für die Analyse des Verhaltens im Durchschnitt wird wiederum eine Wahrscheinlichkeitsverteilung der Zeichen des Alphabets zugrunde gelegt.

Sei h_j die Wahrscheinlichkeit des Zeichens p_j. Mit dieser Wahrscheinlichkeit muss das Muster wie in Bild 3 dargestellt mit p_j 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 h_j  (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 h_j < 1 sind. Für h gilt h≤1, wenn alle Zeichen des Musters verschieden sind. Auch wenn jedes Zeichen nur eine konstante Anzahl von Malen im Muster vorkommt, gilt noch h ∈ O(1). In diesen Fällen gilt also V ∈ O(n/m). Nur wenn ein Zeichen Ω(m)-mal im Muster vorkommt, ist h ∈ Ω(m), somit sind dann insgesamt V ∈ Θ(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 Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

[Web 1]   http://www-igm.univ-mlv.fr/~lecroq/string/