Textsuche

Naiver Algorithmus

 aufwärts

In der Beschreibung aller folgenden Text­such­verfahren wird das Muster stets mit p und der zu durch­suchende Text mit t bezeichnet. Die Länge des Musters ist stets m, die des Textes n. Es ist sinnvoll, mkleiner gleichn anzunehmen.

Idee

Der naive Algorithmus überprüft das Muster an allen Positionen i des Textes. Die möglichen Positionen reichen von i = 0 (Muster linksbündig mit dem Text) bis i = n-m (Muster rechtsbündig mit dem Text). Das Muster wird an der jeweiligen Position zeichenweise von links nach rechts mit dem Text verglichen. Bei einem Mismatch oder bei voll­ständiger Über­ein­stimmung wird das Muster um eine Position weiter­geschoben und an dieser Position verglichen usw.

Beispiel:  

012345678...
aaabaabacabca
aaba
aaba
aaba
aaba
aaba
aaba
. . .

Algorithmus

 

Naiver Algorithmus
Eingabe:Text  t = t0 ... tn-1  und Muster   p = p0 ... pm-1
Ausgabe:Alle Positionen von Vorkommen von p in t, d.h.  { i  |  ti ... ti+m-1 = p }
Methode:
void naiveSearch()
{
    int i=0, j;
    while (i<=n-m)
    {
        j=0;
        while (j<m && p[j]==t[i+j]) j++;
        if (j==m) report(i);
        i++;
    }
}

 

Der Algorithmus überprüft an allen in Frage kommenden Positionen i des Textes, ob das Muster über­einstimmt. Hierzu werden alle Zeichen des Musters pj mit den entsprechenden Zeichen des Textes ti+j verglichen. Bei einem Mismatch wird die j-Schleife abgebrochen. Wenn dagegen alle m Zeichen des Musters überein­gestimmt haben, wird durch Aufruf der (hier nicht näher spezifizierten) Funktion report die Position des Vorkommens festgehalten.

Das Programm lässt sich mit For-Schleifen eleganter formulieren; hier ist in Analogie zu den noch folgenden Verfahren eine Version mit While-Schleifen gewählt worden.

Wir nehmen an, dass der Such­algorithmus in einer Klasse gekapselt ist, in der p, t, n und m als Elemente deklariert sind.

Analyse

Verhalten im schlechtesten Fall

Der Algorithmus durchläuft die i-Schleife (n-m+1)-mal. Die j-Schleife wird höchstens m-mal durchlaufen. Somit gilt für die Anzahl der Vergleiche

V kleiner gleich (n-m+1) · m.

Es ist also V Element O(n·m).

Im schlechtesten Fall wird die j-Schleife tatsächlich jedesmal genau m-mal durchlaufen, zum Beispiel wenn der Text t = aaaaaaa...aaa ist und das Muster p = aa...aab ist. In diesem Fall gilt V  =  (n-m+1) · m.

Ist das Muster kurz im Vergleich zum Text, also z.B. mkleiner gleichn/2, so ist

V  =  (n-m+1) · m größer gleich (n-n/2+1) · m größer gleich n/2 · m.

Damit gilt V Element Ω(n·m). Der Algorithmus liegt also in Θ(n·m).

Verhalten im günstigsten Fall

Im günstigsten Fall liefert immer bereits der erste Vergleich einen Mismatch, somit sind Θ(n) Vergleiche erforderlich.

Verhalten im Durchschnitt

Abhängig vom Muster und von der Wahr­schein­lich­keitsverteilung der Zeichen des Textes lässt sich das Verhalten im Durchschnitt ermitteln.

Mit hj sei die Wahr­schein­lich­keit bezeichnet, mit der das j-te Zeichen des Musters im Text auftritt. Ist also beispiels­weise pj = a, und sind 15% aller Textzeichen a's, so ist hj = 0,15.

Mit v sei die durch­schnitt­liche Anzahl der Zeichen­vergleiche pro Position i des Textes bezeichnet, also die durch­schnitt­liche Anzahl der Durchläufe durch die j-Schleife.

Das erste Zeichen des Musters p0 wird immer verglichen, dies ist also 1 Vergleich. In h0 Fällen stimmt dieses erste Zeichen überein, so dass auch noch das zweite Zeichen des Musters verglichen werden muss. In h1 Fällen von diesen Fällen stimmt auch das zweite Zeichen überein, also absolut gerechnet in h0·h1 Fällen, so dass auch noch das dritte Zeichen des Musters verglichen werden muss usw.

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

v  =  1  +   h0   +   h0·h1   +  ...  +   h0·h1· ... ·hm-2.

Verhalten im Durchschnitt bei fester Wahr­schein­lich­keitsverteilung der Textzeichen

Es sei h = max(hj). Voraus­gesetzt sei, dass h<1 ist, d.h. dass es nicht lediglich ein einziges Zeichen gibt, das mit 100% Wahr­schein­lich­keit auftritt. Die Anzahl der Vergleiche lässt sich dann unabhängig vom Muster abschätzen durch

v  =  1  +   h   +   h2   +  ...  +   hm-1.

Die geometrische Reihe 1 +  h  +  h2  + ...  konvergiert gegen 1/(1 – h). Daher gilt

v  kleiner gleich  1/(1 – h).

Die Anzahl der Vergleiche insgesamt beträgt somit

V  =  (n-m+1)/(1 – h)  Element  O(n).

Der naive Algorithmus hat also im Durchschnitt lineare Laufzeit.

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. Somit ist h0 = h1 = 0,6 und h2 = 0,3. Die Anzahl der Vergleiche für das Muster aaba ist also

v  =  1  +  0,6  +  0,6 · 0,6  +  0,6 · 0,6 · 0,3  =  2,068.

Der naive Algorithmus führt also mit dem Muster aaba und bei Texten, bei denen die Wahr­schein­lich­keitsverteilung der Zeichen wie in dem Beispiel ist, im Durchschnitt rund 2,1 Vergleiche pro Textzeichen durch.

Unabhängig vom Muster gilt mit h = 0,6

v  kleiner gleich  1  +  0,6  +  0,62  +  0,63  +  ...   kleiner gleich    1/(1-0,6)  =  2,5 ,

also im Durchschnitt höchstens 2,5 Vergleiche pro Textzeichen.

In deutschen Texten tritt das e als häufigstes Zeichen mit der Wahr­schein­lich­keit h = 0,13 auf. Hier führt der naive Algorithmus also im Durchschnitt höchstens 1/(1-0,13) = 1,15 Vergleiche pro Textzeichen durch.

Literatur

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

Den 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:   [Nicht ganz so naiver Algorithmus]   oder   up

 

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