Textsuche

Nicht ganz so naiver Algorithmus

Beim naiven Algorithmus ist es nicht notwendig, die Zeichen des Musters p in aufsteigender Reihenfolge p₀, ..., p_m-1 mit dem Text zu vergleichen. Sie können in beliebiger Reihenfolge verglichen werden. Es ist vorteilhaft, zuerst diejenigen Zeichen zu vergleichen, die mit der größten Wahrscheinlichkeit einen Mismatch verursachen, sodass die j-Schleife möglichst schnell abgebrochen werden kann. Diese Vorgehensweise ist dann möglich, wenn die Häufigkeitsverteilung der Zeichen im Text, zumindest annäherungsweise, bekannt ist. In deutschen Texten kommen zum Beispiel die Zeichen e, n, i, s, r, a, t häufig vor, die Zeichen v, j, x, y, q eher selten.

Sucht man beispielsweise das Muster text, würde man zuerst das x mit dem entsprechenden Zeichen des Textes vergleichen, bei Übereinstimmung danach die beiden t's und dann das e.

In dem folgenden Beispiel tritt das Zeichen a am häufigsten auf, die Zeichen b und c seltener. Daher wird zuerst das b des Musters verglichen, dann die a's.

Beispiel:

012345678...

aaabaabacabca

aaba

. . .

Es zeigt sich, dass mit diesem Verfahren gegenüber dem naiven Algorithmus weniger Vergleiche durchgeführt werden.

Mit g_j sei die Stellung des Zeichens p_j in der Vergleichsreihenfolge bezeichnet. Ist beispielsweise das Zeichen p₂ ein x, das als erstes verglichen werden soll, so ist g₂ = 0. Es handelt sich bei g also um eine Permutation der Indexmenge {0, ..., m-1}. Beim naiven Algorithmus ist das j-te Zeichen der Vergleichsreihenfolge stets gerade das j-te Zeichen des Musters, also g_j = j.

Um die Vergleichsreihenfolge der Zeichen des Musters entsprechend einer Häufigkeitsverteilung der Zeichen des Alphabets festzulegen, ist ein Vorlauf (preprocessing) nötig. Im Prinzip müssen die Zeichen des Musters nach ihrer Wahrscheinlichkeit sortiert werden. Hierfür ist eine Zeit von O(m log(m)) erforderlich.

Nicht ganz so naiver Algorithmus

Eingabe:

Text t = t₀ ... t_n-1 und Muster p = p₀ ... p_m-1 sowie Vergleichsreihenfolge g = g₀ ... g_m-1

Ausgabe:

Alle Positionen von Vorkommen von p in t, d.h. { i | t_i ... t_i+m-1 = p }

Methode:

void notsoNaiveSearch()
{
    int i=0, j;
    while (i<=n-m)
    {
        j=0;
        while (j<m && p[g[j]]==t[i+g[j]]) j++;
        if (j==m) report(i);
        i++;
    }
}

Die Analyse der Anzahl der benötigten Vergleiche ist im Prinzip dieselbe wie beim naiven Algorithmus.

Mit h_j sei nun die Wahrscheinlichkeit bezeichnet, mit der das g_j-te Zeichen des Musters im Text auftritt. Somit ist h₀ die Wahrscheinlichkeit desjenigen Zeichens, das als erstes verglichen wird.

Als Formel für die Anzahl der Vergleiche v pro Textposition ergibt sich also

v = 1 + h₀ + h₀·h₁ + ... + h₀·h₁· ... ·h_m-2.

Beispiel: In obigem Beispiel tritt das a mit der Wahrscheinlichkeit 0,6 im Text auf, das b mit der Wahrscheinlichkeit 0,3. Das b wird zuerst verglichen, da es die geringste Wahrscheinlichkeit hat. Somit ist h₀ = 0,3 und h₁ = h₂ = 0,6. Bezogen auf dieses Beispiel ergibt sich folgender Wert:

v = 1 + 0,3 + 0,3 · 0,6 + 0,3 · 0,6 · 0,6 = 1,588.

Der verbesserte Algorithmus führt also nur rund 1,6 Vergleiche pro Textzeichen durch, gegenüber 2,1 beim naiven Algorithmus.

Wie viele Vergleiche sich einsparen lassen, hängt von der Wahrscheinlichkeitsverteilung der Zeichen des Musters ab. Sind alle Zeichen des Musters gleichwahrscheinlich, so lassen sich überhaupt keine Vergleiche einsparen. Im schlechtesten Fall hat dieser Algorithmus also dieselbe Komplexität wie der naive Algorithmus.

Kommt allerdings im Muster ein Zeichen vor, dessen Wahrscheinlichkeit sehr klein ist, so führt der Algorithmus im Durchschnitt nur wenig mehr als einen Vergleich pro Textzeichen durch.

Für die korrekte Funktionsweise des naiven Algorithmus kommt es nicht darauf an, dass die Zeichen des Musters mit den Zeichen des Textfensters in einer bestimmten Reihenfolge verglichen werden. Dies ist beim Knuth-Morris-Pratt-Algorithmus und beim Boyer-Moore-Algorithmus anders. Beim Sunday-Algorithmus und beim Karp-Rabin-Algorithmus dagegen ist die Vergleichsreihenfolge wiederum beliebig.

Für Algorithmen, bei denen die Vergleichsreihenfolge beliebig ist, definieren wir eine Funktion matchesAt, die das Muster mit dem Textfenster vergleicht und bei Übereinstimmung true zurückgibt. Für die Funktion matchesAt sind dann unterschiedliche Implementationen möglich, z.B. ein Vergleich von links nach rechts oder in der Reihenfolge der Zeichenwahrscheinlichkeiten.

Der naive Algorithmus, bzw. der nicht ganz so naive Algorithmus, je nach Implementation der Funktion matchesAt, lässt sich somit wie folgt formulieren:

void naiveSearch()
{
for (int i=0; i<=n-m; i++)
if (matchesAt(i)) report(i);
}

Implementation von matchesAt

a) für den naiven Algorithmus (Vergleich von links nach rechts)

boolean matchesAt(int i)
{
    int j=0;
    while (j<m && p[j]==t[i+j]) j++;
    return j==m;
}

b) für den nicht ganz so naiven Algorithmus (Vergleich entsprechend den Zeichenwahrscheinlichkeiten)

boolean matchesAt(int i)
{
    int j=0;
    while (j<m && p[g[j]]==t[i+g[j]]) j++;
    return j==m;
}

[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den nicht ganz so naiven 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]

Weiter mit: [Knuth-Morris-Pratt-Algorithmus] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 22.03.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Textsuche

Nicht ganz so naiver Algorithmus

Idee

Algorithmus

Analyse

Funktion matchesAt

Literatur