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 und Themenschwerpunkte
Die Arbeit befasst sich mit dem Prinzip der Datenkompression. Ziel ist es, ein grundlegendes Verständnis für verlustfreie Kompressionsverfahren zu vermitteln und verschiedene Methoden und Algorithmen vorzustellen. Die Arbeit erläutert die zugrundeliegenden Konzepte und Prinzipien.
- Grundlagen der Datenkompression (verlustfrei und verlustbehaftet)
- Konzepte wie Entropie und variable Codelänge
- Wichtige Codierungsverfahren (Shannon, Huffman)
- Überblick über verschiedene Kompressionsverfahren (LZ77, LZ78, etc.)
- Vergleich verschiedener Verfahren für Audio und Bilddaten
Zusammenfassung der Kapitel
1 Motivation: Dieses Kapitel führt in das Thema Datenkompression ein, definiert den Begriff und unterscheidet zwischen verlustfreien und verlustbehafteten Verfahren. Es erläutert die Relevanz von Kompressionsverfahren im Alltag und definiert den Kompressionsquotienten als Maß für die Effizienz eines Verfahrens. Die Unterscheidung zwischen Redundanz (verlustfreie Kompression) und Irrelevanz (verlustbehaftete Kompression) als Grundlage für die Komprimierung wird hier eingeführt.
2 Grundbegriffe: Kapitel 2 legt die theoretischen Grundlagen für das Verständnis der folgenden Kapitel. Es definiert zentrale Konzepte wie Entropie nach Shannon als Maß für den Informationsgehalt und erklärt das Prinzip der variablen Codelänge zur Optimierung der Kompression. Die Fano-Bedingung für Präfixcodes wird eingeführt, um die Eindeutigkeit bei variabler Codelänge zu gewährleisten.
3 Codierung: Dieses Kapitel behandelt verschiedene Codierungsverfahren, die für die Datenkompression essentiell sind. Es beschreibt die Shannon-Codierung, die Shannon-Fano-Codierung und die Huffman-Codierung. Die Kapitel beschreibt die jeweiligen Algorithmen und deren Eigenschaften im Kontext der Datenkompression.
4 Kompressionsverfahren: Hier werden konkrete Kompressionsverfahren detailliert erläutert, darunter LZ77 und weitere Verfahren der LZ-Familie (LZ78, LZW, LZSS), sowie ein Vergleich verschiedener Verfahren für Audio- und Bilddaten. Der Abschnitt bietet einen umfassenden Überblick über etablierte Algorithmen und deren Anwendung in verschiedenen Medienformaten.
Schlüsselwörter
Datenkompression, verlustfreie Kompression, verlustbehaftete Kompression, Entropie, variable Codelänge, Shannon-Codierung, Huffman-Codierung, LZ77, LZ78, LZW, Kompressionsquotient, Redundanz, Irrelevanz.
Häufig gestellte Fragen (FAQ) zu "Datenkompression"
Was ist der Inhalt dieses Dokuments?
Dieses Dokument bietet einen umfassenden Überblick über das Thema Datenkompression. Es beinhaltet ein Inhaltsverzeichnis, eine Beschreibung der Zielsetzung und der Themenschwerpunkte, Zusammenfassungen der einzelnen Kapitel und eine Liste wichtiger Schlüsselwörter. Der Fokus liegt auf verlustfreien Kompressionsverfahren und den zugrundeliegenden Prinzipien.
Welche Themen werden behandelt?
Das Dokument behandelt die Grundlagen der Datenkompression, darunter verlustfreie und verlustbehaftete Verfahren. Es erklärt Konzepte wie Entropie und variable Codelänge und beschreibt wichtige Codierungsverfahren wie die Shannon-Codierung und die Huffman-Codierung. Darüber hinaus werden verschiedene Kompressionsverfahren wie LZ77, LZ78, LZW und weitere Algorithmen der LZ-Familie detailliert erläutert und im Kontext von Audio- und Bilddaten verglichen. Zusätzlich werden weiterführende Themen wie adaptive Huffman-Codierung und arithmetische Codes angesprochen.
Welche Arten von Datenkompression werden unterschieden?
Es wird zwischen verlustfreien und verlustbehafteten Kompressionsverfahren unterschieden. Verlustfreie Verfahren ermöglichen eine vollständige Wiederherstellung der ursprünglichen Daten nach der Dekompression, während verlustbehaftete Verfahren Informationen verwerfen, um eine höhere Kompressionsrate zu erzielen. Der Fokus des Dokuments liegt auf verlustfreien Verfahren.
Welche wichtigen Konzepte werden erklärt?
Wichtige Konzepte umfassen die Entropie als Maß für den Informationsgehalt, variable Codelänge zur Optimierung der Kompression und die Fano-Bedingung zur Gewährleistung eindeutiger Decodierung. Der Kompressionsquotient als Maß für die Effizienz eines Verfahrens wird ebenfalls erläutert. Die Unterscheidung zwischen Redundanz (verlustfreie Kompression) und Irrelevanz (verlustbehaftete Kompression) als Grundlage für die Komprimierung wird ebenfalls thematisiert.
Welche Codierungsverfahren werden beschrieben?
Das Dokument beschreibt die Shannon-Codierung, die Shannon-Fano-Codierung und die Huffman-Codierung. Für jedes Verfahren werden der Algorithmus und dessen Eigenschaften im Kontext der Datenkompression erläutert.
Welche Kompressionsverfahren werden behandelt?
Das Dokument behandelt detailliert LZ77 und andere Verfahren der LZ-Familie, wie LZ78, LZW, und LZSS. Es bietet auch einen Überblick über weitere Algorithmen wie Deflate, ZLib, LZ4, Snappy, Zopfli und Brotli und vergleicht verschiedene Verfahren für Audio- (z.B. ALS, FLAC, MP3, AAC, Dolby Digital) und Bilddaten (z.B. TIFF, BMP, JPEG, PNG, GIF).
Gibt es weiterführende Informationen?
Ja, das Dokument erwähnt weiterführende Themen wie adaptive Huffman-Codierung, arithmetische Codes und verschiedene Datenbanken mit Testdaten für die Evaluierung von Kompressionsverfahren (Calgary-Corpus, USC-SIPI Image Database Suite, Kodak Lossless True Color Image Suite) sowie den Hutter Prize, einen Wettbewerb zur Datenkompression.
Welche Schlüsselwörter sind relevant?
Wichtige Schlüsselwörter sind: Datenkompression, verlustfreie Kompression, verlustbehaftete Kompression, Entropie, variable Codelänge, Shannon-Codierung, Huffman-Codierung, LZ77, LZ78, LZW, Kompressionsquotient, Redundanz, Irrelevanz.
- Quote paper
- Tim Kilian (Author), 2017, Datenkompression. Grundlagen und Kompressionsverfahren, Munich, GRIN Verlag, https://www.grin.com/document/429837
