Text-Indexierung
- Typ: Vorlesung (V)
- Semester: WS 21/22
-
Ort:
Geb. 50.34, Raum -119
-
Zeit:
Montag 10:00 - 11:30 Uhr
- Beginn: 18.10.2021
-
Dozent:
Prof. Dr. Peter Sanders
Dr. Florian Kurpicz - SWS: 3
- LVNr.: 2400005
| Inhalt | In dieser Vorlesung beschäftigen wir uns mit Algorithmen und Datenstrukturen für Texte, speziell Text-Indizes. Text-Indizes sind Datenstrukturen, die Zusatzinformationen über einen Text bereitstellen, um Anfragen hinsichtlich dieses Texts zu beschleunigen. Hierbei kann es sich um einfache Pattern-Matching-Anfragen („Kommt ein Suchmuster im Text vor?“) oder komplexere Data-Mining-Anfragen („Welches Muster einer bestimmten Länge kommt am häufigsten im Text vor?“) handeln.
Darüber hinaus beschäftigen wir uns mit der Textkompression. Hierbei möchten wir einen Text möglichst platzeffizient darstellen. Allerdings müssen wir sicherstellen, dass der originale Text vollständig rekonstruiert werden kann. Wir sprechen hierbei von verlustfreier Kompression. In der Vorlesung lernen wir Techniken kennen, die unter anderem in Kompressionsprogrammen wie gzip verwendet werden. |
| Vortragssprache | Deutsch |
Materialien
Folien
Kapite 00 Einführung: Folien und Video
Kapitel 01 Tries: Folien und Video
Kapitel 02 Suffix-Trees und Suffix-Arrays: Folien, Handout und Video
Kapitel 03 Longest-Common-Präfix-Array: Folien und Video
Kapitel 04 Kompression: Folien und Video
Kapitel 05 Burrows-Wheeler-Transformation: Folien und Video
Kaptiel 06 Wavelet-Trees: Folien und Video
Kapitel 07 FM-Index und r-Index: Folien
Kapitel 08 LZ- und BWT-komprimierte Indizes: Folien
Kapitel 09 Suffix-Array-Konstruktion im Verteilten und Externen Speicher: Folien
Kapitel 10 Invertierter Index: Folien
Kapitel 11 Top-k Dokumenten-Retrieval: Folien
Kapitel 12 Longest Common Extensions: Folien
Zusammenfassung und Fragerunde: Folien
Projekt
Die Projektbeschreibung kann hier heruntergeladen werden.
Beispieleingaben für die unterschiedlichen Anfragen gibt es hier:
- Top-k Beispieleingabe 1 und Beispieleingabe 2
- Repeats Beispieleingabe 1 und Beispieleingabe 2
Hilfreiche Webseiten
Erstellung von Suffix-Arrays, LCP-Arrays, BWT, uvm. Hier
Changelog:
- 31.01.2022: Folien für Zusammenfassung und Fragerunde hochgeladen
- 24.01.2022: Folien für Kapitel 12 hochgeladen
- 17.01.2022: Folien für Kapitel 11 hochgeladen und Beispieltexte für das Projekt hochgeladen
- 10.01.2022: Folien für Kapitel 10 hochgeladen, Video für Kapitel 06 verlinkt und Folien für Kapitel 06 aktualisiert (Typos entfernt)
- 05.01.2022: Video Kapitel 05 verlinkt und Folien für Kapitel 05 aktualisiert (Folien 4 und 11)
- 03.01.2022: Video Kapitel 04 verlinkt und Folien für Kapitel 04 aktualisiert (Folie 18)
- 20.12.2021: Folien für Kapitel 09 hochgeladen
- 13.12.2021: Folien für Kapitel 08 hochgeladen
- 11.12.2021: Video Kapitel 03 verlinkt und Folien für Kapitel 03 aktualisiert (Typos entfernt)
- 06.12.2021: Folien für Kapitel 07 hochgeladen
- 29.11.2021: Folien für Kapitel 06 hochgeladen
- 22.11.2021: Folien für Kapitel 05 hochgeladen, Video für Kapitel 02 hochgeladen und "Hilfreiche Webseiten" verlinkt
- 15.11.2021: Folien für Kapitel 04 hochgeladen (aktualisiert 23:15 Uhr)
- 12.11.2021: Video Kapitel 01 verlinkt
- 09.11.2021: Link zu Video (Kapitel 00) aktualisiert (Tonprobleme behoben)
- 08.11.2021: Folien für Kapitel 03 hochgeladen, Projektbeschreibung hochgeladen und Video Kapitel 00 verlinkt (aktualisiert 13:45 Uhr)
- 27.10.2021: Errata Folien Kapitel 02 (Definition LMS-Präfix)
- 25.10.2021: Folien und Handout für Kapitel 02 hochgeladen
- 18.10.2021: Folien für Kapitel 00 und 01 hochgeladen