Informatik-Logo
Fakultät für Informatik der Technischen Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Proseminar: Textalgorithmen

[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 und zur Textkompression.

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


Themenliste:

    Online Pattern Matching
  1. Der Knuth-Morris-Pratt Algorithmus
  2. Der Boyer-Moore Algorithmus
  3. Die Karp-Rabin Fingerprint-Methode
    Offline Pattern Matching (Indexstrukturen)
  4. Tries und PATRICIA Trees
  5. Suffix Trees (Algorithmus von Ukkonen)
  6. Suffix Arrays (Einführung und Algorithmus von Manber und Myers)
    Approximate Pattern Matching (fehlertolerante Suche)
  7. Die Editier-Distanz (Algorithmus von Needleman, Wunsch)
  8. Approximate Pattern Matching in Suffix Trees
  9. Parameterisiertes Pattern Matching
    Textkompression
  10. Huffman Kodierung
  11. Lempel-Ziv-Kodierungen
  12. Burrwos-Wheeler Transformation und Anwendungen
    Zustatzthemen
  13. Suffix Trees (Algorithmus von McCreight)
  14. Suffix Trees (Algorithmus von Weiner)
  15. Suffix Arrays (Algorithmus von Ko, Aluru)
  16. Inverted Files
  17. 2-dimensionales Pattern Matching

Eine Ausführliche Themenliste mit Literaturangaben folgt.

Anmeldung

* Interessentinnen/en können sich bei der Vorbesprechung oder vorab per Email an nowakj@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

07.02.2006, 14:00 Uhr s.t.

im Raum

MI 03.11.018

statt.

Termine und Betreuer

:
(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

01.02.2005: N.N. (erstes Treffen mit Betreuer spätestens am: 21.12.04)
Ersatztermin 2
Betreuer: N.N.

08.02.2005: N.N. (erstes Treffen mit Betreuer spätestens am: 21.12.04)
Ersatztermin 2
Betreuer: N.N.

-->

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 Vortragerstes 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 VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortragfertige 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:
* 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: Johannes Nowak

Johannes Nowak Last modified: Tue Jan 24 13:55:37 CET 2006