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.