Studium
(Sorry, no english translation here...)
Im Rahmen meiner Diplomarbeit mit dem Thema Algorithmen zur Mustersuche in Zeichenfolgen habe ich die unterschiedlichen Algorithmen, die ich in dieser Arbeit behandelt habe, auch implementiert und Testprogramme dafür geschrieben. Der Arbeit liegt eine CD bei, deren Inhalt es auch hier zum Download gibt.
Die Programme sind nicht für den Masseneinsatz gedacht und sind dementsprechend anfällig für Fehleingaben. Daher unbedingt die beiliegende Readme beachten.
Alternative download
Beschreibung
Das Animationsprogramm führt einige ausgewählte einfache Algorithmen parallel aus und animiert den Suchvorgang. Das andere misst die Laufzeiten sämtlicher Algorithmen für verschiedene Musterlängen und Alphabetgrößen und bereitet die Ergebnisse grafisch auf.
|
|
|
Folgende Algorithmen werden dabei getestet:
Einfache Mustersuche
- Pos (Delphi-Interne Funktion)
- Naives Verfahren
- Knuth-Morris-Pratt
- Knuth-Morris-Pratt (geschickter implementiert)
- Boyer-Moore
- Boyer-Moore (geschickter implementiert)
- Quicksearch (Sunday)
- Boyer-Moore-Horspool
- Backward-Dawg-Matching
- Backward-Oracle-Matching
- Shift-Or
- Shift-And
- Backward-Nondeterministic-Dawg-Matching
Mehrfache Mustersuche
- Naives Verfahren
- Naive Triesuche
- Aho-Corasick
- Advanced Aho-Corasick
- Commentz-Walter
- Set Horspool
- Wu-Manber
- Set-Backward-Oracle-Matching
- Multiple Shift-And
Unscharfe Mustersuche
- Dynamische Programmierung (O(kn)-Laufzeit)
- Simulierung des nichtdeterministischen endlichen Automaten
- Filter: Zeichen zählen, Verifikation: DP
- Filter: Zeichen zählen, Verifikation: NFA