Unter Datenkompression, auch Datenkomprimierung genannt, versteht man ein Algorithmenpaar (Codec, engl.: Coder, Decoder), welches aus einem Kompressions- und einem Dekompressionsalgorithmus besteht. Der Kompressionsalgorithmus konstruiert für eine Eingabe X eine Repräsentation Xc, welche möglichst weniger Bits als X benötigt. Der Dekompressionsalgorithmus wiederum generiert für ein gegebenes Xc eine Rekonstruktion Y. Häufig liegen dabei beide Repräsentationen X und Xc in derselben Abstraktionsebene. Es gibt zwei Arten der Kompression, die verlustfreie und die verlustbehaftete Kompression, weshalb ein Algorithmenpaar entweder verlustfrei oder verlustbehaftet sein kann.
Inhaltsverzeichnis
1 Motivation
1.1 Was ist Datenkompression?
1.2 Warum wollt ihr etwas über Kompression erfahren?
1.3 Wie kann man Daten komprimieren?
1.3.1 Verlustfreie Kompressionsverfahren
1.3.2 Verlustbehaftete Kompressionsverfahren
2 Grundbegriffe
2.1 Entropie
2.2 Variable Codelänge
2.3 Fano-Bedingung
3 Codierung
3.1 Shannon Codierung
3.2 Shannon-Fano Codierung
3.3 Huffman Codierung
4 Kompressionsverfahren
4.1 LZ77
4.2 Übersicht
4.2.1 Morse-Code
4.2.2 Forsyth-Edwards-Notation (FEN)
4.2.3 LZ78
4.2.4 LZW
4.2.5 LZSS, Deflate, ZLib
4.2.6 LZ4
4.2.7 Snappy, Zopfli, Brotli
4.3 Vergleich
4.3.1 Audio - ALS, FLAC, MP3, AAC, Dolby Digital
4.3.2 Bild - TIFF, BMP, JPEG, PNG, GIF
5 Weiterführende Inhalte
5.1 Adaptive Huffman-Codierung
5.2 Arithmetische Codes
5.3 Calgary-Corpus
5.4 USC-SIPI Image Database Suite
5.5 Kodak Lossless True Color Image Suite
5.6 Hutter Prize
Zielsetzung & Themen
Die vorliegende Arbeit vermittelt ein grundlegendes Verständnis für die Funktionsweise der Datenkompression, indem sie theoretische Konzepte der Codierung erläutert und eine Vielzahl praktischer Verfahren gegenüberstellt, um deren Effizienz und Einsatzgebiete zu verdeutlichen.
- Grundlagen der Informationstheorie und Entropie.
- Methoden der verlustfreien vs. verlustbehafteten Kompression.
- Detaillierte Analyse von Codierungsstrategien wie Shannon, Shannon-Fano und Huffman.
- Übersicht und technischer Vergleich gängiger Kompressionsalgorithmen (LZ-Familie, Audio- und Bildformate).
- Einblick in moderne Forschungsthemen und Testumgebungen für Kompressionsalgorithmen.
Auszug aus dem Buch
3.3 Huffman Codierung
1. Starte mit einem Wald aus Bäumen, in dem jeder Baum ein Symbol darstellt und wi = P(Ai) das Gewicht des Baumes ist.
2. Wiederhole solange, bis der Wald nur noch aus einem Baum besteht:
• Wähle zwei Bäume mit den kleinsten Gewichten w1 und w2.
• Verbinde diese zu einem neuen Baum mit dem Gewicht wr = w1+w2.
Beispiel 3.5. Sei wieder Σ = {a, b, c, d, e} ein Alphabet mit den gleichen Wahrscheinlichkeiten P(a)= 0.15, P(b)= 0.15, P(c)= 0.4, P(d)= 0.15 und P(e)= 0.15. So entsteht nach dem Algorithmus ein von den Blättern wachsender Binärbaum mit der zugehörigen Tabelle.
Zusammenfassung der Kapitel
1 Motivation: Definition der Datenkompression als Algorithmenpaar sowie Abgrenzung zwischen verlustfreien und verlustbehafteten Verfahren.
2 Grundbegriffe: Einführung in mathematische Grundlagen wie Entropie, variable Codelängen und die Fano-Bedingung.
3 Codierung: Erläuterung optimaler und nicht-optimaler Strategien zur Codierung mittels Shannon, Shannon-Fano und Huffman.
4 Kompressionsverfahren: Praktische Anwendung von Kompressionsalgorithmen von LZ77 bis hin zu modernen Audio- und Bildformaten.
5 Weiterführende Inhalte: Ausblick auf adaptive Methoden, arithmetische Codierung und Ressourcen für Benchmarks im Bereich Kompression.
Schlüsselwörter
Datenkompression, Codierung, Entropie, Huffman, Shannon-Fano, LZ77, Verlustfreie Kompression, Verlustbehaftete Kompression, Algorithmus, Binärbaum, Redundanz, Bitrate, Kompressionsfaktor, Datei-Formate, Informationstheorie.
Häufig gestellte Fragen
Was ist das zentrale Thema dieser Arbeit?
Die Arbeit behandelt die Grundlagen und Verfahren der Datenkompression, von der informationstheoretischen Basis bis hin zu konkreten Algorithmen für Text, Bild und Audio.
Welche Arten der Datenkompression werden unterschieden?
Es wird grundsätzlich zwischen verlustfreier Kompression, bei der Informationen vollständig wiederhergestellt werden können, und verlustbehafteter Kompression, bei der Redundanz und Irrelevanz zur Verkleinerung der Datenmenge entfernt werden, differenziert.
Was ist das Ziel einer Komprimierung?
Das primäre Ziel ist die Reduktion der Bit-Anzahl (Datenmenge) bei gleichzeitigem Erhalt oder akzeptabler Qualität der ursprünglichen Information.
Welche mathematischen Methoden spielen eine Rolle?
Die Arbeit verwendet unter anderem das Entropie-Maß nach Claude Shannon, die Kraftsche Ungleichung zur Prüfung der eindeutigen Dekodierbarkeit und statistische Häufigkeitsverteilungen.
Welche Codierungsalgorithmen werden im Hauptteil vorgestellt?
Detailliert besprochen werden die Shannon-Codierung, die Shannon-Fano-Codierung sowie die Huffman-Codierung als ein weit verbreitetes, optimales Verfahren.
Wie werden die verschiedenen Verfahren in Kapitel 4 analysiert?
Kapitel 4 vergleicht diverse Algorithmen anhand ihres Zeitstrahls sowie ihrer spezifischen Einsatzgebiete in der Audio- (z.B. MP3, AAC) und Bildverarbeitung (z.B. JPEG, PNG).
Wie funktioniert das Gleitfenster-Prinzip beim LZ77-Verfahren?
Das LZ77-Verfahren nutzt einen Absuch-Puffer (für bereits gelesene Daten) und einen Codier-Puffer, um Zeichensequenzen zu finden und durch Zeiger auf das Vorkommen im Puffer zu ersetzen.
Warum wird im Kontext des Brotli-Algorithmus ein vordefiniertes Wörterbuch genutzt?
Der Brotli-Algorithmus verwendet ein 120 kB großes Wörterbuch mit 13.000 häufigen Ausdrücken aus Text- und HTML-Dokumenten, um die Kompressionseffizienz gegenüber dem Deflate-Verfahren um ca. 20 % zu steigern.
- Arbeit zitieren
- Tim Kilian (Autor:in), 2017, Datenkompression. Grundlagen und Kompressionsverfahren, München, GRIN Verlag, https://www.grin.com/document/429837
