Algorithmen und Datenstrukturen 8 String Matching Patrick Horster Universität Klagenfurt Informatik – Systemsicherheit [email protected] 8 String Matching • • • • • • Datentypen und Definitionen Grober Algorithmus Algorithmus nach Knuth-Morris-Pratt Algorithmus nach Boyer-Moore Algorithmus nach Rabin-Karp Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-2 Einleitung Suchen in Texten (lineare, gewöhnlich sehr lange Zeichenfolgen) wird auf das „Pattern-Matching“ (Musteranpassung) zurückgeführt. Pattern-Matching: Gegeben sei eine Text-Zeichenfolge der Länge N und ein Muster der Länge M (i.A. N j M); zu suchen ist ein (das erste) Auftreten des Musters innerhalb des Textes. Problem: Die bisher vorgestellten Such-Algorithmen sind hier nicht hilfreich, denn das Muster ist (wenn überhaupt) an einer beliebigen Stelle im Text enthalten À spezielle Algorithmen notwendig. Erwartete Komplexitäten: • Ideal wäre eine Laufzeit von O(N+M) – also linear. • Im ungünstigsten Fall ist O(N ·M) zu erwarten. • Ist auch O(N/M) erreichbar ? Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-3 Datentypen und Definitionen Texte und Muster werden in Character-Arrays entsprechender Länge abgelegt. Dies ermöglicht den schnellen und einfachen Zugriff auf einzelne Buchstaben. Zur einfacheren Darstellung der Algorithmen werden die einzelnen Zeichen ab Index 1 abgelegt. D.h. Position 0 bleibt ungenutzt und die Arrays müssen wie folgt definiert werden: a = new char[N+1]; p = new char[M+1]; // Text // Muster Eine binäre Zeichenkette ist eine Zeichenkette, die nur zwei unterschiedliche Zeichen (meist ‘0‘ und ‘1‘) enthält. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-4 8 String Matching • Datentypen und Definitionen • Grober Algorithmus – Prinzip – Algorithmus – Analyse • • • • Algorithmus nach Knuth-Morris-Pratt Algorithmus nach Boyer-Moore Algorithmus nach Rabin-Karp Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-5 Grober Algorithmus I Ein grober Algorithmus („brute search“) ist naheliegend: 1) Vergleiche das Muster mit dem Text ab Position i; beginne mit i := 1. 2) Stimmen Muster und Text nicht überein, so starte den Vergleich erneut bei Position i + 1 des Textes. Beispiel 8.1: T ex t H H H H H H H H H H H H H H H i = = = M u ste r H i H i H i . . . H i H i Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-6 Grober Algorithmus II i:=1; j:=1; repeat if (a[i]=p[j]) then i:=i+1; j:=j+1; else i:=i-j+2; j:=1; end; until ((j>M)or(i>N)); if (j>M) then pos:=i-M; else pos:=-1; Patrick Horster // Position im Text // Position im Muster // weiter vergleichen // zurücksetzen // Muster gefunden // Muster nicht gefunden Algorithmen und Datenstrukturen SS 2001 8-7 Grober Algorithmus – Analyse Aufwandsabschätzung: • worst case: M · (N – M + 1) ° O(N·M) • Für die „meisten“ praxisrelevanten Suchvorgänge O(N + M), da die einzelnen Vergleiche von Muster und Text bereits am Anfang des Musters fehlschlagen. Existieren Algorithmen, die auch im worst case O(N+M) Schritte benötigen? Idee: Bei einer Nichtübereinstimmung kennen wir bereits Zeichen des Textes. Diese Informationen können ausgenutzt werden, damit der Zeiger i nicht jedes Mal ganz zurückgesetzt werden muss. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-8 8 String Matching • Datentypen und Definitionen • Grober Algorithmus • Algorithmus nach Knuth-Morris-Pratt – – – – – – Idee Procedure next Algorithmus Automat Verbesserter Algorithmus Analyse • Algorithmus nach Boyer-Moore • Algorithmus nach Rabin-Karp • Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-9 Algorithmus von Knuth-Morris-Pratt I Grundlegende Gedanken: • Der Vergleich an der Position j des Musters schlägt fehl. À Bisher wurden j – 1 Zeichen erfolgreich verglichen. À Der Text ab Position i – j + 1 besteht aus j – 1 Zeichen des Musters. • Im „Groben Algorithmus“ setzt man i um j – 1 Zeichen auf i – j + 2 zurück. À j – 2 Zeichen des Textes (= Muster) werden nochmals mit dem Muster verglichen. À Diese Vergleiche könnte man vorab durchführen und somit unnötige Vergleiche einsparen. Wie weit kann man von i aus nach rechts gehen ? Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-10 Algorithmus von Knuth-Morris-Pratt II Idee: Ausgangssituation: Bisher wurden j – 1 Zeichen erfolgreich verglichen. • Lege die ersten j – 1 Zeichen des Musters untereinander. • Verschiebe das untere Muster nach rechts, bis alle untereinanderliegenden Zeichen übereinstimmen oder sich die Zeichenfolgen nicht mehr überlappen. • Die Anzahl der überlappenden Zeichen x gibt an, um wie weit man i von der ursprünglichen Position aus nach rechts rücken kann. • Da ab dieser Position aber alle Zeichen bis einschließlich i – 1 mit dem Muster übereinstimmen, muss man i gar nicht zurücksetzen. Es genügt, wenn man j geeignet verändert. Da x Zeichen übereinstimmen, muss j := x + 1 gesetzt werden. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-11 Algorithmus von Knuth-Morris-Pratt IIIa À zu jeder Position j, an der der Vergleich fehlschlägt, muss eine neue Position gespeichert werden. Dies geschieht im Feld next = new int[M+1]. Beispiel 8.2: Muster p = „10101“ j n ex t[j] M u ster 1 v ersch o b en es M u ster 2 ? 1 1 0 3 ? 1 0 1 0 1 4 ? 1 0 1 1 0 1 0 5 ? 1 0 1 0 Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-12 Algorithmus von Knuth-Morris-Pratt IIIb • Das Muster für j = 2 kann nicht mehr weiter verschoben werden • À next[2] = 1. Die Muster für j = [3 .. 5] werden weiter verschoben. Beispiel 8.2: Muster p = „10101“ (Fortsetzung) j n ex t[j] M u ster 1 v ersch o b en es M u ster 2 1 1 1 0 3 ? 1 0 1 0 1 4 ? 1 0 1 1 0 1 0 5 ? 1 0 1 0 Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-13 Algorithmus von Knuth-Morris-Pratt IIIc • Das Muster für j = 3 kann nicht mehr weiter verschoben werden À next[3] = 1. • Die Muster für j = 4 und j = 5 stimmen überein À next[4] = 2 und next[5] = 3. Beispiel 8.2: Muster p = „10101“ (Fortsetzung) j Patrick Horster n ex t[j] 2 1 3 1 4 2 5 3 M u ster v ersch o b en es M u ster 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 Algorithmen und Datenstrukturen SS 2001 8-14 Algorithmus von Knuth-Morris-Pratt IV i:=1; j:=1; InitNext(); repeat if ((j=0) or a[i]=p[j])) then i:=i+1; j:=j+1; else j:=next[j]; // i wird nicht verändert (zurückgesetzt) end; until ((j>M)or(i>N)); if (j>M) then pos:=i-M; // Muster gefunden else pos:=-1; // Muster nicht gefunden Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-15 Algorithmus von Knuth-Morris-Pratt V InitNext: (Prinzip: Das Muster wird auf Übereinstimmung mit sich selbst geprüft.) i:=1; j:=0; next[1]:=0; repeat if ((j=0) or (p[i]=p[j])) then i:=i+1; j:=j+1; next[i]:=j; // Zeile (6) wird in der // verbesserten Version ersetzt else j:=next[j]; end; until (iM); Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-16 Algorithmus von Knuth-Morris-Pratt VI Betrachtet man das Muster als feststehend, so kann die Tabelle next[] auscodiert („fest verdrahtet“) werden: next[] À i:=0; 0: i:=i+1; 1: if (a[i]‘1‘) 2: if (a[i]‘0‘) 3: if (a[i]‘1‘) 4: if (a[i]‘0‘) 5: if (a[i]‘1‘) then then then then then goto goto goto goto goto 0; 1; 1; 2; 3; else else else else else i:=i+1; i:=i+1; i:=i+1; i:=i+1; i:=i+1; end; end; end; end; end; Die goto-Marken entsprechen der Tabelle next. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-17 Algorithmus von Knuth-Morris-Pratt VII Für dieses Programm kann ein endlicher Automat angegeben werden: 1) Starte im Zustand 1. 2a) Stimmt das Zeichen überein, so folge dem „vollen“ Pfeil und prüfe das nächste Zeichen. 2b) Stimmt das Zeichen nicht überein, so folge dem strichlierten Pfeil und prüfe das Zeichen erneut. 3) Beende das Programm bei Erreichen des Endzustandes E (Muster gefunden). 1 1 2 0 3 1 4 0 5 1 E 0 Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-18 Algorithmus von Knuth-Morris-Pratt VIII Analyse des Automaten À Automat nicht optimal. • Wird in Zustand 4 eine 1 gelesen, so erfolgt der Sprung in Zustand 2 . • Wird in Zustand 2 eine 1 gelesen, so erfolgt der Sprung in Zustand 1. Optimal wäre es, wenn der Sprung direkt von Zustand 4 zu Zustand 1 erfolgen würde (Verkettung von Zustand 5 analog). 1 1 0 2 3 1 4 0 5 1 E 0 Diese Änderung des Automaten soll nun auch im Programm InitNext vollzogen werden. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-19 Algorithmus von Knuth-Morris-Pratt IX Verbessertes InitNext: • Da die Werte next[] von links nach rechts aufgebaut werden, können die Zeiger direkt verkettet werden, da alle „Vorgänger“ bereits berechnet wurden. • Ein Verkettung erfolgt, falls das gesuchte Muster an beiden Positionen gleich ist (Zustände 4 und 5). Ist das gesuchte Muster ungleich, so wird next[] wie bisher berechnet (Zustände 2 und 3). • Es muss nur Zeile (6) auf Folie (8-16) ersetzt werden: if (p[i]p[j]) then next[i]:=j; else next[i]:=next[j]; end; Patrick Horster // Muster nicht gleich À keine Verkettung // Muster gleich À Verkettung Algorithmen und Datenstrukturen SS 2001 8-20 Algorithmus von Knuth-Morris-Pratt X Analyse: • Bei der Suche in Zeichenfolgen gemäß dem Algorithmus von Knuth-Morris-Pratt sind niemals mehr als N + M Zeichenvergleiche erforderlich. • Entweder inkrementieren wir j oder wir setzen es mittels der Tabelle next zurück, und zwar höchstens einmal für jedes i. Vorteile des Algorithmus: Zeiger i wird nie zurückgesetzt À Daten können blockweise eingelesen und verarbeitet werden. Ist das Rücksetzen von i unproblematisch, so können schnellere Algorithmen angegeben werden. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-21 8 String Matching • • • • Datentypen und Definitionen Grober Algorithmus Algorithmus nach Knuth-Morris-Pratt Algorithmus nach Boyer-Moore – Idee – Procedure skip – Algorithmus – Analyse & Probleme • Algorithmus nach Rabin-Karp • Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-22 Algorithmus von Boyer-Moore I Idee: • Angenommen, das Rücksetzen des Zeigers im Text ist nicht kostenintensiv, so kann das Muster von rechts nach links durchsucht werden, um Übereinstimmungen mit dem Text zu finden. • Wir betrachten alle möglichen Zeichen des Textes und überlegen, wie weit wir das Muster bei ihrem Auftreten nach rechts verschieben können. Beispiel 8.3: Suche das Muster im Text. Text: D u r c h s u c h e d e n T e x t . M u ster: T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-23 Algorithmus von Boyer-Moore IIa • Wir beginnen an Position 4 des Musters mit dem Vergleich. • Muster und Text stimmen nicht überein und der Buchstabe ‘c‘ • kommt im Muster nicht vor À Muster kann um seine ganze Länge, also um 4 Positionen nach rechts verschoben werden. Der nächste Vergleich erfolgt an Position 8 des Textes (mit Position 4 des Musters). D u r c h s u c h e d e n T e x t . T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-24 Algorithmus von Boyer-Moore IIb • Der Buchstabe ‘c‘ kommt im Muster nicht vor À Das Muster kann um weitere 4 Positionen nach rechts verschoben werden. D u r c h s u c h e d e n T e x t . T e x t T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-25 Algorithmus von Boyer-Moore IIc • Der Buchstabe ‘e‘ kommt im Muster an der 2. Position vor À Muster darf nicht mehr um 4 Positionen verschoben werden. Wie weit muss das Muster verschoben werden ? Das ‘e‘ des Musters muss unter dem ‘e‘ des Textes zu liegen kommen À Muster um 2 ( = M – 2) Positionen nach rechts verschieben. D u r c h s u c h e d e n T e x t . T e x t T e x t T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-26 Algorithmus von Boyer-Moore IId • Der Buchstabe ‘T‘ kommt im Muster an der 1. Position vor À Muster um 4 ( = M – 1) Positionen nach rechts verschieben, damit das ‘T‘ des Musters unter dem des Textes zu liegen kommt. D u r c h s u c h e d e n T e x t . T e x t T e x t T e x t T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-27 Algorithmus von Boyer-Moore IIe • Das Zeichen ‘t‘ kommt in Muster und Text vor À in Muster und • Text um eine Position nach links und Vergleich fortsetzen. Alle Zeichen des Musters stimmen mit den Zeichen des Textes überein À erstes Auftreten des Textes im Muster gefunden. D u r c h s u c h e d e n T e x t . = = = = T e x t T e x t T e x t T e x t T e x t Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-28 Algorithmus von Boyer-Moore III Vergleichen & Verschieben: • Zeichen des Textes kommt im Muster nicht vor À Muster kann um M Positionen nach rechts verschoben werden. • Zeichen kommt an Position j des Musters vor À Muster kann um M – j Positionen nach rechts verschoben werden. Beachte: Tritt ein Zeichen im Muster mehrmals auf, so ist sein erstes Auftreten von rechts zu berücksichtigen, damit das Muster nicht zu weit nach rechts verschoben wird. Wie weit das Muster verschoben werden kann, wird im Feld skip[] gespeichert. Die Initialisierung von skip[] erfolgt durch InitSkip. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-29 Algorithmus von Boyer-Moore IV Ein einzelner Buchstabe b wird mit der Funktion ORD(b) auf seinen ASCII Wert (0..255) abgebildet. skip := new int[256]; InitSkip: 1) Initialisiere alle Einträge des Feldes mit dem Wert M for j:=0 to 255M do skip[j]:=M; end; 2) Berechne skip[] für alle Zeichen des Musters: for j:=1 to M do skip[ORD(p[j])]:=M-j; end; Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-30 Algorithmus von Boyer-Moore V i:=M; j:=M; InitSkip(); repeat if (a[i]=p[j]) then i:=i-1; j:=j-1; else if (M-j+1>skip[ORD(a[i])]) then i:=i+M-j+1; else i:=i+skip[ORD(a[i])]; end; j:=M; end; until ((j<1) or (i>N)); pos:=i+1; Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-31 Algorithmus von Boyer-Moore VI Eigenschaften: • Bei der Suche gemäß dem Algorithmus von Boyer-Moore sind niemals mehr als N + M Zeichenvergleiche notwendig. • Es werden ungefähr N/M Schritte benötigt, wenn das Alphabet nicht klein und das Muster nicht lang ist. Binäre Zeichenfolgen À Alphabet sehr klein (2 Zeichen) À Teilfolgen der Länge b können zusammengefasst werden À 2b Einträge im Feld skip[]. Problem: geeignete Wahl von b. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-32 8 String Matching • • • • • Datentypen und Definitionen Grober Algorithmus Algorithmus nach Knuth-Morris-Pratt Algorithmus nach Boyer-Moore Algorithmus nach Rabin-Karp – – – – Idee Ermittlung des Hashwertes Algorithmus Analyse & Probleme • Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-33 Algorithmus von Rabin-Karp I Idee: • Jeder mögliche, aus M Zeichen bestehende Abschnitt des Textes wird als Schlüssel für eine Hashtabelle verwendet À großer Speicherbedarf. • Die Hashwerte müssen jedoch nicht gespeichert werden, da nur ein Hashwert (der des Musters) gesucht wird. À Erzeuge alle möglichen Hashwerte nacheinander und vergleiche sie mit dem des Musters. Stimmen die Hashwerte überein, dann prüfe die Textstelle genauer. Problem: Effiziente Berechnung der Hashwerte À Berechnung aus dem alten Wert und dem nächsten Zeichen. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-34 Algorithmus von Rabin-Karp II Ermittlung des Hashwertes: 1) Sei d die Anzahl der möglichen Zeichen. Betrachte die Zeichenkette als Zahl zur Basis d und wandle sie in eine Dezimalzahl k um. 2) Hashfunktion h(k) = k MOD q, mit q ° ¶. Anmerkung: Da keine Speicherung erfolgt, kann die Primzahl q sehr groß gewählt werden. Hashwert an der Position i : ki a[i]d M 1 a[i 1]d M 2 ... a[i M 1] MOD q Hashwert an der Position i + 1: k i 1 (k i a[i]d M 1 ) ¹ d a[i M] MOD q Der Wert von d M-1 MOD q kann vorausberechnet werden. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-35 Algorithmus von Rabin-Karp III Wähle geeignete Primzahl q und Zahlenbasis d. Algorithmus (Skizze): 1) Berechne d M-1 MOD q. 2) Berechne den Hashwert des Musters p. 3) Berechne den Hashwert der ersten M Zeichen des Textes a. 4a) Solange die beiden Hashwerte unterschiedlich sind, aktualisiere den Hashwert des Textausschnittes. 4b) Stimmen die beiden Werte überein, so wurde das Muster im Text gefunden. Exakter Algorithmus siehe Übung. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-36 Algorithmus von Rabin-Karp IV Laufzeit: Das Pattern-Matching nach dem Algorithmus von Rabin-Karp ist in den meisten Fällen linear. Problem: Beim Hashen kann es zu Kollisionen kommen (unterschiedliche Zeichenfolgen werden auf gleiche Hashwerte abgebildet). À Nach einem Übereinstimmen der Hashwerte sind auch noch die Zeichenfolgen zu vergleichen ! Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-37 8 String Matching • • • • • • Datentypen und Definitionen Grober Algorithmus Algorithmus nach Knuth-Morris-Pratt Algorithmus nach Boyer-Moore Algorithmus nach Rabin-Karp Ausblick Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-38 Mehrfache Suche • Wird eine Zeichenfolge mehrfach nach Mustern durchsucht, • • ist es angebracht, sie in einer geeigneten Datenstruktur abzulegen. Durch die Vorbearbeitung des Textes können die einzelnen Suchvorgänge nun effizient durchgeführt werden. Suchen in Zeichenfolgen kann nun als Spezialfall des allgemeinen Suchproblems angesehen werden. À Es können nun Hashen, Binärbaum-Suche und andere Suchalgorithmen direkt angewendet werden. Patrick Horster Algorithmen und Datenstrukturen SS 2001 8-39 Pattern Matching Allgemeines Pattern-Matching: Muster können Wildcards wie ‘?‘ oder ‘*‘ enthalten. Diese Muster können mit endlichen Automaten auf einfache Weise erkannt werden. Beispiel 8.4: Suche die Zeichenfolge ‘a?b‘ in einem Text über dem Alphabet [‘a‘ .. ‘z‘]. Automat läuft in den Zustand E, falls das Muster gefunden wurde. Patrick Horster a b..z 4 a b c..z 1 a Algorithmen und Datenstrukturen 2 b..z 3 b E a a..z c..z SS 2001 8-40
© Copyright 2024 ExpyDoc
