Text-Indexierung und Information Retrieval

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

• 08.01.19: neues Skript online.
• 06.01.19: neues Skript online. Frohes neues Jahr!
• 11.12.18: neues Skript + Übungsblatt 9 online
• 10.12.18: neues Skript online
• 27.11.18: Skript+Übungsblatt 8 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:

• Tries (Datenstrukturen zur Stringsuche); Strings sortieren
• Textindizes: Suffixbäume, Suffix-Arrays, Inverted Indexes, FM-Index (evtl. LZ-Index)
• 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.

• 8.10.: Tries
• 15.10.: Suffixbäume in O(n) Zeit, Suffix-Arrays in O(n log n) Zeit
• 22.10.: Suffix-Arrays in O(n) Zeit
• 29.10.: LCP-Arrays und LZ77 in O(n) Zeit
• 5.11.: LZ78 in O(n log σ) Zeit, Suche in Suffixarrays in O(n log n) und O(n+log n) Zeit, O(1)-RMQs in O(n log n) Platz
• 12.11.: RMQ und LCA in O(1) Zeit und O(n) Platz
• 19.11.: BWT und Einführung in die Rückwärtssuche
• 26.11.: Rückwärtssuche; Rank in Bitvektoren, Wavelet Trees
• 03.12.: Y-fast Tries und Approximate Pattern Matching
• 10.12.: Komprimierter FM-Index
• 17.12.: Suffix-Array Sampling
• 7.1.: Inverted Indexes
• 14.1.: Document Retrieval; Compressed Suffix Trees
• 21.1.: Compressed RMQ und P/NSV

• aktuelle Version (Wird forlaufend erneuert.)

1. Übungsblatt 1,Wortliste für Aufgabe 2 und 3
2. Übungsblatt 2
3. Übungsblatt 3
4. Übungsblatt 4
5. Übungsblatt 5
6. Übungsblatt 6
7. Übungsblatt 7
8. Übungsblatt 8
9. Übungsblatt 9

Die letzten 3 Übungstermine nutzen wir zu einem Mini-Seminar, bei dem jeder Stud. ein 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.

1. U. Beier: On Undetected Redundancy in the Burrows-Wheeler Transform. Proc. CPM'18, article no. 3. LIPIcs Band 105. Osthues
2. Platzeffiziente Konstruktion der BWT (Kapitel 9.3 in Mäkinen et al.'s Buch “Genome Scale Algorithm Design”) Böcker
3. Bidirektionale BWT (Kapitel 9.4 in Mäkinen et al.'s Buch “Genome Scale Algorithm Design”) Michaelis
4. BWT für Bäume (Abschnitt 2 in P. Ferragina et al.: Compressing and Indexing Labeled Trees, with Applications. J. ACM 57(1), Article No. 4, 2009.) Metz

1. Range Min-Max-Trees (Kapitel 7.1 aus Navarros Buch “Compact Data Structures: A Practical Approach”). Hier bitte eine geeignete Auswahl treffen (d.h. reduzieren)! Haldimann
2. LZ77: Ultraschnelle Berechnung (Kapitel 5.2.2 aus Ohlebuschs Buch “Bioinformatics Algorithms”) Bertram
3. LZ-Index (Abschnitt 13.2.2 in Navarros Buch “Compact Data Structures: A Practical Approach”, mit den notwendigen Ergänzungen aus vorangegangenen Kapiteln) Brümmer

1. Compressed Suffix Arrays (Kapitel 11.1 aus Navarros Buch “Compact Data Structures: A Practical Approach”) Pink
2. obere Schranke für die Anzahl an Runs (Abschnitt 3 in H. Bannai et al.: The “Runs” Theorem. SIAM J. Computing 46(5), pp 1501-1514, 2017) Bode
3. Runs-Berechnung in O(n) Zeit (Abschnitt 4.1 in H. Bannai et al.: The “Runs” Theorem. SIAM J. Computing 46(5), pp 1501-1514, 2017.) Schinner

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