Wavelet-Trees (WT) sind eine platzeffiziente Datenstruktur mit einer Vielzahl von Anwendungen in der Text-Indexierung, algorithmischen Geometrie. Ziel dieser Arbeit ist die Konstruktion von WTs unter Ausnutzung spezieller CPU-Instruktionen (z.B. Packed Shuffle Bytes oder Parallel Bits Extract). In der Praxis sollte dieser Algorithmus der schnellste sequentielle WT-Konstruktionsalgorithmus sein, siehe Kaneta (2018). Der zu implementierende Algorithmus wurde von Babenko et al. (2015) und Munro et al. (2016) vorgestellt.

Masterarbeit

• Spaß an algorithmischen Problemstellungen
• Gute Programmierkenntnisse in C++
• Kenntnisse in String-Algorithmen und idealerweise parallelen Algorithmen oder die Bereitschaft, sich selbständig einzuarbeiten

Die Arbeit wird betreut von Johannes Fischer und Florian Kurpicz.