Laufzeit naives Stringmatching

Michamab

Hallo,

in der Uni bin auch eine Übungsaufgabe gestoßen, bei der ich einfach auf dem Schlauch stehe. Es geht um die Bestimmung der Laufzeit eines naiven Stringmatching-Algorithmus.

Der Algorithmus sucht der mit der Brute-Force-Methode alle Vorkommen eines Pattern in einem Text. Das gesuchte Wort wird zuerst an der ersten Stelle des Textes angelegt und Zeichen für Zeichen verglichen. Stimmt ein Zeichen nicht überein, so wird die Schleife abgebrochen und das Wort eine Position "weitergeschoben". Anschließend wird der erste Schritt wiederholt.

Hier nochmal als Pseudocode, falls die Beschreibung nicht verständlich war:

String-Matching(T, P)
  n <- laenge[T]
  m <- laenge[P]
  for s <- 0 to n - m
     do if P[1 .. m] = T[s + 1 .. s + m]
        then print "Muster mit Verschiebung " s " gefunden"

n = Länge des Textes
m = Länge des Wortes

Recht trivial lässt sich sagen, dass die Laufzeit im Bezug auf die Vergleiche O(n*m) beträgt. Bzw. genauer O((n - m + 1) * m). Ich streiche jedoch den konstanten Teil.

Nun soll ich diese Aussage jedoch konkretisieren. Gegeben ist, dass jeder Buchstaben an jeder Stelle des Textes mit gleicher Wahrscheinlichkeit vorkommt. Wenn Σ unser Alphabet ist, dann beträgt die Wahrscheinlichkeit, dass der gerade untersuchte Buchstabe übereinstimmt 1/|Σ|. Dann lässt sich für die Laufzeit O(n * (1/|Σ|)^m) schlussfolgern.

Dies ist jedoch leider nicht genug. Da ich zeigen soll, dass man bei jedem erneuten Anlegen des Musters an den Text nach erwartet konstant vielen Vergleichen ein Mismatch erhält, muss ich einen Wert finden, wie viele Vergleiche im Mittel pro Anlegen benötigt werden.

Dies ist mir jedoch absolut nicht klar. Mir mangelt es hierbei wohl an ausreichendem mathematischen Verständnis. Ich würde mich über Tipps oder andere Hilfe freuen.

Michael E.

Michamab schrieb:

Nun soll ich diese Aussage jedoch konkretisieren. Gegeben ist, dass jeder Buchstaben an jeder Stelle des Textes mit gleicher Wahrscheinlichkeit vorkommt. Wenn Σ unser Alphabet ist, dann beträgt die Wahrscheinlichkeit, dass der gerade untersuchte Buchstabe übereinstimmt 1/|Σ|. Dann lässt sich für die Laufzeit O(n * (1/|Σ|)^m) schlussfolgern.

Das würde ich nicht sagen. Denn mit wachsendem m würde sich deine Laufzeit exponentiell beschleunigen, was sicher nicht der Fall sein kann.

Betrachte die Anzahl Vergleiche in einer Iteration als geometrisch verteilte Zufallsvariable. Dann hast du im Erwartungswert min{m, |Σ|/(|Σ|-1)} viele Vergleiche pro Iteration ("Erfolg" der geometrisch verteilten Zufallsvariable heißt, dass zwei Zeichen nicht übereinstimmen). Also kommst du wieder auf auf O(n*m).

Dies ist jedoch leider nicht genug. Da ich zeigen soll, dass man bei jedem erneuten Anlegen des Musters an den Text nach erwartet konstant vielen Vergleichen ein Mismatch erhält,

Gerade getan.

muss ich einen Wert finden, wie viele Vergleiche im Mittel pro Anlegen benötigt werden.

Ebenso.

Michamab

Michael E. schrieb:

Michamab schrieb:

Nun soll ich diese Aussage jedoch konkretisieren. Gegeben ist, dass jeder Buchstaben an jeder Stelle des Textes mit gleicher Wahrscheinlichkeit vorkommt. Wenn Σ unser Alphabet ist, dann beträgt die Wahrscheinlichkeit, dass der gerade untersuchte Buchstabe übereinstimmt 1/|Σ|. Dann lässt sich für die Laufzeit O(n * (1/|Σ|)^m) schlussfolgern.

Das würde ich nicht sagen. Denn mit wachsendem m würde sich deine Laufzeit exponentiell beschleunigen, was sicher nicht der Fall sein kann.

Aber mit wachsendem m wird der Term (1/|Σ|)^m doch immer kleiner? Intuitiv würde ich das auch als logisch empfinden, da die Wahrscheinlichkeit ein Matching zu haben mit wachsenden m auch kleiner wird, da jeder Buchstabe mit gleicher Wahrscheinlichkeit an der jeweiligen Position vorkommt.

Michael E.

Michamab schrieb:

Aber mit wachsendem m wird der Term (1/|Σ|)^m doch immer kleiner?

Ja.

Intuitiv würde ich das auch als logisch empfinden, da die Wahrscheinlichkeit ein Matching zu haben mit wachsenden m auch kleiner wird, da jeder Buchstabe mit gleicher Wahrscheinlichkeit an der jeweiligen Position vorkommt.

Nach der Wahrscheinlichkeit für ein Matching ist aber nicht gefragt, sondern nach der Laufzeit. Wenn dein Wort länger ist, hast du auch mehr zu überprüfen.

Ein Beispiel: Σ = {0,1}, T = 0^n-11 (also n-1 Nullen gefolgt von einer 1), P = 0^n/21. Dann musst du in jeder Iteration n/2 + 1 Vergleiche machen. Insgesamt hast du n/2 Iterationen (plus minus 1, bin zu faul zum Rechnen ;)), also eine Gesamtlaufzeit von n^2/4.

Michamab

Oh logisch. Danke!