Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Proseminar (SS'07)

Datenkompression

[Zusammenfassung] [Themenliste] [Anmeldung] [Vorbesprechung] [Termine] [Hinweise]

Bitte wenden Sie sich mit Fragen an Hanjo Täubig oder Jens Ernst.

Zusammenfassung

Die immer bequemere Verfügbarkeit (über weltweite Vernetzung) immer größerer Datenmengen (u.a. Text, Audio, Video) verstärkt die Notwendigkeit, diese Daten in möglichst kompakter Form zu speichern und zu übermitteln. Das Proseminar behandelt grundlegende Techniken der Komprimierung von Daten, die in vielen Bereichen Anwendung finden.
Wir unterscheiden zwischen Komprimierung mit und ohne Verlust, sowie zwischen online- und offline-Komprimierung. Bei der verlustfreien Komprimierung kann die ursprüngliche Information durch Dekomprimierung exakt wiederhergestellt werden, während bei der Komprimierung mit Verlust zugunsten höherer Kompressionsdichte gewisse Details verlorengehen, was zum Beipiel bei der Komprimierung von Bildern tolerierbar ist. Im Falle der offline-Komprimierung stehen die gesamten Daten a priori zur Verfügung; bei der online-Komprimierung hingegen wird ein Datenstrom verarbeitet, dessen Verlauf sich erst während der Komprimierung ergibt.
Neben den praktischen Anwendungen wird im Proseminar auch Wert auf den theoretischen Hintergrund der Algorithmen gelegt.


Themenliste:

  1. Verlustfreie Komprimierung
    1. Informationstheorie
    2. Shannon-Fano-Kodierung
    3. Huffman-Kodierung
    4. Adaptive Huffman-Kodierung
    5. Arithmetische Kodierung
    6. Wörterbuchbasierte Kodierung, LZ77, LZ78 und LZW
    7. Run-Length Encoding, Fax-Kodierung
    8. QuadTree Komprimierung, Raumfüllende Kurven

  2. Verlustbehaftete Komprimierung
    1. Dynamisches fensterbasiertes RLE
    2. Block Truncation Coding
    3. Differentielle Kodierung
    4. Skalare Quantisierung
    5. Vektorquantisierung
    6. JPEG

Eine ausführliche Themenliste mit Literaturangaben folgt.

Anmeldung

* Interessentinnen/en können sich bei der Vorbesprechung oder vorab per eMail anmelden. In der E-Mail sollen folgende Informationen enthalten sein:

  • Name, Vorname
  • Studiengang und Studienfach
  • Semester
  • E-Mail (nur TUM-Adressen)
  • bevorzugtes Thema

Vorbesprechung

* Die Vorbesprechung findet am

Dienstag 30.01.2007, 14:15 Uhr

im Raum

MI 03.09.011B

statt.

Termine und Betreuer

Das Proseminar findet jeweils Dienstags von 14:15 Uhr (s.t.) bis 15:45 Uhr im Raum 03.11.018 statt.

Termin Teilnehmer Thema Betreuer
05.06.2007 Bombera, Christian Grundlagen der Informationstheorie,
Huffman-Code, Shannon-Fano-Code		 Johannes Nowak
12.06.2007 Grunow, Sebastian Arithmetische Kodierung
19.06.2007 Hasler, Stefanie Wörterbuchbasierte Kodierung, LZ, LZW Matthias Baumgart
26.06.2007 (noch frei) Run-Length Encoding, Fax-Kodierung
03.07.2007 Schaumeier, Andreas QuadTree Komprimierung, Raumfüllende Kurven
10.07.2007 Kawollek, Thomas JPEG Stefan Eckhardt

Die Teilnehmer, denen noch kein anderer Betreuer zugeordnet ist, wenden sich mit Fragen bitte an Hanjo Täubig oder Jens Ernst.

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Vortrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) unter LaTeX (Hinweise siehe unten).
Anwesenheit bei den Vorträgen Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortrag erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem Vortrag Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem Vortrag evt. Probevortrag in Absprache mit dem Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortrag fertige Ausarbeitung abgeben.

Hinweise zur Anfertigung der Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es kann der normale article-Style oder der LNCS-Style (die Datei llncs.cls) des Springer-Verlages verwendet werden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf den folgenden Link hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.

Literaturvorschläge

  1. W. Heise, P. Quattrocchi:
    Informations- und Codierungstheorie,
    Dritte Auflage, Springer-Verlag, 1995.

  2. G. Held, Th. R. Marshall:
    Data and Image Compression,
    Fourth edition, John Wiley & Sons, 1996.

  3. M. Nelson, J.-L. Gailly:
    The Data Compression Book,
    Second edition, M&T Books, 1996.

  4. D. Salomon:
    Data Compression - The Complete Reference,
    Springer-Verlag, 1998.

  5. K. Sayood:
    Introduction to Data Compression,
    Third edition, Morgan Kaufmann, 2006.

Weitere (thematische) Auskünfte bei: Jens Ernst oder Hanjo Täubig

Hanjo Täubig Last modified: Tue Oct 2 14:10:12 CEST 2007