Local-Sensitive-Parsing ist eine Familie von Grammatikkompressoren, bei deren Substrings mit dem gleichen lokalen Kontext in die selben Faktoren zerlegt werden. Wegen dieser Eigenschaft ist es leicht möglich, die Kompression parallel zu berechnen. Hierbei können verschiedene Kompressionsschema wie ESP [1], HSP, oder Signature-Encoding ausgetestet werden.

Das Problem lässt sich als Masterarbeit erweitern, indem wir auf der erzeugten Grammatik eine Datenstruktur bauen möchten, die sogenannte Longest-Common-Extension (LCE) Anfragen geschickt beantwortet. Hierzu gibt es bereits theoretische Ansätze [2] als auch Software [3], die aber mit praktischen Techniken wie Caching oder Bookmarking verschnellert werden können.

Bachelor- oder Masterarbeit

[1]: Yoshimasa Takabatake, Kenta Nakashima, Tetsuji Kuboyama, Yasuo Tabei, Hiroshi Sakamoto: siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves. Algorithms 9(2): 26 (2016), https://github.com/tkbtkysms/esp-index-I

[2]: Johannes Fischer, Tomohiro I, Dominik Köppl:

Deterministic Sparse Suffix Sorting in the Restore Model. ACM Trans. Algorithms 16(4): 50:1-50:53 (2020)

[3]: https://github.com/itomomoti/ShapedSlp

Bei Interesse wenden Sie sich bitte Johannes Fischer.