Parallele Grammatikkompression mit Local-Sensitive-Parsing

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.

Typ

Bachelor- oder Masterarbeit

Literatur/Software

[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

Betreuer

Bei Interesse wenden Sie sich bitte an Dominik Köppl (Extern) und Johannes Fischer.

 
Last modified: 2021-12-22 17:16 by Johannes Fischer
DokuWikiRSS-Feed