Time-space-Optimal String Matching nach Zvi Galil und Joel SeiferasChris Schwiegelshohn Katja Losemann
Time-space-Optimal String Matching nach Zvi Galil und Joel Seiferas
Chris Schwiegelshohn Katja Losemann
‹#›
Geg.: Suchtext y und Muster x p Position im Suchtext und q Position im Muster Init: p=0 und q=0 loop { while y(p + q + 1) == x(q + 1) do q = q +1; p = p‘; q = q‘; } goto loop
Stringalgorithmus
‹#›
Varianten
Nur über Berechnung von p‘ und q‘! Naiv: p‘ = p + 1 und q‘ = q + 1 Knuth-Morris-Prat berechnet p‘ = p + shiftx(q) und q‘ = q - shiftx(q), wobei shiftx(q) = min{shift > 0 |[shift,q] x= [0,q-shift]x}
‹#›
Aufwand von String Matching
String-matching Algorithmen: Entweder: in linearer Zeit (Knuth-Morris) Oder: ohne Speicherplatzbedarf (naiv) Jetzt: Beides
‹#›
Terminologie
k: beliebig, fest und hinreichend groß z und w Strings w(i): i-ter Buchstabe von Wort w z ist Periode von w, wenn w Präfix von z∞ z ist einfach, wenn für kein i>1 z‘i = z gilt z ist Präfix-Periode von w, wenn w einfach ist und zk ein Präfix von w ist,
‹#›
(ab) 3= ababab ist nicht einfach abababa ist dagegen einfach Beide Strings haben dieselben Perioden ab, abab, ababab und sogar abababa String w = (abababa) k ∘ abab besitzt mit k>=4 die Präfix-Periode abababa und mit k=3 auch ab
Beispiele
‹#›
Weitere Terminologie
Gegeben String w und p <= |w| Funktion reachw(p): reachw (p) = max{q‘ <= |w| | [0,p] wist Periode von [0,q‘]w}
‹#›
Beispiele
String w = (abababa) k ∘ abab reachw (1) = 1 reachw (2) = 7 reachw (7) = |w|
‹#›
Sei x ein String mit Länge: p1+ p2 und habe x Perioden der Länge p1 und p2, dann hat x eine Periode der Länge des GGT(p1,p2)
Perioden Lemma
‹#›
Verschiedene Präfix-Perioden desselben Strings, haben mindestens verschiedene Längen eines Faktor von (k-1). Es gilt: Sei w String mit Präfix-Periode mit Länge p1 und einem einfachen Präfix der Länge p2 > p1 mit reachw (p2) = k‘*p2, dann ist p2 > (k-1)p1.
Korollar
‹#›
Geg.: Suchtext y und Muster x p Position im Suchtext und q Position im Muster Init: p=0 und q=0 loop { while y(p + q + 1) == x(q + 1) do q = q +1; p = p‘; q = q‘; } goto loop
Stringalgorithmus
‹#›
Neue Definition
(p‘,q‘) = (p + shiftx(q), q – shiftx(q)), wenn shiftx (q) ≤ q/k = (p + max(1, ⌈q/k⌉), 0) sonst Fall 1 benötigt zusätzlichen Speicherplatz! Können wir den Fall 1 vermeiden?
‹#›
Vorgehen
Leider nicht ganz Ist k groß, dann sollte der erste Fall relativ selten vorkommen. Es lässt sich ein Zusammenhang zwischen der Häufigkeit von shiftx (q) ≤ q/k und Präfix-Perioden des Suchmusters x erstellen.
‹#›
Vorkommen von shiftx(q) ≤ q/k
Lemma 1: Wenn shiftx(q)<=q/k , dann [0, shiftx(q)] x Präfix-Periode von x. Lemma 2: Wenn [0, shiftx(q)] x Präfix-Periode von x, dann shift = shiftx(q) <= q/k k * shift <= q <= reachx (shift)
‹#›
Suche nach einem festen Muster
Dekompositions Theorem: Jedes Muster x kann in Strings u und v aufgeteilt werden, so dass x = uv und v hat maximal eine Präfix-Periode und |u| = O(shiftv( |v| )) Beweis: Klemmen wir uns
‹#›
Die große Zusammenführung 1
Idee des Algorithmus ist, nach Vorkommen von Suffix v zu suchen Fall 1: v hat keine Präfix-Periode ⇒ Wegen Lemma 1 kann shiftx (q) ≤ q/k nicht eintreten ⇒ ( p‘ , q‘ ) = ( p + max ( 1 , ⌈q/k⌉ , 0 )
‹#›
Die große Zusammenführung 2
Fall 2: v hat genau eine Präfix-Periode der Länge p1. Wegen Lemma 2 gilt shiftx (q) ≤ q/k genau dann wenn k ⋅ p1 ≤ q ≤ reachv(p1) Also gilt: ( p‘ , q‘ ) = ( p + shiftx(q) , q - shiftx(q) ) = ( p + p1, q – p1 )
‹#›
Laufzeit und Analyse
Suche nach Suffix v: f(p,q) = a1 * p + a2 * q = O(|y| + |v|) Wähle a1 und a2 geschickt, so dass die Funktion linear steigt Suche nach u: Wegen des DekompositionsLemmas kann u in y nur |y| / shift(v) häufig vorkommen und somit in O(|y|). Suche daher naiv. Insgesamt: O(|v| + |y|) = O(|x| + |y|)
‹#›
Speicherplatzbedarf: Da wir nur eine Präfix Periode haben konstant! FERTIG !
Comments