Hauptseminar im SS 2000:
Algorithmen und Datenstrukturen
in der Stringverarbeitung

Veranstalter: H.Leiß, CIS
leiss@cis.uni-muenchen.de

Organisatorisches

Zeit:

Mi, 11-13 Uhr

Beginn:

Mi, erste Semesterwoche

Raum:

1.13

Inhalt:

Es werden verschiedene Datenstrukturen und effiziente Algorithmen der Stringverarbeitung behandelt, insbesondere Indexierung von Texten, exakte und approximative Suche in Strings, Textkomprimierung, und Suche in komprimierten Texten.

Teilnahme:

Interessenten sollten mir frühzeitig eine Email schicken und sich (ggf. nach Rücksprache) ein Thema aussuchen. Es wird erwartet, daß im Semester 2 Wochen vor dem Vortrag jeder Student sich soweit mit seinem Thema vertraut gemacht hat, daß alle Fragen noch genau besprochen werden können und Zeit für die Vortragsausarbeitung bleibt.

Das Seminar ist auch für Informatikstudenten geeignet, die Interesse an der Bioinformatik haben.

Literatur:

Zu den Themen sind teilweise die Originalarbeiten angegeben, teilweise wird auf Kapitel der nachfolgenden einführenden Literatur verwiesen. Für einige Aufsätze kann man sich bei mir die Originalarbeit zum Kopieren ausleihen.

Vortragsthemen

• Klassische Suchverfahren

  1. Boyer-Moore Pattern matching (nach [Gus97] 2.2,3.1,3.2; [Wat95])
  2. Commentz-Walter pattern matching (Proc. 6th ICALP, 118-132 (1979), ggf. nach [Wat95])
  3. Kosaraju: Fast Pattern Matching in Trees. Proceedings 30th IEEE Symp. Found.of Comp.Science, 178-183.

• Aufbau von Datenstrukturen zur Indizierung (Suffixbäume)

  1. Weiner-Verfahren zum Aufbau eines Suffixbaums (Gusfield, 6.2)
  2. Ukkonen-Verfahren zum Aufbau eines Suffixbaums ([Gus97] 6.1, [Ste94] 4.2.3)
  3. Giegerich/Kurtz: Suffix Trees in the Functional Programming Paradigm. Proc. ESOP'94. Springer LNCS 788, 225-240. (schon vergeben)
  4. Breslauer: The Suffix Tree of a Tree and Minimizing Sequential Transducers. In: Hirschberg and Myers (eds.) Combinatorial Pattern Matching: 7th Annual Symposium, CPM '96 Proceedings, LNCS 1075, 1996, pages 116-129.
     http://www.brics.aau.dk/BRICS/RS/95/Ref/BRICS-RS-95-Ref/BRICS-RS-95-Ref.html

• Anwendung von Suffixbäumen zur Konstruktion schneller Algorithmen:

  1. Einfache Anwendungen der Suffixbäume ([Gus97], 7. statt Vortrag gemeinsame Lektüre)
  2. Niedrigster gemeinsamer Vorgängerknoten zweier Knoten in einem Baum ([Gus97], 8.)
  3. Längstes gemeinsames Präfix einer Wortmenge (Landau/Vishkin, JCSS 37, 63-78 (1988), J.Algorithms 10, 157-169 (1989), [Gus97])
  4. Approximative Suche in Zeichenreihen (nach [Gus97], 9.4,12.2 und [Ste94])

• Kompressionsverfahren und Suche in komprimierten Texten

  1. Die Textkompressionen nach Lempel und Ziv. (nach [BCW90] 8.2; Implementierung durch Suffixbäume: [Gus97] 7.17)
  2. Farach e.a.: String-matching in Lempel-Ziv compressed strings. Proceedings of the 27th ACM STOC, 703-713, 1995. Siehe http://www.cs.rutgers.edu/~farach/
  3. Crochemore e.a.: Text Compression Using Antidictionaries. Proceedings of MFCS 1998.
     http://www-igm.univ-mlv.fr/~mac/DCA.html
  4. Shibata e.a.: Pattern Matching in Text Compressed by Using Antidictionaries. Tech. Report DOI-Tr-157, Kyushu University, Jan. 1999
     http://www.i.kyushu-u.ac.jp/~ysuke/kenku.html
  5. Manber: A text compression scheme that allows fast searching directly in the compressed file. Proceedings Comb. Pattern Matching, Springer LNCS 1264, 1-11, 1994

References

[BCW90]

Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice Hall, Englewood Cliffs, NJ, 1990.

[CR94]

M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, Oxford, 1994.

[Gus97]

Dan Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.

[Ste94]

Graham A. Stephen. String Searching Algorithms. World Scientific, River Edge, NJ, 1994.

[Wat95]

Bruce W. Watson. Taxonomies and Toolkits of Regular Language Algorithms. PhD thesis, Eindhoven Univ. of Technology, 1995, 1995.