Seminar Datenkompression

Aktuelles

Eine Vorbesprechung findet am 17.04.2012 um 16.15 Uhr in O27/531 (Seminarraum des Instituts für Theoretischen Informatik) statt. Dabei werden inbesondere die Themen vorgestellt. Die Themenvergabe selbst erfolgt per E-Mail. Eine Teilnahme an der Vorbesprechung ist empfohlen, aber nicht verpflichtend.

Ankündigung

Das Seminar kann entweder wöchentlich oder als Blockseminar am Ende des Semester stattfinden. Dies entscheiden die Seminarteilnehmer. Zu Beginn des Semesters wird es eine Vorbesprechung mit Themenvergabe geben.

Inhalt

In diesem Seminar sollen verschiedene Themen der Datenkompression bearbeitet werden. Der Schwerpunkt wird hierbei bei Methoden und Algorithmen zur verlustfreien Datenkompression liegen.

Es stehen unter anderem folgenden Themen zur Auswahl:

LZ77 Faktorisierung

Falls Sie ein Thema bearbeiten möchten, schicken Sie mir bitte eine E-Mail. Es können gerne eigene Themen vorgeschlagen werden.

Folgende Themen wurden bereits vergeben:

Grundlagen verlustfreier Datenkompression
Huffman-Codierung
Arithmetische Codierung
LZ77 und LZMA
LZ78 und LZW
PPM
Kompression von Integern
BWT (Burrows-Wheeler-Transformation)
Grammatik basierte Kompression
JPEG-Verfahren

Literatur

D. Salomon: Data Compression. The Complete Reference. Springer, 2007.
K. Sayood: Introduction to Data Compression. Morgan Kaufmann, 2006.
A. Moffat, A. Turpin: Compression and coding algorithms. Kluwer Academic Publishers, 2002.

(Die verlinkten PDF-Dateien sind vom Uni-Netz aus kostenfrei zugänglich.)

Huffman-Codierung:
A Method for the Construction of Minimum-Redundancy Codes

LZ77 und LZMA:
A universal algorithm for sequential data compression

LZ77 Faktorisierung:
Computing longest previous factor in linear time and applications
Lempel-Ziv Factorization Revisited

LZ78 und LZW:
Compression of individual sequences via variable-rate coding
A Technique for High-Performance Data Compression

PPM:
Unbounded length contexts for PPM

BWT:
A block sorting lossless data compression algorithm
The Burrows-Wheeler Transform: Theory and Practice

Grammatik-basierte Kompression:
The smallest grammar problem