Die Veranstaltung ist dem Modul Ausgewählte Kapitel der Algorithmik zugeordnet.

• 27.1.15: Bitte schicken Sie Ihre Matriklenr. per Email an den Dozenten (Subject “TIIR WS14/15”), damit Ihre Studienleistung eingetragen werden kann.
• 27.1.15: neue Version vom Skript und Folien der letzten VL online
• 19.1.15: neue Version vom Skript und letztes Übungsblatt online
• 12.1.15: neue Version vom Skript und 12. Übungsblatt online
• 6.1.15: neue Version vom Skript und 11. Übungsblatt online

In dieser Vorlesung beschäftigen wir uns mit dem Problem, einen (oft sehr langen) Text so vorzuverarbeiten, dass im Anschluss effiziente Suchanfragen darin ausgeführt werden können. Beispiele solcher Anfragen reichen von einfachen Pattern-Matching Anfragen (“kommt ein Suchmuster im Text vor?”) bis hin zu komplexen Data-Mining-Anfragen, z.B. die Suche nach repetitiven Mustern. Im einzelnen behandeln wir die folgenden Themen:

• Textindizes: Suffixbäume, Suffix-Arrays, Inverted Indexes
• exakte und approximative Mustersuche mit Hilfe von Textindizes
• Funktionalität von Suchmaschinen: schnelle Berechnung und Sortierung aller Dokumente, die ein Suchmuster enthalten
• Textkompression: Burrows-Wheeler-Transformation und LZ-Komprimierung

Sie sollten Spaß an algorithmischen Problem und der Analyse von Algorithmen haben. Die Vorlesungen DAP1 und DAP2 sollten nicht zu Ihren schlechtesten Fächern gehört haben. Im Idealfall haben Sie bereits andere Veranstaltungen aus diesem Bereich gehört (Algorithmen und Datenstrukturen, Effiziente Algorithmen, Algorithm Engineering, Algorithmische Bioinformatik, etc.) bzw. haben vor, dies noch zu tun.

Für die Übungen sind Programmierkenntnisse in C/C++ oder Java erforderlich.

Die Vorlesung ist geeignet für Informatiker im Master- oder Diplomstudiengang (Hauptstudium). Sie eignet sich gut als Vorbereitung zur Erstellung von Studien- oder Abschlussarbeiten (Master/Diplom) im Bereich Text-Indexierung.

• 6.10.14: Einführung; Tries
• 13.10.14: Inverted Index: Vokabular und Algorithmen für List Intersection
• 20.10.14: Inverted Index: Kompression von Postings Listen
• 27.10.14: Suffixbäume und Suffix-Arrays
• 3.11.14: Linearzeitkonstruktion von Suffix-Arrays
• 10.11.14: Linearzeitkonstruktion von Suffix-Arrays (ctd.), Linearzeitkonstruktion von LCP-Arrays
• 17.11.14: Linearzeitkonstruktion von LCP-Arrays (ctd.), Suche mit Suffix Arrays [Folien]
• 24.11.14: guest lecture by Tomohiro I: Construction of Sparse Suffix Arrays
• 1.12.14: Range Minimum Queries
• 8.12.14: Range Minimum Queries (ctd.), document retrieval, longest common prefixes
• 15.12.14: LZ77 Datenkompression
• 5.1.15: Burrows-Wheeler-Transformation
• 12.1.15: Rückwärts-Suche
• 19.1.15: Wavelet-Trees
• 26.1.15: komprimierte Suffixbäume [Folien]

aktuelle Version

• Übungsblatt 1, Wortliste für Aufgabe 2
• Übungsblatt 2, Beispieldatei für Aufgabe 1
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7
• Übungsblatt 8
• Übungsblatt 9
• Übungsblatt 10
• Übungsblatt 11
• Übungsblatt 12
• Übungsblatt 13

• Vorlesung: Mo 10-12 c.t. (SRG1 3.012)
• Übungsgruppe: Mo 12-14 s.t. (SRG1 3.012)