Text-Indexierung und Information Retrieval

Die Veranstaltung ist dem Modul Text-Indexierung und Information Retrieval zugeordnet. Dozent und Übungsleiter ist Johannes Fischer.

• 10.3.17: kleine Korrekturen beim Skript, danke an P. Dinklage
• 25.1.17: neues Skript online
• 21.12.16: die Abschlussprojekte wurden verteilt und per Email verschickt
• 15.12.16: 9. Übungsblatt und neues Skript 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.

• 17.10.16: Einführung; Tries
• 24.10.16: Suffix-Arrays: Einführung und O(n log n)-Konstruktion
• 31.10.16: Linearzeitkonstruktion von Suffix-Arrays
• 7.11.16: Suffixbäume; LCP-Arrays
• 14.11.16: Lempel-Ziv-Faktorisierung
• 21.11.16: Level-Ancestor-Datenstruktur
• 28.11.16: Burrows-Wheeler-Transformation
• 5.12.16: Backwards Search; rank-Anfragen auf Bitvektoren
• 12.12.16: Wavelet Trees
• 19.12.16: Inverted Indexes
• 9.1.17: Range Minimum Queries
• 16.1.17: Das Ψ-Array (Komprimierte Suffix-Arrays und Fehlertolerante Textsuche)
• 23.1.17: Document Retrieval; Komprimierte Suffixbäume
• 30.1.17: Komprimierte LCP-Arrays; succinct trees
• 6.2.17: wg. Krankheit ausgefallen, nur Übung mit Seminarvorträgen

• Version vom 10.3.17.

• Übungsblatt 1,Wortliste für Aufgabe 2
• Übungsblatt 2
• Übungsblatt 3 (Die Lösung zu Aufgabe 4 steht in Aho/Hopcroft/Ullman: The Design and Analysis of Computer Algorithms (Addison-Wesley 1974), S. 80ff Alg. 3.2)
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7
• Übungsblatt 8
• Übungsblatt 9

Die letzten 2-3 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. eine Thema präsentieren soll.

Ziel ist es, einen die Vorlesung ergänzenden Aspekt aus einem wissenschaftlichen Artikel oder aus einem Buch in ca. 25 Minuten vorzustellen.

• Der Φ-Algorithmus aus Kärkkäinen, J., Manzini, G., & Puglisi, S. J. (2009): Permuted longest-common-prefix array. In Annual Symposium on Combinatorial Pattern Matching (pp. 181-192). Springer Berlin Heidelberg.
• Der DC3-Algorithmus zur Suffixsortierung (Kapitel 4.1.1 aus Ohlebuschs Buch “Bioinformatics Algorithms”)
• Ultraschnelle LZ77-Faktorisierung (Kapitel 5.2.2 aus Ohlebuschs Buch “Bioinformatics Algorithms”)
• Ultraschnelle Textsuche mit dem Suffix-Array (Kapitel 7.14.4 aus Gusfields Buch “Algorithms on Strings, Trees, and Sequences”)
• kompakte Suffix-Automaten (Kap. 5.5 aus Crochemore et al.'s Buch “Algorithms on Strings”)
• Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch “Genome Scale Algorithm Design”)
• Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch “Genome Scale Algorithm Design”)
• Die Wavelet-Matrix (Kapitel 6.2.5 aus Navarros Buch “Compact Data Structures: A Practical Approach”)
• Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch “Compact Data Structures: A Practical Approach”)

Ziel ist es, in der Vorlesung eingeführte Algorithmen und Datenstrukturen gut zu implementieren und anhand von realistischen Eingaben auf Platzbedarf und Laufzeit zu testen sowie mit konkurrierenden Verfahren zu vergleichen. Auch hier soll am Ende eine ca. 25-minütige Präsentation stehen.

• Vergleich von Suffix Arrays und Inverted Indexes bei der Beantwortung von Suchanfragen
• Effiziente Implementierungen von dynamischen Tries
• Praktische Evaluation der Level-Ancestor-Datenstruktur
• Vergleich von Wavelet Trees und Wavelet Matrices mit der sdsl

• Vorlesung: Mo 14-16 c.t. (SRG1 3.013)
• Übungsgruppe: Mo 16-18 s.t. (SRG1 3.013)