Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Algorithmen und Datenstrukturen 1 Kapitel 6 Robert Giegerich und Jens Stoye Technische Fakultät Universität Bielefeld [email protected] Vorlesung, U. Bielefeld, Winter 2008/2009 Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Kapitel 6: Algorithmen auf Zeichenreihen Anwendungsgebiete Verarbeitung von Zeichenreihen ist wichtiges Teilgebiet der Informatik, z.B. Erstellen, Durchsuchen, Archivieren von Dokumenten Text-Kompression & Datenkompression (auf allen digitalen Übertragungswegen) Genomforschung: Genome, Gene; Proteindatenbanken Internet-Suchmaschinen Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Fragestellungen Suchen (Muster P in Text T ) Vergleichen (Text S gegen Text T ) Clustering und Klassifizierung von Mengen von Zeichenreihen Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Logische Varianten Exakte Suche oder Vergleich (Ja/Nein; alle Auftreten/ein Auftreten) Approximative Suche oder Vergleich (kleine Abweichungen erlaubt – bester Treffer gesucht) Paarweiser vs. multipler Vergleich Einfache vs. multiple Mustersuche Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Technische Varianten z.B. bei Mustersuche 1 beide P und T variabel: “naive” Verfahren 2 P bekannt, T variabel: generiere spezielles Suchverfahren (“Matcher”) für M in wechselnden Texten T 3 P variabel, T (relativ) stabil: generiere Index-Struktur zum schnellen Durchsuchen für wechselnde P Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus z.B. beim Vergleichen 4 beide Texte etwa gleich groß – Vergleich über volle Länge 5 beste lokale Ähnlichkeit. (Was ist die ähnlichste Tonfolge in zwei Musikstücken?) 6 kleiner Abschnitt in langem Text. (Z.B. wird “Giegerich” in der Bibel nicht erwähnt. Was ist die dazu ähnlichste Zeichenreihe, die darin vorkommt?) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus z.B. bei großen/komprimierten Texten 7 online-Verfahren: Text wird nur einmal gelesen, von links nach rechts 8 residente Verfahren: ganzer Text muss gleichzeitig verfügbar sein für Zugriffe in beliebiger Folge Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Mehr Beispiele zu 1 – 8 1 Text-Editor: Finde alle Auftreten eines Wortes; ersetze durch ein anderes 2 Übersetzung von Programmiersprachen: Erkennung der lexikalischen Grundsymbole der Sprache in Programmen (Lexikalische Analyse als 1. Stufe der Syntaxanalyse) 3 Suche nach Stichworten im Werk von Shakespeare; Suche nach DNS-Muster (“ACGTAACCTTA”) im menschlichen Genom (3.3 GB) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus 4 Textvergleich abgeschriebener (?) Hausaufgaben; Vergleich zweier orthologer Gene (ortholog: verwandt durch Abstammung) 5 Aussortieren von Zerfallsprodukten der RNS; (sie sind Teile längerer Sequenzen; siehe auch 3) 6 Suche nach “Raubkopien” von Musikstücken 7 Komprimieren/Dekomprimieren auf Übertragungswegen; Verschalten von Programmen als Unix “pipes”; “Listlessness” bei funktionalen Programmen 8 Komplexere Suchmusteranfragen, z. B. verteilte Repeats im menschlichen Genom Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Effizienz-Betrachtungen Hier eine allgemeine Vorausbetrachtung zur Effizienz – noch haben wir keine Algorithmen gesehen. Sei |P| = m, |T | = n. Untergrenze der worst-case Effizienz: O(m + n) bzw. denn alle Zeichen im Muster/Text müssen mindestens einmal gelesen werden. O(m · n) ist trivial erreichbar bei Vorverarbeitung von Muster oder Text muss Generierungsaufwand gegen verbesserten Suchaufwand abgewogen werden (amortisierte Effizienz) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Untergrenze für das Finden von P nach Vorverarbeitung von T ist O(m) – das wäre unabhängig von der Größe des Textes! Eine Besonderheit wird wichtig bei sehr großen Texten: Größe des Index kann kritisch werden. Das Lokalitätsverhalten der Indexkonstruktion und der Suche spielt eine Rolle in Rechnern mit Cache-Architektur (Thrashing) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Konstante Faktoren Der Vergleich zweier Zeichen ist charakteristische Operation Ansonsten wird kaum etwas gerechnet Konstante Faktoren sind generell gering, asymptotische Laufzeit ist hartes Kriterium Ausnahme: Thrashing-Phänomene Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus 6.2 Grundlegende Definitionen Die Suche nach allen (exakten) Vorkommen eines Musters in einem Text ist ein Problem, das häufig auftritt (z.B. in Editoren, Datenbanken etc.). Wir vereinbaren folgende Konventionen: Alphabet Σ Muster P Text T P[j] P[b..e] = = = = endlicher Zeichenvorrat P[0..m − 1] ∈ Σm T [0..n − 1] ∈ Σn Zeichen an der Position j Teilwort von P “von bis” den Positionen b und e Beispiel P = abcde, P[0] = a, P[3] = d, P[2..4] = cde. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Notation: leeres Wort: Länge eines Wortes x: |x| Konkatenation zweier Wörter x und y : xy Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Präfix und Suffix Sei x = uvw , mit u, v , w ∈ P∗ . Dann heißt u Präfix von x, v Teilwort von x und w Suffix von x. Beachte: “abc” hat Präfixe , “a”, “ab”, “abc” und die Suffixe “abc”, “bc”, “c”, . Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Das Problem der exakten Suche Definition Ein Muster P kommt mit der Verschiebung s im Text T vor, falls 0 ≤ s ≤ n − m und T [s..s + m − 1] = P[0..m − 1] gilt. In diesem Fall nennen wir s eine gültige Verschiebung. Das Problem der exakten Textsuche ist, alle gültigen Verschiebungen zu finden. Man kann auch sagen: Finde alle Suffixe von T , die P als Präfix haben. Beispiel T = bielefeld oh bielefeld P = feld Gültige Verschiebungen: s = 5 und s = 18. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Die naive Lösung des Problems sieht so aus: naive1 p t = [i|i <- [0..length t - 1], p == take (length p) (drop i t)] Diese Lösung ist offensichtlich NICHT effizient – sie führt zum Aufwand O(n2 + 2nm) wegen der Aufrufe von drop. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Besser ist die Variante naive2 p t = [i|(i,w) <- zip [0..] where m = length p (suffixes t), p == take m w] suffixes [] = [[]] suffixes (x:xs) = (x:xs) : suffixes xs Hier ist der worst-case Aufwand O(m · n) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Am Beispiel T = abrakadabraxasa und P = abraxas erkennt man das ineffiziente Vorgehen, insbesondere wenn Text und Muster immer komplett verglichen werden: a b r a k a d a b r a x a s a | | | | o | o a b r a x a s o o o o o o o - a b r a x a s o o o | o | o - a b r a x a s | o o o o o o - a b r a x a s o o o | o o o - a b r a x a s | o o o o | o - a b r a x a s o o o o o o o - a b r a x a s | | | | | | | - a b r a x a s o o o o o o o - a b r a x a s Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Selbst wenn Text und Muster zeichenweise von links nach rechts und nur bis zum ersten Mismatch1 verglichen werden, ist die worst-case Zeiteffizienz des naiven Algorithmus O n · m , z.B. wird für T = an , P = am der Vergleich p = . . . n − m + 1 mal ausgeführt und in jedem Test in werden m Zeichen verglichen. Wie kann man den naiven Algorithmus verbessern? Idee 1: Überspringe ein Teilwort w von T , falls klar ist, dass w 6= P (BM-Algorithmus 1977). Idee 2: Merke Informationen über bisherige Vergleiche und nutze diese, um neue, unnötige Vergleiche zu vermeiden (KMP-Algorithmus 1977). 1 Die zwei Zeichen stimmen nicht überein. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus 6.3 Der Boyer-Moore-Algorithmus Der BM-Algorithmus legt wie der naive Algorithmus das Muster zunächst linksbündig an den Text, vergleicht die Zeichen des Musters dann aber von rechts nach links mit den entsprechenden Zeichen des Textes. Beim ersten Mismatch benutzt er zwei Heuristiken, um eine Verschiebung des Musters nach rechts zu bestimmen. Beispiel: T = RHABARBERBARBARA P = BARBIER Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Die bad-character Heuristik Falls beim Vergleich von P[0..m − 1] und T [s..s + m − 1] (von rechts nach links) ein Mismatch P[j] 6= T [s + j] für ein j mit 0 ≤ j ≤ m − 1 festgestellt wird, so schlägt die bad-character Heuristik BCH(T [s + j]) eine Verschiebung des Musters um j − k Positionen vor, wobei k der größte Index (0 ≤ k ≤ m − 1) ist mit T [s + j] = P[k]. Wenn kein k mit T [s + j] = P[k] existiert, so sei k = −1. BCH wird vor Beginn der Suche berechnet!! Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus h i n o BCH T [s + j] = max k|P[k] = T [s + j] 0≤km−1 Berechne: ∀a ∈ X Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 BCH[a] = max 0≤km−1 n o k|P[k] = a Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Einfacher gesagt: T [s + j] ist der “bad character”. Wir verschieben das Muster so, dass das rechteste Auftreten des bad character im Muster, also P[k], unter T [s + j] liegt. Problem: Wenn k > j, würde das Muster nach links verschoben! Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Die good-suffix Heuristik Falls beim Vergleich von P[0..m − 1] und T [s..s + m − 1] (von rechts nach links) ein Mismatch P[j] 6= T [s + j] für ein j mit 0 ≤ j ≤ m − 1 festgestellt wird, so wird das Muster so weit nach rechts geschoben, bis das bekannte Suffix T [s + j + 1..s + m − 1] wieder auf ein Teilwort des Musters passt. Im Boyer-Moore-Algorithmus wird das Muster um das Maximum von beiden vorgeschlagenen Verschiebungen verschoben. Es kann gezeigt werden, dass die Laufzeitkomplexität dann im worst case O(n + m) ist. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen Vorverarbeitungsschritte: Bad character Heuristik: Good suffix Heuristik: Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Die Verschiebespannen beider Heuristiken werden vorab durch Analyse von P ermittelt und tabelliert P BCH: → [−1..m − 1] BCH(a) = k gdw. k ist rechtestes Auftreten von a in P; oder k = −1 GSH: [0..m − 1] → [−1..m − 1] GSH(j) = max r : P[r ..r + (m − 1)− (j + 1)] = P[j + 1..m − 1] oder r = −1 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Beispiel Die bad-character Heuristik schlägt eine Verschiebung von j − k = (m − 3) − 5 = (12 − 3) − 5 = 4 Positionen vor; dies ist im Fall (b) illustriert. Aus der Darstellung (c) wird ersichtlich, dass die good-suffix Heuristik eine Verschiebung von 3 Positionen vorschlägt. Also wird das Muster um max{4, 3} = 4 Positionen nach rechts verschoben. bad character ... w r i t t e n s good suffix ? ?z }| { n o t i c e o t h a t ... - r e m i n i s c e n c e (a) ... w r i t t e n s+4 n o t i c e t h a t ... - r e m i n i s c e n c e (b) ... w r i t t e n s+3 n o t i c e t h a t ... - r e m i n i s c e n c e (c) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Ein Beispiel, in dem die Bad-Character-Heuristik eine Verschiebung nach links (negativ) vorschlägt: ... R H A B A R B E R B A R B A R A B R A ... B I E R B A R 6 rechtes Auftreten von t in P 6 bad character t ergibt Verschiebung −3! Good suffix Heuristik: Verschiebung +7. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Wirksamkeit der Heuristiken: lange gute Suffixe sind selten, in der Regel beruhen große Verschiebungen auf der bad-character Heuristik Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Der Boyer-Moore-Horspool-Algorithmus Der BM-Algorithmus verdankt seine Schnelligkeit vor allem der bad-character Heuristik. Daher wurde 1980 von Horspool eine Vereinfachung des BM-Algorithmus vorgeschlagen: Die bad-character Heuristik wird derart modifiziert, dass sie immer eine positive Verschiebung vorschlägt. Damit wird die good-suffix Heuristik überflüssig (und auch die Vorverarbeitung einfacher). Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Der Boyer-Moore-Horspool-Algorithmus Der BMH-Algorithmus geht in den meisten Fällen analog zur bisherigen bad-character Heuristik vor. Aber: Falls P[j] 6= T [s + j] für ein j (0 ≤ j ≤ m − 1) gilt, so wird s um m − 1 − k erhöht, wobei k der größte Index zwischen 0 und m − 2 ist mit T [s + m − 1] = P[k]. Wenn kein k (0 ≤ k ≤ m − 2) mit T [s + m − 1] = P[k] existiert, so wird s um m erhöht. Das Muster wird also um “ ˆ ˜ ˘ ¯” λ T [s+m−1] = min {m}∪ m−1−k | 0 ≤ k ≤ m−2 und T [s+m−1] = P[k] verschoben. Wenn ein Match gefunden wurde, dann wird ebenfalls um λ T [s + m − 1] verschoben. Vorverarbeitung: λ[c] für alle c ∈ Σ. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Verhalten des BMH-Algorithmus bei einem Mismatch ... g o l d e n s- f l e e c e o o f ... r e m i n i s c e n c e ⇓ ... g o l d e n s+3 Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 f l e e c e o f ... - r e m i n i s c e n c e Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Verhalten des BMH-Algorithmus bei einem Treffer ... g o l d e n s f l e e c e o f ... - f l e e c e ⇓ ... g o l d e n s+2 Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 f l e e c e o f ... - f l e e c e Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Boyer-Moore-Horspool Algorithmus in Haskell import Array Eine halbherzige Lösung lambda :: String -> String -> Int -> Int lambda p t s = minimum (m:[m-1-k | k <- [0..(m-2)], t!!(s+m-1) == p!!k]) where m = length p bMh :: String -> String -> [Int] bMh p t = bmh’ 0 p t where bmh’ i p t | i > (length t)-(length p) = [] | p == (take (length p) (drop i t)) = i:(bmh’ (i + lambda p t i) p t) | otherwise = bmh’ (i + lambda p t i) p t Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Kritik: 1 Die Repräsentation von Muster und Text als String statt als Array verhindert das Erreichen guter Effizienz. 2 Die Verschiebefunktion λ wird nicht vorab berechnet, sondern bei jedem Gebrauch neu. 3 Für die lokale Funktion bmh’ sind p und t bekannt. Es ist unnötig, sie jedesmal als (unveränderte) Parameter zu übergeben. 4 λ sollte lokale Funktion von bmh sein, da auch dafür p und t konstant sind. 5 Eine zentrale BMH-Idee ist, dass λ(a) für alle a aus [’A’..’z’] berechnet wird. Dadurch wird λ unabhängig von Text t!! Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Eine korrekte Lösung type SArr = Array Int Char bmh:: SArr -> SArr -> [Int] bmh p t = bmhi 0 m where ( ,m) = bounds p ( ,n) = bounds t bmhi i k |i+m >n = [] |k == 0 = [i|t!i == p!0]++ bmhi (i+shift!(t!(i+m))) m |t!(i+k) == p!k = bmhi i (k-1) |otherwise = bmhi (i+shift!(t!(i+m))) m shift shift [0..m-1]] :: Array Char Int = accumArray min (m+1) (’A’,’z’) [(p!k,m-k)|k <- Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Zum Aufruf mit zwei Strings tbmh p t = bmh (mk p) (mk t) where mk s = listArray (0,length s -1) s Zum separat Angucken eine ent-lokalisierte Kopie von shift shift shift p :: SArr -> Array Char Int = accumArray min (m+1) (’A’,’z’) [(p!k,m-k)|k <- [0..m-1]] where ( ,m) = bounds p Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus 6.4 Der Knuth-Morris-Pratt-Algorithmus Der naive Algorithmus: a b r a | | | | a b r a o -a b r o -a b | -a k a d a b e r a b r a k a d a b r a k a b r a k a d a b r a | | | | | o k a d a b r a a k a d a b r a r a k a d a b r a o b r a k a d a b r a etc. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Man erkennt, dass im zweiten und dritten Schritt das Zeichen a an Position 1 im Muster mit den Zeichen b und r an der zweiten und dritten Position des Textes verglichen wird, obwohl bereits nach dem positiven Vergleich von abra klar sein musste, dass hier keine Übereinstimmung existieren kann. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Der Knuth-Morris-Pratt-Algorithmus geht nach folgendem Schema vor: Wenn ein Teilwort (Präfix) des Musters bereits erkannt wurde, aber dann ein Mismatch auftritt, so ermittelt der Algorithmus das längste Präfix dieses Teilwortes, das gleichzeitig echtes Suffix davon ist, und schiebt das Muster dann so weit nach rechts, dass dieses Präfix an der bisherigen Position des Suffixes liegt. a b r a k a d a b e | | | | | | | | | o a b r a k a d a b r o -a b r o -a r a b r a k a d a b r a k a b r a k a d a b r a a a k a d a b r a b r a o -a b r | | -a b k a d a b r a a k a d a b r a | | | | | | | | | r a k a d a b r a | | o -a b r a k a d a b r a | | | | | | | | | | -a b r a k a d a b r a Man erkennt, dass hier drei unnötige Vergleiche vermieden wurden. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Beispiel: Die Präfixfunktion π : {1, 2, . . . , m} → {0, 1, . . . , m − 1} für ein Muster P[0..m − 1] ist definiert durch π[q] = max{k : k < q − 1 und P[0..k] ist echtes Suffix von P[0..q − 1]}. Sie lautet für unser Beispielwort P = abrakadabra: q P[q] π[q] 0 a ⊥ 1 b 0 2 r 0 3 a 0 4 k 1 5 a 0 6 d 1 7 a 0 8 b 1 9 r 2 10 a 3 11 ⊥ 4 Für q = 9 wäre das entsprechende Teilmuster also abrakadab. Das längste Präfix, das gleichzeitig echtes Suffix davon ist, ist ab. Es hat die Länge 2, darum findet sich in der Tabelle an der Position q = 9 der Eintrag π[q] = 2. P wird so verschoben, dass P[π(q)] unter der Mismatch-Position in T steht, d. h. S 7−→ S + q − π[q]. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Berechnung der Präfixfunktion für KMP Vorgehen: induktiv Annahme: Die Werte von π sind bereits für 1 . . . q − 1 berechnet. Gesucht: π[q] = max{k | k < q und P[0..k − 1] ist echtes Suffix von P[0..q − 1]}. Welche k kommen in Frage? → alle echten Suffixe von P[0..q − 2], die sich zu einem echten Suffix von P[0..q − 1] erweitern lassen. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus (a) 0 k1−2 k−1 1 q−2 q−1 x k1 x k1 Sei k1 = π[q − 1] + 1 Dann ist π[q] = k1 falls, P[k1 − 1] = P[q − 1]. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus (b) andernfalls (y 6= x): k1−1 k 2−1 y x k2 q−2 q−1 k2 x k2 Sei k2 = π[k1 − 1] + 1. Dann ist π[q] = k2 , falls P[k2 − 1] = P[q − 1]. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Allgemein: ki =π[ki−1 −1]+1=π[π[ki−2 −1]+1−1]+1=···=π[π[ki−2 −1]]+1 ki =π i [q−1]+1 Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus KMP-Algorithmus in Haskell import Array Eine halbherzige Lösung für KMP (einschließlich einer besonders peinlichen Implementierung von suffixes) Pi-Funktion für den KMP: pi’ :: String -> Array Int Int pi’ p = array (1,qmax) [ (q, maximum [ k | k <- [0..q], (take k p) ‘elem‘ (suffixes (take q p)) ]) | q <- [1..qmax] ] where qmax = (length p) Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Gibt alle echten Suffixe eines Worts inklusive des leeren Worts aus: suffixes :: [a] -> [[a]] suffixes as = [ (drop n as) | n <- [1..(length as)] ] Gibt die Stelle des ersten unterschiedlichen Zeichens in zwei gleich langen Strings aus: getQ :: String -> String -> Int getQ a b = getQ’ 0 a b where getQ’ i (a:as) (b:bs) = if a/=b then i else getQ’ (i+1) as bs getQ’ i [] [] = i Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Führt den KMP aus: kMp :: String -> String -> [Int] kMp [] = error "ungueltiger Suchstring" kMp p t = kmp’ 0 p t where kmp’ i p t | i > lt-m = [] | q == m && k’ == 0 = i:kmp’ (i + m) p t | q == m && k’ > 0 = i:kmp’ (i + m - k’) p t | q < m && p!!q /= t!!(i+q) && q /= 0 = kmp’ (i + q - pq) p t | q < m && p!!q /= t!!(i+q) && q == 0 = kmp’ (i+1) p t where q = getQ p (take m (drop i t)) k’ = pit!m pq = pit!q pit = pi’ p lt = length t m = length p Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Kritik: 1 Darstellung von Text und Muster als String (statt Array) torpediert die Effizienz. 2 Suffixes haben wir in den Übungen schon eleganter implementiert – diese Implementierung ist in O(n2 )! 3 getQ vergleicht im Muster jedesmal von ganz vorne, das stimmt nicht mit der KMP-Idee überein. 4 kmp’ als lokale Funktion von KMP braucht keine Parameter p und t. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Eine korrekte Implementierung von KMP type SArr = Array Int Char kmp p t = kmp’ 0 0 where ( ,m) = bounds p ( ,n) = bounds t kmp’ i q | i+m > n = [] | q == m+1 = i:kmp’(i+q-pi!q) (pi!q) -- i+q bleibt invariant! | t!(i+q) == p!q = kmp’ i (q+1) -- q rueckt vor | q == 0 = kmp’ (i+1) 0 -- i rueckt vor |otherwise = kmp’ (i+q-pi!q) (pi!q) -- i+q bleibt invariant! pi :: Array Int Int pi = array (0,m+1) ((0,0):(1,0):[(q,iteratep (pi!(q-1)) q)| q <- [2..m+1]]) where iteratep 0 q = if p!0 == p!(q-1) then 1 else 0 iteratep k q = if p!k == p!(q-1) then k+1 else iteratep (pi!k) q Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Zum Aufruf von kmp mit zwei Strings tkmp p t = kmp (mk p) (mk t) where mk s = listArray (0,length s -1) s Ent-lokalisierte Version von pi zum Reingucken pTab p = pi where ( ,m) = bounds p pi = array (0,m+1) ((0,0):(1,0):[(q,iteratep (pi!(q-1)) q)| q <- [2..m+1]]) iteratep 0 q = if p!0 == p!(q-1) then 1 else 0 iteratep k q = if p!k == p!(q-1) then k+1 else iteratep (pi!k) q mk s = listArray (0,length s -1) s Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Ein Wettrennen zwischen KMP und BMH 1. Satz: 0:1 tkmp "accgagt" "aatcgtagagctagcatgatgtatatagcgccggcgtatagctaagcaccgataccgagtcxgaagcta" [53] (11975 reductions, 15574 cells) tbmh "accgagt" "aatcgtagagctagcatgatgtatatagcgccggcgtatagctaagcaccgataccgagtcxgaagcta" [53] (7473 reductions, 9958 cells) 2. Satz: 1:0 tkmp "abbaba" "abbababbbabaaababababbabbabbabbabababbbbabbaaaaababaabbab" [0,28] (10881 reductions, 14126 cells) tbmh "abbaba" "abbababbbabaaababababbabbabbabbabababbbbabbaaaaababaabbab" [0,28] (12374 reductions, 15919 cells) 3. Satz: 0:1 kmp "WerdurchTesten" "Programmeverstehenwilldermussschonsehrvielmessenundganzgenauhinsehen" [] (8068 reductions, 10646 cells) tbmh "WerdurchTesten" "Programmeverstehenwilldermussschonsehrvielmessenundganzgenauhinsehen" [] (5979 reductions, 8064 cells) Ergebnis:..................... Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 KMP : BMH 1:2 .................................... Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus KMP-Algorithmus als Automat mit spontanen Übergängen (ohne Kantenmarkierung; ohne Weitergehen im Text) Jeder Zustand entspricht einem erkannten Präfix; die Nummer ist q aus der π-Tabelle b =a a ab 2 r abr 3 a abra 4 k abrak 5 a abraka 6 a 1 d ε abrakad 7 0 abrakadabra 11 a abrakadabr 10 r abrakadab 9 b abrakada 8 a Speicherplatz für den KMP-Automat: O(|P|) für die Tabelle der Spontanübergänge. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus Transformation des KMP-Automaten in einen endlichen Automaten (Zusammenziehen der spontanten Übergänge, so dass bei jedem Übergang ein Zeichen gelesen wird) = a,r b a ε abr 3 r ab 2 a =a = a,b,k =a abra 4 b k = a,b,d abrak 5 a a a a 1 =a a b a d = a,b abrakad 7 0 a = a,b,k abraka 6 b k abrakadabra 11 a a abrakadabr 10 =a r a abrakadab 9 b abrakada 8 = a,r Speicherplatz für endlichen Automat: O(| Kombinationen von Zeichen und Zustand. Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 =a a = a,b P | · |P|) für alle Universität Bielefeld Algorithmen auf Zeichenreihen Grundlegende Definitionen BM-Algorithmus BMH-Algorithmus Der KMP-Algorithmus 6.5 Aho-Corasick Bei mehr als einem Muster bilden alle Präfixe aller Muster die Zustandsmenge des Aho-Corasick-Automaten. Beispiel: P1 = abra, P2 = abba, P3 = brabra. r a a = a,b ε a abr abra ab b b abb a abba b b r Robert Giegerich und Jens Stoye A&D 1 Vorlesung Winter 2008/2009 br a bra b brab r brabr a brabra Universität Bielefeld
© Copyright 2024 ExpyDoc
