Textsuche

Nicht ganz so naiver Algorithmus

 aufwärts

Idee

Beim naiven Algorithmus ist es nicht notwendig, die Zeichen des Musters p in auf­steigender 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 Wahr­schein­lich­keit einen Mismatch verursachen, so dass die j-Schleife möglichst schnell abgebrochen werden kann. Diese Vorgehens­weise ist dann möglich, wenn die Häufigkeits­verteilung der Zeichen im Text, zumindest annäherungs­weise, 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 beispiels­weise das Muster text, würde man zuerst das x mit dem ent­sprechenden Zeichen des Textes vergleichen, bei Über­ein­stimmung 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 Vergleichs­reihen­folge bezeichnet. Ist beispiels­weise 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 Vergleichs­reihen­folge stets gerade das j-te Zeichen des Musters, also gj = j.

Um die Vergleichs­reihen­folge der Zeichen des Musters entsprechend einer Häufigkeits­verteilung der Zeichen des Alphabets festzulegen, ist ein Vorlauf (preprocessing) nötig. Im Prinzip müssen die Zeichen des Musters nach ihrer Wahr­schein­lich­keit 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 Wahr­schein­lich­keit bezeichnet, mit der das gj-te Zeichen des Musters im Text auftritt. Somit ist h0 die Wahr­schein­lich­keit 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 Wahr­schein­lich­keit 0,6 im Text auf, das b mit der Wahr­schein­lich­keit 0,3. Das b wird zuerst verglichen, da es die geringste Wahr­schein­lich­keit 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 Wahr­schein­lich­keitsverteilung der Zeichen des Musters ab. Sind alle Zeichen des Musters gleich­wahr­scheinlich, 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 Wahr­schein­lich­keit 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 Funktions­weise 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 Vergleichs­reihen­folge wiederum beliebig.

Für Algorithmen, bei denen die Vergleichs­reihen­folge beliebig ist, definieren wir eine Funktion matchesAt, die das Muster mit dem Textfenster vergleicht und bei Über­ein­stimmung true zurückgibt. Für die Funktion matchesAt sind dann unter­schiedliche Implementationen möglich, z.B. ein Vergleich von links nach rechts oder in der Reihenfolge der Zeichen­wahrscheinlich­keiten.

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 Zeichen­wahrscheinlich­keiten)

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   ©   Created: 22.03.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