Textsuche
Naiver Algorithmus
In der Beschreibung aller folgenden Textsuchverfahren wird das Muster stets mit p und der zu durchsuchende Text mit t bezeichnet. Die Länge des Musters ist stets m, die des Textes n. Es ist sinnvoll, m≤n 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 vollständiger Übereinstimmung wird das Muster um eine Position weitergeschoben und an dieser Position verglichen usw.
Beispiel:
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:
{
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 übereinstimmt. 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 übereingestimmt 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 Suchalgorithmus 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 ≤ (n-m+1) · m.
Es ist also V ∈ O(n·m).
Im schlechtesten Fall wird die j-Schleife tatsächlich jedes Mal 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. m≤n/2, so ist
V = (n-m+1) · m ≥ (n-n/2+1) · m ≥ n/2 · m.
Damit gilt V ∈ Ω(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 Wahrscheinlichkeitsverteilung der Zeichen des Textes lässt sich das Verhalten im Durchschnitt ermitteln.
Mit hj sei die Wahrscheinlichkeit bezeichnet, mit der das j-te Zeichen des Musters im Text auftritt. Ist also beispielsweise pj = a, und sind 15% aller Textzeichen a's, so ist hj = 0,15.
Mit v sei die durchschnittliche Anzahl der Zeichenvergleiche pro Position i des Textes bezeichnet, also die durchschnittliche 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, sodass 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, sodass 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 Wahrscheinlichkeitsverteilung der Textzeichen
Es sei h = max(hj). Vorausgesetzt sei, dass h<1 ist, d.h. dass es nicht lediglich ein einziges Zeichen gibt, das mit 100% Wahrscheinlichkeit 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 ≤ 1/(1 – h).
Die Anzahl der Vergleiche insgesamt beträgt somit
V = (n-m+1)/(1 – h) ∈ O(n).
Der naive Algorithmus hat also im Durchschnitt lineare Laufzeit.
Beispiel: In obigem Beispiel tritt das a mit der Wahrscheinlichkeit 0,6 im Text auf, das b mit der Wahrscheinlichkeit 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 Wahrscheinlichkeitsverteilung 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 ≤ 1 + 0,6 + 0,62 + 0,63 + ... ≤ 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 Wahrscheinlichkeit 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
Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
Weiter mit: [Nicht ganz so naiver Algorithmus] oder [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 22.02.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden