Îçҹ̽»¨

• Gute Programmierkenntnisse
• Optional: Vorlesung Sequenzanalyse

Die Themen sollen - je nach Umfang - alleine oder in Gruppen mit bis zu drei Studierenden bearbeitet werden. Die Themen stammen aus dem Bereich der Sequenzanalyse. Eine vorläufige Themenliste besteht aus:

• Textindizierung per LZ77 und SLP
• Textindizierung per LZ77 und RL - BWT
• Implementierung und Vergleich von BWT - Konstruktionsalgorithmen

Selbstverständlich können auch eigene Themen vorgeschlagen werden.

Folien der Vorbesprechung

LZ-Index:

• LZ-Index Implementierung
• Sebastian Kreft, Gonzalo Navarro: , Theoretical Computer Science, 483, S. 115-133, 2013
• Variante 1 (Grammatikbasiert):
  Travis Gagie , Pawel Gawrychowski , Juha Kärkkäinen , Yakov Nekrich: , Proceedings of the 6th international conference on Language and Automata Theory and Applications, LATA '12, S. 240-251, 2012
• Variante 2 (BWT-supported):
  Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, Mathieu Raffinot: , Proceedings of the 26th annual conference on Combinatorial Pattern Matching, CPM '15, S. 26-39, 2015

BWT Konstruktion:

• BWT inplace:
  Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen and Gad M. Landau: , Journal of Discrete Algorithms, 32, S. 44 - 52, 2015
• Dynamische Strukturen für BWT inplace von Nicola Prezza:
• BWT durch Vorsortierung von Suffixen mit gleichem Anfangsbuchstaben:
  Markus J. Bauer, Anthony J. Cox, Giovanna Rosone: , Theoretical Computer Science, 483, S. 134-148, 2013

Textindizierung ist ein wesentlicher Bestandteil der Sequenzanalyse, bei dem ein Text derart vorverarbeitet wird um anschließend effizient exakte Suche und Textextraktion innerhalb der konstruierten Strukturen betreiben zu können. Die verschiedenen Textindizierungsarten sollen zuerst implementiert, und anschließend anhand von Experimenten mit gängigen anderen Indizierungsarten (z.B. FM-Index, Enhanced Suffix Array, ...) bezüglich Konstruktionszeit, Speicherverbrauch und Queryzeit verglichen werden. Als Programmiersprache ist C++ vorgesehen.