Immer mehr Menschen sorgen, unter anderem durch die Nutzung von Social Media Seiten, für die Produktion von immer mehr Daten. Auch bei der Kommunikation von Sensoren und Maschinen, die durch eine immer bessere Verknüpfung (auch von kleinsten Geräten) möglich wird, fallen immer mehr Daten an. Die Auswertung diese Daten stellen für einige Unternehmen die Geschäftsgrundlage dar. Es gibt aber auch Fälle bei denen die Daten lediglich archiviert werden sollen. Hierbei bietet es sich unter anderem an die Daten komprimiert abzuspeichern. Das von Abraham Lempel und Jacob Ziv im Jahr 1977 erdachte Kompressionsverfahren LZ77 ist verlustfrei und zerlegt einen Text in Faktoren.

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