Text-Indexierung

  • Typ: Vorlesung (V)
  • Semester: WS 2023/24
  • Ort:

    Geb. 50.34, Raum 236
  • Zeit:

    Montag 14:00 - 15:30
  • Dozent: Dr. Florian Kurpicz
  • SWS: 3
  • LVNr.: 2400005
  • Hinweis: Präsenz
Links
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

Übersicht

Wichtige Informationen
  • Bitte melden Sie sich im ILIAS-Kurs an. Dort werden alle weiteren wichtigen Informationen bekanntgegeben.
  • Die mündlichen Prüfungen finden am 20.02, 21.02. und 22.02. statt (weitere Termine sind möglich). Bitte wenden Sie sich für einen Termin per E-Mail an das Sekretariat von Prof. Sanders, blancani∂kit.edu, und nennen Sie Ihren vollständigen Namen, Ihre Matrikelnummer, Ihr Studienfach sowie die Version der Prüfungsordnung, nach der Sie studieren.
    Vor Ihrem Termin bzw. vor dem Abgabetermin der Übungsleistung müssen Sie sich am Studierendenportal sowohl für die mündliche Prüfung als auch für die Übung anmelden.
  • Alte Vorlesungsaufzeichnungen finden Sie hier und hier.
  • Lehrevaluation: https://onlineumfrage.kit.edu/evasys/online.php?p=K2FFL (beendet)
  • Die Vorlesung am 22.01.2024 fällt krankheitsbedingt aus.
Folien
  1. Kapitel 00 Einführung: Folien und Folien ohne Animationen
  2. Kapitel 01 Tries: Folien und Folien ohne Animationen
  3. Kaptiel 02 Invertierter Index: Folien und Folien ohne Animationen
  4. Kaptiel 03 Suffix-Baum und -Array: Folien und Folien ohne Animationen
  5. Kapitel 04 LCP-Array: Folien und Folien ohne Animationen
  6. Kapitel 05 Kompression: Folien und Folien ohne Animationen
  7. Kapitel 06 Burrows-Wheeler-Transformation: Folien und Folien ohne Animationen
  8. Kapitel 07 Wavelet-Trees: Folien und Folien ohne Animationen
  9. Kapitel 08 FM-Index und r-Index: Folien und Folien ohne Animationen
  10. Kapitel 09 LZ-komprimierte Indices: Folien und Folien ohne Animationen
  11. Kapitel 10 Top-k Dokumenten-Retrieval: Folien und Folien ohne Animationen
  12. Kapitel 11 Suffix-Array-Konstruktion im externen und verteilten Speicher: Folien und Folien ohne Animationen
  13. Kapitel 12 Move Datenstruktur für r-Index: Folien und Folien ohne Animationen
  14. Kapitel 13 Longest Common Extensions: Folien und Folien ohne Animationen
Projekt
  • Projektbeschreibung: Hier