-----------------------------------------------
CD zur Diplomarbeit

"Algorithmen zur Mustersuche in Zeichenfolgen"

Daniel Gaußmann
Betreuer: Prof. Dr. Egon Wanke
Heinrich-Heine-Universität Düsseldorf
Mathematisch-Naturwissenschaftliche Fakultät
9.Mai 2008


Hinweise zu den Programmen auf der CD
-----------------------------------------------


Executables
===========

Das Animationsprogramm ist in der Anfangsphase dieser Arbeit entstanden 
und dient der reinen Anschauung einiger Algorithmen zur einfachen Mustersuche. 
Es können damit mehrere Verfahren parallel durchgeführt werden, um so die 
Unterschiede der jeweiligen Strategien zu verdeutlichen. 
Es stehen Beispieltexte und -muster zur Verfügung, die die Unterschiede 
zwischen dem naiven Verfahren und Knuth-Morris-Pratt, zwischen next- 
und f-Array oder zwischen der starken und schwachen Good-Suffix-Regel 
anschaulich machen. Ein tieferen Zweck erfüllt es nicht, aber es ist 
eine nette Spielerei und auf der CD ist genug Platz dafür.

Das zweite und für diese Arbeit weitaus wichtigere Programm ist Zeitmessungen. 
Mit diesem Programm wurden die Algorithmen getestet, die Laufzeiten 
gemessen und die Ergebnisse grafisch aufbereitet.

Die Bedienung beider Programme sollte halbwegs intuitiv sein, allerdings 
können einige Probleme auftreten, da ich nicht besonders viel Zeit auf 
das Abfangen von Fehleingaben verwendet habe. 

Daher folgende Hinweise zu bekannten Problemen:
-----------------------------------------------

* Beim Animationsprogramm kann es in seltenen Fällen vorkommen, dass 
  nach dem Auftreten eines Fehlers das Programm unbedienbar wird. 
  In diesem Fall muss die Anwendung neu gestartet werden.

* Das Programm Zeitmessungen ist für eine Auflösung von mindestens 
  1280x1024 Pixeln konzipiert. Auf niedrigeren Auflösungen wird die 
  Bedienung etwas unbequemer. Das Programm besteht aus zwei Fenstern - 
  dem Übersichtsfenster und dem Detailfenster, was beim Start hinter 
  dem anderen liegt. Es kann unter anderem über das Kontextmenü 
  (rechte Maustaste) des "`Kartenbildes"' in den Vordergrund geholt 
  werden.

* Die Option "Real-Time-Priority" ist mit Vorsicht zu genießen. Dadurch 
  erhalten die Algorithmen höchste Priorität (damit zwischendurch 
  keine anderen Prozesse Rechenzeit zugeteilt bekommen, wodurch die 
  Messungen verfälscht werden), was bei längeren Laufzeiten zu 
  Komplikationen bis hin zur Unbedienbarkeit des Systems führen kann. 
  Unter Vista konnte ich dieses Problem nicht beobachten, aber im 
  Zweifel sollte die Option ausgeschaltet bleiben.

* Die Option "Statistik automatisch speichern" führt zu einem Fehler, 
  wenn das Unterverzeichnis \Daten\ nicht existiert oder schreibgeschützt 
  ist.

* Die Option "Treffer auflisten und checken" dient der Fehlerkontrolle.
  Ist sie aktiviert, werden die Fundstellen in einer Liste gespeichert, 
  miteinander verglichen und Unstimmigkeiten in dem Textfeld darunter 
  ausgegeben. Dabei kann es bei der mehrfachen Mustersuche zu zwei 
  Problemen kommen:

    - Bei großen Mustermengen, langen Texten und sehr kleinen Alphabeten 
      (d.h. am Anfang eines Durchlaufs) ist die Menge der Fundstellen 
      derart groß, dass der Arbeitsspeicher vollläuft und das Programm 
      irgendwann abstürzt. Systembedingt passiert das spätestens bei  
      einem Speicherbedarf von 2GiB, auf meinem Laptop war bei ca. 1.6GiB 
      Ende.

    - Bei der Suche nach 2 Mustern kommt es in ca. 50% der Fälle vor,
      dass die Suche bei längeren Texten am Anfang scheinbar in eine 
      Endlosschleife läuft. Dieser Effekt erklärt sich dadurch, dass die 
      Trefferlisten für einen schnellen Vergleich sortiert werden müssen 
      (der naive Algorithmus findet die Muster in einer anderen 
      Reihenfolge als die anderen) und die Vorsortierung der "naiven Liste"
      bei zwei gleichen Mustern für die intern verwendete Quicksort-Variante 
      den Worst-Case bedeutet. In dem Fall hilft langes Warten, oder ein 
      Abschießen des Programms durch den Taskmanager.

* Beim Laden von vorher gespeicherten Daten wird (fast) keine Überprüfung 
  auf Sinnhaftigkeit der Daten durchgeführt. Werden über die Dialoge 
  ungültige Dateien ausgewählt, kann es zu unerwünschten Effekten kommen,
  zum Beispiel zu einem Volllaufen des Arbeitsspeichers mit abschließendem
  Absturz der Anwendung. Die Standard-Dateiendung für Kartendaten ist ".dpl", 
  die Daten für detailliertere Messungen sind in ".det"-Dateien gespeichert.

	

Quellcode
=========

Die Programme wurden mit "Borland Delphi 7 Personal" entwickelt. Eine 
Portierung auf Lazarus, einer freien Entwicklungsumgebung, die in weiten Teilen 
kompatibel zu Delphi ist und plattformübergreifendes Programmieren ermöglicht, 
ist mit einigen kleinen Änderungen möglich. Allerdings zeigten erste Experimente, 
dass dabei alle Algorithmen mindestens doppelt so lange brauchen, und einige 
Algorithmen komplett unbrauchbar wurden (100-500fache Laufzeit), was irgendwie 
mit einem anderen Parameter- oder Speicher-Management zusammenhängt. 

Für ein Kompilieren der Projekte mit den aktuellen kostenfreien Delphi-Versionen 
(Turbo Delphi Explorer) sind kleinere Umbauten an dem GUI nötig, da dort eine 
der verwendeten visuellen Komponenten ("TSpinEdit", zur Eingabe von ganzzahligen 
Werten) nicht mehr verfügbar ist. 

Bei den Zeitmessungen kann zusätzlich zu den hier vorgestellten Algorithmen 
die von Delphi zur Verfügung gestellte Funktion "Pos" getestet werden. Um es 
diplomatisch zu formulieren: Diese Funktion wurde wahrscheinlich für andere 
Fälle optimiert.



Download
========

Der Inhalt der CD ist auch über meine Webseite www.gausi.de zu bekommen.
