Forgot your password?
Advanced Text Indexing Techniques
General Information
| Lecturer | Dr.
Johannes Fischer |
| Lectures | donnerstags, 11:15-13:00, Kleiner Hoersaal, Sand 6/7 |
| Tutorials |
dienstags, 11:15-12:45, Seminarraum 1, Sand 6/7 |
| Credits | 4 LP, 2+2 SWS |
| Prerequisites |
(Algorithms
in) Bioinformatics I oder Adv. Meth. for Sequence Analysis könnten hilfreich sein, sind aber nicht zwingende Voraussetzung |
| Modules |
siehe "Modulhandbuch" |
| Language |
Deutsch |
Schedule
| 20.04.2009 |
Wiederholung Suffixbäume und -arrays |
| 27.04.2009 | Suchen in Suffixarrays |
| 04.05.2009 | Suffix Trays; Burrows-Wheeler-Transformation |
| 14.05.2009 | Rücktransformation & Komprimierung der BWT; Rückwärtssuche |
| 26.05.2009 | Reduktion Occ->rank-queries in Bitvektoren; rank-Anfragen in sublinearem Platz |
| 28.05.2009 | select-Anfragen in sublinearem Platz; Wavelet Trees |
| 16.06.2009 | Midterm Exam (keine Übungen, sondern Klausur!) |
| 18.06.2009 | Komprimierte Suffixarrays I: rekursive Zerlegung durch die psi-Funktion |
| 25.06.2009 | Komprimierte Suffixarrays II: Repräsentation von psi mittel Elias delta-Code |
| 02.07.2009 | Analyse CSA; Komprimierte Texte mit random access |
| 09.07.2009 | Komprimierte Texte mit random access (Forts.); Komprimierte Suffixbäume |
| 16.07.2009 | Komprimierte LCP-Arrays; succinct data structures for RMQs und PSV/NSV-queries |
| 23.07.2009 | Abschlussklausur |
Skript
Es wurde ein vorlesungsbegleitendes Skript verfasst, welches nicht mehr online verfügbar ist. Eine Kopie wird auf Anfrage (per Email an den Dozenten) zur Verfügung gestellt.
Übungen
- Übungsblatt 1
- Übungsblatt 2
- Übungsblatt 3
- Übungsblatt 4
- Übungsblatt 5
- Übungsblatt 6
- Übungsblatt 7
- Übungsblatt 8
- Übungsblatt 9
Zusammenfassung
Suffixbäume und -arrays sind einfache Beispiele von Textindizes, die jeder aus den Einführungsveranstaltungen kennen sollte. In dieser Vorlesung gehen wir einen Schritt weiter und betrachten aktuellere Forschungsergebnisse zur Textindizierung. Wir gehen insbesondere auf das Zusammenspiel von Textkomprimierung und -indizierung ein und zeigen, dass diese scheinbar unterschiedlichen Konzepte in Wirklichkeit zwei Seiten der gleichen Medaille sind.
Wir behandeln die folgenden 4 Textindizes im Detail:
- Suffix Trays (eine Mischung aus "suffix TRee" und "suffix arrAY")
- komprimierte Suffixarrays und Vorwärtssuche
- FM-Indizes und Rückwärtssuche
- komprimierte Suffixbäume
Die Vorlesung ist geeignet für Informatiker und Bioinformatiker im Master- oder Diplomstudiengang (Hauptstudium). Sie eignet sich gut als Vorbereitung zur Erstellung von Abschlussarbeiten (Master/Diplom) im Bereich Textindizierung.
Literatur
- U. Manber and E. W. Myers: Suffix Arrays: A New Method for Online String Searches. SIAM J. Computing 22(5): 935-948, 1993.
- R. Cole, T. Kopelowitz, and M. Lewenstein: Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. Proc. 33rd International Colloquium on Automata, Languages, and Programming, pp. 358-369, Lecture Notes in Computer Science 4051, Springer-Verlag, 2006.
- K. Sadakane: New Text Indexing Functionalities in the Compressed Suffix Arrays. J. Algorithms 48(2), 294-313, 2003.
- P. Ferragina and R. Venturini: A Simple Storage Scheme for Strings Achieving Entropy Bounds. Theoretical Computer Science 372(1): 115-121, 2007.
- J. Fischer, V. Mäkinen, and G. Navarro: An(other) Entropy-Bounded Compressed Suffix Tree. Proc. 19th Annual Symposium on Combinatorial Pattern Matching, pp. 152--165, Lecture Notes in Computer Science 5029, Springer-Verlag, 2008.
- G. Navarro and V. Mäkinen: Compressed Full-Text Indexes. ACM Computing Surveys 39(1), Article No. 2 (61 pages), 2007.
Credits for this course:
This course is worth 4 LP, so you will be expected to do 4x30=120 hours of work for this course.
Master Students
You have to take part in the problem sessions, where we discuss exercises that are handed out at regular intervals. You will be graded on your participation in the problem sessions. This grade will make up 1/3 of your final grade. The mid-term exam and final exams will each also contribute 1/3 toward your final grade.
Diploma Students
To get credit for this course, you must obtain a grade of 4.0 or better as described under Master students. Diese Veranstaltung ist prüfbar als Praktische Informatik (2+2 SWS) or Theoretische Informatik (maximal 2+2 SWS).
