LZ77 beschreibt ein verlustloses Kompressionsverfahren, welches den Text in Faktoren zerlegt. Für dieses Verfahren soll im Rahmen dieser Arbeit die in dem Paper Approximating LZ77 via Small-Space Multiple-Pattern Matching beschriebene Approximation, die mit dem Rabin–Karp-Algorithmus arbeitet, implementiert und evaluiert werden. Bei der Evaluation sollen die Anzahl der erzeugten Faktoren, der Speicherbedarf und die Laufzeit gemessen und mit einer Implementierung, die eine exakten LZ77-Faktorisierung erzeugt, verglichen werden.

Bachelorarbeit.

• Spaß an algorithmischen Problemstellungen
• gute Programmierkenntnisse in C++ (oder die Bereitschaft, von Java umzusteigen)
• Im Idealfall bereits Kenntnisse in String-Algorithmen (z.B. aus unserer Vorlesung “Text-Indexierung”) oder die Bereitschaft, sich selbständig einzuarbeiten

Patrick Nowak (2015).

• Dominik Köppl
• Florian Kurpicz