Eine kurze Ausarbeitung zum Knuth-Morris-Pratt Algorithmus von 1977. In dieser Seminararbeit wird die anschaulichere, weniger theoretische Herangehensweise von Morris erläutert. Dazu wird im ersten Schritt der naive Suchalgorithmus vorgestellt und darauf aufbauend werden dann die Verbesserungen durch den KMP-Algorithmus nachvollzogen.
Für verschiedene Anwendungen ergibt sich die Aufgabenstellung, in einem Text ein bestimmtes Suchmuster (engl. Pattern) zu finden. Dabei kann der Text sehr groß sein. Deshalb ist es wichtig, dass der verwendete Algorithmus effizient ist und auch für große Datensätze eine kurze Laufzeit aufweist. Der Knuth-Morris-Pratt Algorithmus ist ein Ansatz, diese Aufgabe zu erfüllen.
Inhalt
1. Einleitung
2. Grundlagen/Begrifflichkeiten
3. Naiver Suchalgorithmus
3.1. Definition
3.2. Stringmatching am Beispiel
3.3. Laufzeitanalyse
3.3.1. Worst case
3.3.2. Best case
3.3.3. Average case
4. KMP-Algorithmus
4.1. Grundidee
4.2. Präfix-Suffix Array
4.3. Stringmatching am Beispiel
4.4. Laufzeitanalyse
5. Laufzeitvergleich
6. Anwendung
7. Zusammenfassung
8. Literaturverzeichnis
9. Tabellenverzeichnis
10. Quellcodeverzeichnis
11. Abbildungsverzeichnis
12. Anhang
1 Einleitung
Für verschiedene Anwendungen ergibt sich die Aufgabenstellung, in einem Text ein bestimmtes Suchmuster (engl. Pattern) zu finden. Dabei kann der Text sehr groß sein. Deshalb ist es wichtig, dass der verwendete Algorithmus effizient ist und auch für große Datensätze eine kurze Laufzeit aufweist. Der Knuth-Morris-Pratt Algorithmus ist ein Ansatz, diese Aufgabe zu erfüllen.
Professor Stephen A. Cook war der erste, der 1970 bewies, dass ein Algorithmus das Problem des „Pattern Matching“ im ungünstigsten Fall in einer Laufzeit von O(n + m) löst. Dabei ist n die Länge des Textes und m die Länge des Suchmusters.
Im Jahr 1977 veröffentlichten die Professoren Donald E. Knuth, James H. Morris und Vaughan Pratt ihre Version eines solchen Algorithmus, der in der Tat das Problem in der Laufzeit O(n + m) löst.
Knuth und Pratt einerseits und Morris andererseits wählten unterschiedliche Ansätze zur Entwicklung des Algorithmus, die beide zum selben Ergebnis führten. Während Knuth und Pratt die theoretischen Ansätze Cooks nachvollzogen und auf dieser Grundlage ihren Algorithmus entwarfen, arbeitete Morris zeitgleich an einer Weiterentwicklung des naiven Suchalgorithmus, der das Pattern auf intuitive, aber wenig effiziente Weise Zeichen für Zeichen durch den Text schiebt und vergleicht (s. Abschnitt 3). Die Veröffentlichung des Algorithmus erfolgte dann von den drei Autoren gemeinsam.
In dieser Seminararbeit wird die anschaulichere, weniger theoretische Herangehensweise von Morris erläutert. Dazu wird im ersten Schritt der naive Suchalgorithmus vorgestellt (s. Abschnitt 4.1) und darauf aufbauend werden dann die Verbesserungen durch den KMP-Algorithmus nachvollzogen.
2 Grundlagen/Begrifflichkeiten
Im weiteren Verlauf der Arbeit sind die Begriffe Text und Pattern wesentlich.
- Ein Text t besteht aus einzelnen Teilen tj des Alphabetes £.
- Auch das Pattern p besteht aus dem gleichen Alphabet £.
Beispiel: Im Text aabacababc kommt das Pattern abab einmal vor (durch Unterstreichung kenntlich gemacht): aabacababc.
Die Code-Beispiele in den folgenden Abschnitten verwenden einige wesentliche Variablen mit immer gleicher Bedeutung:
- n beschreibt die Textlänge eines Textes t[],
- m beschreibt die Länge des Patterns pattern[].
- i beschreibt den Index der aktuellen Stelle im Text t[],
- j beschreibt die aktuelle Stelle im Pattern pattern[].
3 Naiver Suchalgorithmus
3.1 Grundidee
Der Knuth-Morris-Pratt Algorithmus basiert auf dem naiven Suchalgorithmus. Dieser iteriert über den Text und vergleicht das Pattern mit dem String, indem er naiv vergleicht und jedes Mal den Index des Patterns um eins erhöht.
Abbildung in dieser Leseprobe nicht enthalten
Quellcode 1: Naiver Suchalgorithmus
Quellcode 1 implementiert den naiven Suchalgorithmus. Wie beschrieben wird in Zeile 4 mit While- Schleife 1 über den Text iteriert. Die 2. Schleife prüft nacheinander für jedes Zeichen des Patterns, ob es zur aktuellen Stelle im Text passt. Sie bricht ab, wenn ein Mismatch gefunden wurde.
3.2 Stringmatching am Beispiel
Der naive Suchalgorithmus iteriert über einen Text oder String und gleicht ein vorgegebenes Pattern mit dem String ab. Dabei betrachtet er alle möglichen Textpositionen als Startindex für das Pattern und gleicht davon ausgehend das Pattern mit den nachfolgenden Zeichen im Text ab.
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 1: Naiver Suchalgorithmus am Beispiel
Wie in Tabelle 1 gezeigt, iteriert der naive Suchalgorithmus über den gesamten String. Der Algorithmus liefert ein korrektes Ergebnis, aber kann in Bezug auf die Laufzeit verbessert werden.
3.3 Laufzeitanalyse
3.3.1 Worst case
Wie oben in Quellcode 1 zu sehen, durchläuft der Algorithmus die i-Schleife (n — m + 1) mal. Die j- Schleife wird höchstens m-mal durchlaufen. Somit gilt für die Anzahl der Vergleiche
V < (n — m + 1) * m.
Also gilt VeO(n*m)
Da wir den schlechtesten Fall betrachten, wird die Schleife tatsächlich m mal durchlaufen, zum Beispiel wenn ein Text t = bbbbb.bc mit dem Pattern p = bbb.bc gematcht wird. Hier wäre die Anzahl der nötigen Vergleiche wieder V < (n — m+1) * m.
Zum Abschätzen wählen wir einen realistischen Wert und setzen voraus, dass die Länge des Patterns nicht länger wird als m < n/2. Ist dies gegeben, gilt
Abbildung in dieser Leseprobe nicht enthalten
Tabelle 2: Naiver Suchalgorithmus worst case
Als Beispiel wird das Pattern aac mit dem Text aaaaaac gematcht (Tabelle 2). Bei jedem Vergleich wird erst beim letzten Index des Patterns ein Mismatch festgestellt.
3.3.2 Best case
Im besten Fall liefert der Vergleich bei Index 0 des Patterns immer ein Mismatch, oder ein Match, wenn das Pattern an dieser Stelle gefunden wird. Somit sind 0(n) Vergleiche nötig.
3.3.3 Average case
Um den durchschnittlichen Fall zu bestimmen, wird auf die Wahrscheinlichkeit des Erscheinens der einzelnen Zeichen eingegangen. Mit v sei die durchschnittliche Anzahl der Zeichenvergleiche pro Position i des Textes gegeben, also die durchschnittliche Anzahl der Durchläufe der while-Schleife (Quellcode 1). Geht man davon aus, dass nicht lediglich ein Zeichen mit 100% Wahrscheinlichkeit im Text vorkommt, lässt sich die Anzahl der Vergleiche unabhängig vom Muster abschätzen. Hier erhalten wir eine Laufzeit von 0(n).
[...]