Praktikum zur Datenkompression

• Gute Programmierkenntnisse
• Interesse an Kompressionsalgorithmen und komprimierten Datenstrukturen
• Vordiplom

• Implementierung eines Kompressionsalgorithmus bzw. einer komprimierten Datenstruktur mit Auswertung von Laufzeit und Platzbedarf.
• Experimenteller Vergleich der eigenen Implementierung mit Software aus der Praxis (etwa gzip, bzip2,...).
• Dokumentation der Herangehensweise und der Ergebnisse in einem Praktikumsbericht.

Die Themen sollen - je nach Umfang - alleine oder in Gruppen bis drei Studenten bearbeitet werden. Zu den von uns vorbereiteten Themen können Sie im Einzelfall selber vorgeschlagene Themen bearbeiten, wenn diese von uns für interessant und umfangreich genug bewertet werden.

Folgende Themen liegen schon vor:

• Varianten des Lempel-Ziv-Algorithmus
• Self-Delimiting Codes und Anwendungen
• Burrows Wheeler Transformation  (BWT) für XML Daten
• Implementierung eines Compressed Suffix Arrays (CST)
• Fraktale Bildkompression
• Bildkompression mittels Wavelet-Tree

Details zu den Themen:

• Varianten des Lempel-Ziv-Algorithmus
  LZ77, LZ78 und LZW sind Algorithmen zur Textkompression, welche auf ein Wörterbuch basieren. Hierbei wird das Wörterbuch direkt aus dem zu komprimierenden Text generiert, d.h. das Wörterbuch besteht aus im bereits komprimierten Text vorkommenden Wörtern, und die Kompression versucht für die nächsten zu komprimierenden Zeichen einen möglichst langen Wörterbucheintrag zu finden. Hierbei unterscheiden sich die verschiedenen Varianten hauptsächlich darin, wie die Wörterbucheinträge generiert werden. Auch moderne Kompressionsalgorithmen sind oft eine Variante dieser Algorithmen (wie z.B. LZMA, implementiert in 7zip). Im Praktikum sollen nun untersucht werden, wie sich verschiedene Parameter (wie z.B. die Wörterbuchgrösse) und Verbesserungen (z.B. Kombination mit Huffman- oder arithmetischer Codierung) auf die Kompressionsrate und Laufzeit des Algorithmus auswirken. Dazu sollen die entsprechenden Algorithmen programmiert und getestet werden, ausserdem sollen sie mit bereits bestehenden Kompressionsalgorithmen verglichen werden (gzip, bzip2, 7zip).
  Ansprechpartner: Martin Bader
• Self-Delimiting Codes und Anwendungen
• Burrows Wheeler Transformation  (BWT) für XML Daten
• Implementierung eines Compressed Suffix Arrays (CST)
• Fraktale Bildkompression
  Die Fraktale Bildkompression ist ein verlustbehaftetes Kompressionsverfahren, welches auf der Selbstähnlichkeit gewisser Teilbereiche des Bildes beruht. Diese Selbstähnlichkeiten werden gesucht und als Funktionensystem dargestellt. Dieses Funktionensystem wird nun kompakt repräsentiert und enthält somit die komprimierten Daten des Bildes. Zum Dekomprimieren muss lediglich das Funktionensystem iterativ auf ein beliebiges Basisbild angewendet werden. Während die Dekomprimierung sehr einfach ist, erweist sich das Bestimmen des Funktionensystems als schwierige und sehr rechenintensive Aufgabe. Diese sowie ein patentrechtliches Problem haben bisher die Verbreitung der Fraktalen Bildkompression verhindert, momentan sind nur sehr wenige Implementierungen verfügbar. Trotzdem ist die Fraktale Bildkompression eine interessante Alternative zu JPEG. Desweiteren sind (hauptsächlich wegen der patentrechtlichen Probleme) auch noch nicht all zu viele Forschungsstunden in die Fraktale Bildkompression geflossen, was sie zu einer idealen Spielwiese macht. Im Praktikum soll nun ein En- und Decoder für die Fraktale Bildkompression geschrieben werden. Für den Encoder sollen verschiedene Heuristiken zur Beschleunigung der Kompression programmiert und getestet werden. Die Implementierung soll mit bestehender Software zur Fraktalen Bildkompression sowie mit einigen Standardgrafikformaten verglichen werden.
  Ansprechpartner: Martin Bader
• Bildkompression mittels Wavelet-Tree