Vorlesung Stringologie SS 2014


Vorlesung: freitags, 9.00 - 11.00 Uhr, Paulinum P-701.

Übung: freitags, 11.15 - 12.45 Uhr, Paulinum P-701 (alle zwei Wochen).

Hauptgegenstand der Veranstaltung ist die Textsuche. Dabei werden die Vorkommen eines (kurzen) Suchmusters in einem (langen) Text gesucht. Im wesentlichen unterscheiden wir zwei Szenarios:

Bei der Online-Suche sind sowohl Muster als auch Text Eingabe. Ein Beispiel ist die Suche nach einem Wort in einer gerade geöffneten Datei. Es ist keine Vorverarbeitung des Textes möglich. Es werden die Algorithmen von Knuth-Morris-Pratt und von Boyer-Moore behandelt und verglichen.

Die Offline-Suche beschreibt den Fall, das der Text vorab vorliegt. Eine Vorverarbeitung lohnt sich insbesondere, wenn viele verschiedene Anfragen erwartet werden, oder wenn der Text so groß ist, dass eine Online-Suche zu inakzeptablen Wartezeiten führen würde. Einen Extremfall stellt ein Suchmaschine für das gesamte Internet dar. Hier wird vorab ein so genannter Index erzeugt. Wir betrachten die üblichen zugrunde liegenden Datenstrukturen wie das Suffix-Array, Suffix-Automaten und -Bäume sowie die Burrows-Wheeler Transform.

Da die effizientesten Algorithmen meist kombinatorische Eigenschaften von Strings ausnutzen, behandelt ein einführender Teil die Wortkombinatorik. Fundamentale Ergebnisse wie das Periodizitäts-Lemma von Fine und Wilf oder Thues Arbeiten zur Vermeidbarkeit sind hier wesentliche Inhalte.

Den Abschluss der Veranstaltung bildet die Behandlung von Spezialfällen wie der ungenauen Suche. Hierbei wird zum Beispiel nicht unbedingt ein genaues Vorkommen des Musters gesucht, sondern auch ähnliche Strings zählen als Treffer.

Literatur


Vorlesungsfolien

Übung

Abgabe des Projektes und dessen Vorstellung: 4.7.

Prüfungstermine

Vorzugsweise: Do 28.8. - Di 9.9. - Do 18.9. - Mi 8.10.