Datenkompression. Grundlagen und Kompressionsverfahren

Inhaltsverzeichnis

1 Motivation.. 1

1.1 Was ist Datenkompression?.. 1

1.2 Warum wollt ihr etwas über Kompression erfahren?.. 1

1.3 Wie kann man Daten komprimieren?.. 1

1.3.1 Verlustfreie Kompressionsverfahren.. 1

1.3.2 Verlustbehaftete Kompressionsverfahren.. 2

2 Grundbegriffe.. 2

2.1 Entropie.. 2

2.2 Variable Codelänge.. 3

2.3 Fano-Bedingung.. 3

3 Codierung.. 4

3.1 Shannon Codierung.. 4

3.2 Shannon-Fano Codierung.. 5

3.3 Huffman Codierung.. 6

4 Kompressionsverfahren.. 8

4.1 LZ77.. 8

4.2 Übersicht.. 9

4.2.1 Morse-Code.. 9

4.2.2 Forsyth-Edwards-Notation (FEN).. 9

4.2.3 LZ78.. 9

4.2.4 LZW.. 10

4.2.5 LZSS, Deflate, ZLib.. 10

4.2.6 LZ4.. 10

4.2.7 Snappy, Zopfli, Brotli.. 10

4.3 Vergleich.. 11

4.3.1 Audio - ALS, FLAC, MP3, AAC, Dolby Digital.. 11

4.3.2 Bild - TIFF, BMP, JPEG, PNG, GIF.. 12

5 Weiterführende Inhalte.. 13

5.1 Adaptive Huffman-Codierung.. 13

5.2 Arithmetische Codes.. 13

5.3 Calgary-Corpus.. 13

5.4 USC-SIPI Image Database Suite.. 13

5.5 Kodak Lossless True Color Image Suite.. 14

5.6 Hutter Prize.. 14

6 Literatur.. 15

1 Motivation

1.1 Was ist Datenkompression?

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 X_c,welche möglichst weniger Bits als X benötigt. Der Dekompressionsalgorithmus wiederum generiert für ein gegebenes X_c eine Rekonstruktion Y. Häufig liegen dabei beide Repräsentationen X und X_c in derselben Abstraktionsebene. Es gibt zwei Arten der Kompression, die verlustfreie und die verlustbehaftete Kompression, weshalb ein Algorithmenpaar entweder verlustfrei oder verlustbehaftet sein kann.

Definition 1.1 (verlustfrei, verlustbehaftet). Sei X eine Eingabe und Y eine Rekonstruktion, so ist ein Datenkompressionschema verlustfrei, wenn X = Y und verlustbehaftet, wenn X /= Y gilt.

1.2 Warum wollt ihr etwas über Kompression erfahren?

Jeder, der das Internet oder einen Computer benutzt, verwendet bewusst oder unbewusst Komprimierungsverfahren. Denn Kompression ist überall! Wenn man beispielsweise eine Seite im Internet öffnet, ein digitales Bild betrachtet oder ein Video schaut wurde es höchstwahrscheinlich komprimiert. Bewusst geschieht dies meist, wenn man Daten archiviert um den Speicherverbrauch zu reduzieren. Unbewusst dann eher beim digitalen Fernsehen oder beim digitalen Rundfunk, um die ü bertragungsraten zu senken. Ein natürliches Maß für die Qualität eines Komprimierungsschemas ist der Komprimierungsquotient (engl.: compression ratio), welcher das Verhältnis der Bit-Anzahl eines komprimierten Codes zur Bit-Anzahl des Originalcodes angibt.

Definition 1.2 (Kompressionsquotient, compression ratio, Kompressionsfaktor). Seien X die Bits der Eingabe und X_c die Bits einer Repräsentation, so nennt man X_c / X Kompressionsquotient und den Kehrwert Kompressionsfaktor.

Für eine gute Kompressionsqualität sollte man also versuchen, den Kompressionsfaktor möglichst groß zu bekommen. Leider ist die Verwendung der Begriffe Kompressionsquotient und Kompressionsfaktor in der Literatur uneinheitlich und wird oft einfach nur als compression ratio bezeichnet. Aus dem Zusammenhang sollte aber klar werden, welche Definition gemeint ist.

1.3 Wie kann man Daten komprimieren?

1.3.1 Verlustfreie Kompressionsverfahren (Redundanz)

Verlustfreie Techniken erlauben eine Reduktion der Datenmenge ohne Informationen zu verlieren, wodurch die originalen Daten vollständig durch eine Dekompression wiederhergestellt werden können. Jedoch ist dies nur bedingt möglich, da Daten eigentlich nicht komprimierbar sind. Laut der Kolmogorov-Komplexität benötigt man nämlich jeden Bit um eine Bitfolge zu beschreiben, wodurch auch zufällige Bitfolgen nicht komprimierbar sind. Trotzdem funktioniert Datenkompression in der Praxis hervorragend, da menschlich erzeugte Informationen häufig Redundanz enthalten, die man beseitigen kann. Beispielsweise tauchen Buchstaben, Silben oder Wörter nicht mit der gleichen Wahrscheinlichkeit auf, wodurch sie durch Verwendung kürzerer Bitketten mit Wörterbüchern oder Verweise auf bereits vorkommende Sequenzen ersetzt werden können.

1.3.2 Verlustbehaftete Kompressionsverfahren (Irrelevanz)

In manchen Anwendungen ist der Verlust von Informationen jedoch kein bedeutendes Problem. So kann man beispielsweise Daten weglassen, die vom menschlichen Auge oder Ohr gar nicht wahrgenommen werden oder einfach mehrfach vorkommen. Die verlustbehaftete Kompression befasst sich mit solchen Techniken und entscheidet dabei, welche Daten redundant sind und verworfen werden können. Der Kompressionsfaktor ist dabei bedeutend höher als bei der verlustlosen Kompression. So kann eine Information so weit reduziert werden, bis nur noch ein Bit übrig ist. Während verlustlose Kompression seine Grenzen hat, ist verlustbehaftete Kompression immer möglich. Jedoch reicht zur Qualitätsmessung jetzt nicht nur der Vergleich des Kompressionsquotienten, es muss auch der Unterschied zwischen der Rekonstruktion und der Eingabe bewertet werden. Diesen Unterschied nennt man Verzerrung. Typische Verzerrungsmaße sind das quadratische Fehlermaß und das Betragsfehlermaß.

2 Grundbegriffe

Im folgenden wird der Fokus auf verlustfreie Kompressionsverfahren gelegt, welche mit dem Teilgebiet Codierung zusammenarbeiten um Redundanz zu vermeiden. Zunächst sind jedoch die Definitionen folgender Begriffe notwendig um ein grundlegendes Verständnis für die Codierung zu bekommen.

2.1 Entropie

Claude Elwood Shannon definierte das Maß der Informationen als

[Formeln sind nicht enthalten in dieser Leseprobe.]

Das Verhalten des Informationsgehalts in Abhängigkeit zur Wahrscheinlichkeit P ist in Abbildung 1 grafisch dargestellt. Wenn ein Ereignis häufig vorkommt, dann enthält es nicht viel neue Informationen, wodurch der Informationsgehalt gering ist. Wenn es jedoch selten vorkommt, ist der Informationsgehalt sehr groß.

Abbildung 1: Das Maß der Informationen [LF11]

[Abbildungen und Tabellen sind nicht enthalten in dieser Leseprobe.]

Die Entropie bezeichnet einen Erwartungswert H(S) des Informationsgehalts und somit die mittlere Anzahl von Bits, um eine Nachricht zu codieren.

[...]