Text-Indexierung

  • Typ: Vorlesung (V)
  • Lehrstuhl: Prof. Dr. Peter Sanders
  • Ort:

    SR 301, Geb. 50.34 (Informatikhauptgebäude)

  • Zeit:

    Donnerstag, 09.45-11.15.

  • Beginn: 19.04.2012
  • Dozent:

    Peter Sanders, Johannes Fischer 

  • SWS: 2
  • ECTS: 5
  • LVNr.: 24692
  • Prüfung:

    ja

Inhalte

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.

Vorlesungsmaterialien

  • 19.4.2011: Introduction [slides pdf] [Quiz pdf]
  • 26.4.2011: Linear Time Construction of Suffix Trees; First Applications of Suffix Trees; Searching in Suffix Arrays
  • 3.5.2012: Linear Time Construction of Suffix Arrays by Induced Sorting [slides pdf]
  • 24.5.2012: Linear Time Construction of LCP-Arrays; Equivalence of RMQs and LCAs [slides pdf]
  • 31.5.2012: Range Minimum Queries; Introduction to Repeat Computation
  • 14.6.2012: Tandem Repeats
  • 21.6.2012: Lempel-Ziv Compression
  • 28.6.2012: Backwards Search and FM Indices [slides pdf]
  • 5.7.2012: Inverted Indices [slides pdf] [more slides pdf]
  • 12.7.2012: Compressed Suffix Trees [slides pdf] [Quiz pdf]
  • 19.7.2012: Compressed LCP-arrays; succinct data structures for RMQ/PSV/NSV [slides pdf] [more slides pdf]

 

Download the script [pdf, last updated on 23.7.2012].