Kompressionsverfahren

Es gibt viele verschiedene Arten der Kompression, die sich in mehreren Punkten voneinander unterscheiden, sodass man sie grob in mehrere Kategorien einteilen kann. Im Folgenden werden die wichtigsten Unterscheidungskriterien vorgestellt.

Unterscheidung nach Laufzeitkomplexität

Grundsätzlich unterscheidet man bei Laufzeitkomplexität in symmetrische und asymmetrische Kompressionsverfahren. Dabei wird die Laufzeit von Kodierung und Dekodierung miteinander verglichen.

Symmetrische Kompressionsalgorithmen

Stimmen die Laufzeiten des Kodierungs- und Dekodierungsvorganges miteinander überein, spricht man von symmetrischer Kompression. Im Prinzip heißt das, dass die Kodierung genauso schnell durchgeführt werden kann wie die Dekodierung (und natürlich auch umgekehrt).

Beispiele für symmetrische Kompressionsalgorithmen:

RLE - Runlength-Encoding
LZW - Lempel-Ziv-Welch

Asymmetrische Kompressionsalgorithmen

Bei asymmetrischen Verfahren sind die Laufzeiten für die Komprimierung und Dekomprimierung unterschiedlich. Das ist der Fall, wenn die Kompression länger oder kürzer benötigt als die Wiederherstellung der ursprünglichen Daten.

Beispiel für asymmetrische Kompressionsalgorithmen:

Wavelet

Unterscheidung nach Rekonstruierbarkeit

Hierbei unterscheidet man in verlustfreie und verlustbehaftete Verfahren.

Verlustfreie Kompressionsverfahren

Von verlustfreier Kompression spricht man, wenn man die ursprünglichen Daten, genau so wie sie vorher waren, wieder herstellen kann.

Beispiele für verlustfreie Kompressionsalgorithmen:

RLE - Runlength-Encoding
Huffman-Kodierung
LZW - Lempel-Ziv-Welch

Verlustbehaftete Kompressionsverfahren

Können die Originaldaten nach der Kompression nicht mehr 1:1 hergestellt werden, so spricht man von verlustbehafteter Kompression (da Informationen über die Ausgangsdaten verloren gehen).

Beispiele für verlustbehaftete Kompressionsalgorithmen:

Wavelet

Unterscheidung nach der Berücksichtigung der Quelle oder Art der Daten

Hierbei unterscheidet man Entropiekodierung und Quellen-Komprimierung.

Entropiekodierung

Bei der Entropiekodierung werden Daten als Folge digitaler Werte verlustfrei komprimiert. Man berücksichtigt dabei nicht, was durch die Folge der digitalen Werte beschrieben wird

Beispiele für Entropiekodierung:

RLE - Runlength-Encoding
Huffman-Kodierung
LZW - Lempel-Ziv-Welch

Quellen-Komprimierung

Je nach Quelle oder Art der Daten werden Kompressionsverfahren eingesetzt, die besondere Eigenschaften der Quelldaten ausnutzen, meist auch mit (hinnehmbaren) Verlusten.
Beispiele: Transformationskodierung wie DCT.

RLE - Runlength-Endcoding
RLE (zu Deutsch Lauflängen-Kodierung) ist ein sehr einfaches Verfahren zur Datenkompression - Passagen mit sich wiederholenden identische Zeichen werden zusammengefasst und durch die Anzahl der gleichen Zeichen ersetzt (z.B. 4A statt AAAA).
Die Dekodierung erfolgt eben so einfach und vollkommen verlustfrei indem die Folge wieder ausgeschrieben wird.
Besonders geeignet ist dieses Kompressionsverfahren für einfache Grafiken, die viele gleichfarbige Flächen enthalten (wie beispielsweise Diagramme oder technische Zeichnungen), da hier häufig längere Reihen gleicher Zeichen vorkommen. Ungeeignet ist RLE hingegen für komplexe Farbbilder.

RLE - Runlength-Endcoding

Huffman-Kodierung
Die Grundidee bei der Huffman-Kodierung ist, dass häufig vorkommenden Zeichen ein kurzer Code zugeordnet wird, selten auftretenden ein langer.
Der Huffman-Algorithmus basiert darauf, dass allen Zeichen, die im jeweiligen Datenstrom vorkommen können, ein Endknoten in einem Binärbaum zugeordnet wird. Den Endknoten wird wiederum die Auftrittshäufigkeit des jeweiligen Zeichens zugewiesen. Dadurch dass immer die beiden Knoten mit der geringsten Auftrittshäufigkeit einem neuen Knoten untergeordnet werden, dem die Summe der beiden Auftrittswahrscheinlichkeiten zugeordnet wird, entsteht die Baumstruktur. Der Vorgang wiederholt sich so oft, bis alle Knoten in einer Wurzel zusammengeführt sind. Den Kanten des Baums werden die binären Werte 0 und 1 zugeordnet, der Weg von der Baumwurzel bis hin zum Zeichen am unteren Ende des Baums, ergibt dann den Huffman-Code.

Huffman-Kodierung

LZW - Lempel-Ziv-Welch
LZW ist ein verlustfreier, symmetrischer und adaptiver Kompressionsalgorithmus der sowohl auf Bild- als auch auf Textdaten angewendet werden kann.
LZW komprimiert mittels Lexikon/Wörterbuch in dem die am häufigsten vorkommenden Zeichenketten gespeichert werden und im kodierten Datenstrom nur noch mit Abkürzungen angesprochen werden müssen. Das Lexikon muss nicht zusätzlich abgespeichert werden, sondern der Decoder ist in der Lage, dass Lexikon aus dem Datenstrom zu rekonstruieren und somit auch die Daten zu dekomprimieren.

LZW - Lempel-Ziv-Welch

Wavelet
Generell werden Wavelets mit einer Kompressionsmethode assoziiert. Aber das Wort Wavelet bedeutet zugleich eine mathematische Theorie, eine Kompressionsmethode und ein Datenanalyse-Werkzeug. Es ist ein mächtiges Paradigma, das viele Anwendungen hat.

Wavelet

Hier findet man eine kompakte Gegenüberstellung der Kompressionsverfahren: