Textsuche

Nicht ganz so naiver Algorithmus

 aufwärts

Idee

Beim naiven Algorithmus ist es nicht notwendig, die Zeichen des Musters p in aufsteigender Reihenfolge p0, ..., pm-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
aaba
aaba
aaba
aaba
aaba
. . .

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

Algorithmus

Mit gj sei die Stellung des Zeichens pj in der Vergleichsreihenfolge bezeichnet. Ist beispielsweise das Zeichen p2 ein x, das als erstes verglichen werden soll, so ist g2 = 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 gj = 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 = t0 ... tn-1  und Muster   p = p0 ... pm-1 sowie Vergleichsreihenfolge g = g0 ... gm-1
Ausgabe:Alle Positionen von Vorkommen von p in t, d.h.  { i  |  ti ... ti+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++;
    }
}

 

Analyse

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

Mit hj sei nun die Wahrscheinlichkeit bezeichnet, mit der das gj-te Zeichen des Musters im Text auf­tritt. Somit ist h0 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  +   h0   +   h0·h1   +  ...  +   h0·h1· ... ·hm-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 h0 = 0,3 und h1 = h2 = 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.

Funktion matchesAt

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;
}

Literatur

[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]

Buch  

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 22.03.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