Florian Kurpicz

Informationen und Material für die Veranstaltung Text-Indexierung (WS2021/22)

Die offiziele Homepage der Veranstaltung befindet sich hier. Inhaltlich beschäftigen wir uns in der Vorlesung mit der effizienten Konstruktion von Text-Indizes. Genauer gesagt:

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.

Materialien

Kapitel 00 Einführung: Folien und Video
Kapitel 01 Tries: Folien und Video
Kapitel 02 Suffix-Bäume 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
Kapitel 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:

Hilfreiche Webseiten

Erstellung von Suffix-Arrays, LCP-Arrays, BWT, uvm. mit tudocomp QuickArrays

Changelog: