Lempel-Ziv '78 (LZ78) ist ein bekanntes Kompressionsschema, dessen Variante Lempel-Ziv-Welch (LZW) unter anderen im Bildformat gif als auch im Kompressionsprogramm ncompress eingesetzt wird. Hierbei partitioniert LZ78 den Text in Faktoren, wobei der x-te Faktor F_x = T[i..i+l-1] auf einen vorigen Faktor F_y verweist wenn F_y = T[i..i+l-2] gilt. In diesem Fall wird der x-te Faktor durch das Paar (y,T[x+l-1]) repräsentiert. Goto et al. [1] haben eine Variante, LZD genannt, entworfen, bei dem alternativ auf zwei verschieden Faktoren verwiesen werden kann, sodass ein Paar wahlweise aus Faktor-Referenz und Zeichen oder zwei Faktor-Referenzen besteht. LZD diente bereits als Inspiration für einen Grammatikkompressor [3], und wurde zu einem Vergleich mit LZMW, einer anderen LZ78 Variante, herangezogen [4].

Unklar ist jedoch, wie sich die LZD Faktorisierung mit der praktischen Variante LZW vergleichen lässt, und wie sich die Faktorisierung verhält, wenn mehr als nur zwei Referenzen erlaubt sind.

Ziel dieser Arbeit ist es, diesen Sachverhalt bezüglich Kenngrößen wie die Anzahl der Faktoren oder der Kompressionsrate zu untersuchen. Hierzu wird die Einschränkung der Darstellung über Paare fallengelassen; Faktoren können also als k-Tupel repräsentiert werden, für eine Zahl k >= 2. Als Einstiegspunkt kann das Framework tudocomp [2] genutzt werden.

Bachelorarbeit

• Spaß an der Datenkompression
• gute Kenntnisse in einer speicher/laufzeit-effizienten Programmiersprache (C++, Rust, etc.)
• Erfahrung mit der Programmierung auf Bit-Ebene

[1]: Keisuke Goto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda: LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, CPM 2015: 219-230. https://github.com/kg86/lzd

[2]: https://tudocomp.github.io/

[3]: Tatsuya Ohno, Keisuke Goto, Yoshimasa Takabatake, Tomohiro I, Hiroshi Sakamoto: LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression, IWOCA 2018: 323-335

[4]: Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov, Simon John Puglisi: On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, SPIRE 2017: 51-67

Bei Interesse wenden Sie sich bitte Johannes Fischer.