Suche Home Einstellungen Anmelden Hilfe  

1.3.1 Beispiel

Die Mustersuche in Strings, in Zeichenketten, wird in vielen Bereichen verwendet. Textverarbeitungsprogramme, Suchmaschinen des Internets nutzen es, aber auch zum Auffinden von Gensequenzen oder Molekülstrukturen wird der Mustervergleich herangezogen. Ein solcher, alltäglicher und häufig genutzter Vorgang sollte dementsprechend nur wenig Zeit in Anspruch nehmen.

Voraussetzungen: Seien der Text A = a1a2...an und das Muster B=b1b2...bm mit n≥m Zeichenketten über einem endlichen Alphabet. Gesucht ist das erste Vorkommen von B in A, gekennzeichnet durch den Index i (Beginn des Musters im Text).
Das folgende Programm ist Pascal-ähnlich für das Registermaschinenmodell kodiert.

function bruteforce ( a, b: string; n, m: integer): integer;
(*liefert Beginn des Musters oder -1, wenn b in a nicht vorkommt*)
var: i, j: integer;
begin
i := 1;
j := 1;
repeat
    if ai=bj then begin
      inc(i);
      inc(j);
    end
    else begin
      i := i - j + 2; (*i wird zurückgesetzt, an Teilstring Vergleichsanfang + 1*)
      j := 1; (*Musterzeiger auf Anfang gesetzt*)
    end;
until (j>m) or (i>n-m+1);
(*b in a gefunden/ kein Vorkommen von b in a*)
if j>m
    then bruteforce := i - m;
    else bruteforce := -1
end;

Die Funktion 'bruteforce' ist ein sehr einfaches Suchverfahren. Sie vergleicht Muster und Text Zeichen für Zeichen beginnend von links. Tritt ein mismatch auf, d.h. stimmen die verglichenen Zeichen nicht überein, so wird der weitere Mustervergleich abgebrochen. Das Muster wird um eine Stelle nach rechts verrückt und der Zeichenvergleich beginnt erneut.
Die Komplexität hängt sowohl von der Länge des Textes als auch der des Musters ab.

Zeitkomplexität:
initiale Zuweisungen 1+1
Schleife (im schlechtesten Fall - kein Vorkommen) (n-m+1)-Mal
  Vergleich (im schlechtesten Fall - Rücksetzen auf [anfängliches] i+1 erst beim Vergleich von bm) und Zuweisungen m-Mal und 1+1
Vergleich und Zuweisung 1+1

Zusammen gerechnet führt das Programm somit 2 + (n-m+1)(m+2) + 2 aus. Es liegt in der Größenordnung von O(nm). Die äußere Schleife wird durch das Zurücksetzen von i innerhalb der Schleife ungefähr m*n-Mal ausgeführt. Die Suche von '0001' in '000000000000000001' benötigt die maximale Laufzeit.

Im Regelfall jedoch arbeitet dieses Programm deutlich besser: meist wird schon beim ersten Buchstaben des Musters ein mismatch festgestellt. Der Rumpf der Schleife setzt in so einem Fall den Zähler i nicht wieder zurück.

Speicherbedarf
i, j, m und n sind die benötigten Variablen für Zahlen. Hinzu kommt Speicherbedarf für die beiden Strings. Der Speicherbedarf liegt ungefähr bei n+m.

Der hier angegebene Algorithmus führt den Mustervergleich immer wieder um nur einen Schritt versetzt aus. Dabei werden viele überflüssige Vergleiche gemacht und der Index immer wieder zurückgesetzt, ohne das Wissen aus den bisherigen Vergleichen zu nutzen. Andere Algorithmen zur Mustersuche in Strings nutzen dieses Wissen und müssen den Index an keiner Stelle zurücksetzen. Dafür sind oft Vorarbeiten nötig, die das Muster untersuchen. Um die Untersuchungsergebnisse aufzuheben, ist weiterer Speicherplatz nötig.

Nun noch ein Überblick über die Komplexität von Programmbestandteilen:1
Rechenregeln

Einfache Anweisungen O(1)
Blöcke O(Block)= O(Anweisung_1) + ... + O(Anweisung_n)
for-Schleifen O(1)+ (Ende-Anfang+1)*O(eingeschlossener Block)
while/repeat-Schleifen Induktion über Steuerblock
Verzweigungen O(1)+ O(größerer Block)
Prozedur O(1)+ O(prozedurrumpf)

________
1 Diese Angaben berücksichtigen das universale Kostenmaß. Jede Zuweisung verbraucht eine Einheit der Größe 1 unabhängig von der Größe der Zahl. Beim logarithmischen Kostenmaß wird die Zahlengröße berücksichtigt. Größere Zahlen verbrauchen mehr Zeit.

Übersicht zurück 1   2   3   4   5 weiter Zusammenfassung

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: