Text-Indexierung

Zusammenfassung

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:

  • Textindizes: Suffixbäume, Suffix-Arrays und Suffix-Trays
  • exakte und approximative Mustersuche mit Hilfe von Textindizes
  • Berechnung von Tandem-Repeats und anderer repetitiver Elemente 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

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.

Die Vorlesung ist so angelegt, dass sie mit anderen Vorlesungen aus dem Vertiefungsgebiet Algorithmik gut kombinierbar ist, d. h. geringe Überlappungen und keine Vorraussetzungen jenseits der Algorithmentechnik.

Stundenplan

  1. (14.4.2010) Einführung
  2. (21.4.2010) Hash-basiertes Dictionary-Matching
  3. (28.4.2010) Textsuche mit Hilfe von Suffix-Bäumen und -Arrays
  4. (5.5.2010) Textsuche mit Hilfe von Inverted Files
  5. (12.5.2010) Konstruktion von Suffixbäumen und -Arrays (1)
  6. (19.5.2010) Konstruktion von Suffixbäumen und -Arrays (2)
  7. (26.5.2010) Repeat-Suche mit Suffixbäumen
  8. (2.6.2010) Tandem Repeats
  9. (9.6.2010) Tandem Repeats (Forts.); Range Minimum Queries
  10. (11.6.2010) Range Minimum Queries (Forts.); Lowest Common Ancestors; LZ-Datenkompression
  11. (16.6.2010) Suffix Trays; BWT
  12. (23.6.2010) Rückwärtssuche; rank-Anfragen
  13. (30.6.2010) Wavelet Trees; Inside Google
  14. (7.7.2010) [vorgezogen auf den 11. Juni]
  15. (14.7.2010) [vorgezogen auf den 11. Juni]