Proseminar: Textalgorithmen und Pattern Matching

(Dienstags 14:30-16:00 Uhr, Raum 03.11.018)

[Zusammenfassung] [Themenliste] [Amneldung] [Vorbesprechung] [Termine] [Hinweise] [Links]

Zusammenfassung

Die Verarbeitung von Texten hat in der Informatik eine lange Tradition. Waren es zu Anfang vor allem Algorithmen zur schnellen Suche in (kurzen) Texten und beim Bearbeiten von Texten (z.B. in den bekannten Programmen grep, awk, emacs, vi) und zur Kompression (compress und zip), so gewinnt zunehmend die Verarbeitung riesiger unstrukturierter Textmengen (oder Datenmengen) an Bedeutung. Einige wichtige Beispiele sind Volltextsuchmaschinen für das Internet (z.B. www.google.de, www.alltheweb.com) und Indizierung von Genomdaten (z.B., GenBank, TIGR).

Desweiteren gibt es Anwendungen in der Theorie der formalen Sprachen, beim Übersetzerbau, bei der Implementierung von Programmiersprachen, bei Multimedia Systemen und bei der Bildverarbeitung.

Das wohl grundlegendste Problem in der Textverarbeitung ist das Suchproblem (Pattern Matching), in dem es darum geht, zu entscheiden ob, wo und wie oft ein Muster in einem Text vorkommt.

In diesem Seminar werden verschiedene Algorithmen zur Lösung dieses Problems betrachtet, die Stärken in unterschiedlichen Anwendungen haben. Wir beginnen mit der einfachen linearen Suche, betrachten die Suche nach mehreren Mustern und die durch Vorverarbeitung des Textes (Indizierung) beschleunigte Suche. Anschließend betrachten wir noch Ansätze zur fehlertoleranten Suche, Textkompression und Suche in Bildern.

Es wird auf eine klare Darstellung der Probleme und Algorithmen Wert gelegt, wobei auch die Analyse (Korrektheit und Laufzeit) berücksichtigt werden soll.

Themenliste:

Der Knuth-Morris-Pratt Algorithmus
Der Boyer-Moore Algorithmus
Die Karp-Rabin Fingerprint-Methode (noch frei)
Der Aho-Corasick-Algorithmus (ggf. mit regulären Ausdrüken) (noch frei)
Tries und PATRICIA Trees (noch frei)
Suffix Trees (Algorithmus von Ukkonen)
Directed Acyclic Word Graphs (DAWGS)
Suffix Arrays (Einführung und Algorithmus von Manber und Myers) (noch frei)
Suffix Arrays (Ein Algorithmus mit linearer Laufzeit von Kärkkäinen und Sanders) (noch frei)
Die Editier-Distanz (Levenshtein-Distanz) und "Longest Common Subsequence" (noch frei)
Textkompression - Huffman Coding Static and Dynamic, Ziv-Lempel
2-Dimensional Pattern Matching

Zustatzthemen

Suffix Trees (Algorithmus von McCreight)
Suffix Trees (Algorithmus von Weiner)
Inverted Files

Die Themen 1-4 beschäftigen sich mit der Suche nach einem oder mehreren Mustern in einem Text unter der Prämisse, dass die Muster aber nicht der Text vorverarbeitet werden können. Die Themen 5-9 betrachten den Fall, dass für einen oder mehrere Texte ein Index erstellt wird, der anschließend eine schnelle Suche erlaubt. Thema 10 beschäftigt sich mit Suche/Vergleich mit Fehlern, Thema 11 mit Kompression und Thema 12 mit Suche z.B. in Bildern.

Thematische Fragen bitte an Moritz Maaß.

Die Themenliste mit Literaturangaben als PostScript-Datei.

Anmeldung

Interessentinnen/en können sich bei der Vorbesprechung oder vorab per Email an maass@in.tum.de mit Subject "Textalgorithmen (Anmeldung)" anmelden. In der E-Mail sollen folgende Informationen enthalten sein:

Name, Vorname
Studiengang und Studienfach
Semester
E-Mail (nur Adressen @in.tum.de)
bevorzugtes Thema

Vorbesprechung

Die Vorbesprechung findet am

22.07.2004, 13:00 Uhr s.t.

im Raum

MI 03.11.018

statt.

Termine und Betreuer

Das Proseminar findet jeweils Dienstags von 14:30 Uhr (s.t.) bis 16:00 Uhr im Raum 03.11.018 statt.

26.10.2004:	`Rolf Siebachmeyer` (erstes Treffen mit Betreuer spätestens am: 21.09.04) 1. Der Knuth-Morris-Pratt Algorithmus Betreuer: Sebastian Wernicke
02.11.2004:	`Konrad, Christian` (erstes Treffen mit Betreuer spätestens am: 28.09.04) 2. Der Boyer-Moore Algorithmus Betreuer: Sven Kosub
21.12.2004: (verlegt)	`Pawel Dacka` (erstes Treffen mit Betreuer spätestens am: 26.10.04) 6. Suffix Trees (Algorithmus von Ukkonen) Betreuer: Stefan Pfingstl
11.01.2005:	`Dennis Roch` (erstes Treffen mit Betreuer spätestens am: 30.11.04) 10. Die Editier-Distanz (Levenshtein-Distanz) und "Longest Common Subsequence" Betreuer: Werner Meixner
18.01.2005:	`Ralf Knuth` (erstes Treffen mit Betreuer spätestens am: 07.12.04) 11. Textkompression - Huffman Coding Static and Dynamic, Ziv-Lempel Betreuer: Ulrich Rührmair
25.01.2005:	`Chen, Mei-Chuan` (erstes Treffen mit Betreuer spätestens am: 14.12.04) 12. 2-Dimensional Pattern Matching Betreuer: Jan Griebsch
1.2.2005: (verlegt)	`Ivan Shterev` (erstes Treffen mit Betreuer spätestens am: 02.11.04) 7. Directed Acyclic Word Graphs (DAWGS) Betreuer: Johannes Nowak

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung)	Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit. Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität)	Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität)	Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).
Anwesenheit bei den Vorträgen	Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortrag		erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem Vortrag		Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem Vortrag		Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortrag		fertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

	Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
	Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden. Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden. Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden) Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
	Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
	LaTeX Kochbuch RBG-Seite zu LaTeX
	Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
	Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)

Interessante Links

	Eine Liste von interessanten Links rund um das Pattern Matching gibt es hier: Pattern Matching Pointers.
	Eine der wichtigsten Konferenzen in diesem Bereich ist das regelmäßige Symposium on Combinatorial Pattern Matching.
	Exact String Matching Algorithms - Animation in Java ist eine Online-Übersicht, die von Christian Charras und Thierry Lecroq zusammengestellt wurde.

Weitere (thematische) Auskünfte bei: Moritz Maaß

Moritz Maaß Last modified: Wed Dec 1 15:02:57 CET 2004