Text-Indexierung

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.

VortragsspracheDeutsch

Materialien

Folien

Kapite 00 Einführung: Folien und Video

Kapitel 01 Tries: Folien und Video

Kapitel 02 Suffix-Trees und Suffix-Arrays: FolienHandout 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

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. Hier

Changelog:

  • 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