Fachbeitrag «Verlustlose Kompression»

Die verlustlose Komprimierung von Daten

Man spricht von verlustfreier Kompression oder Redundanzreduktion, wenn aus den komprimierten Daten wieder alle Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig.

Bei der verlustbehafteten Kompression oder Irrelevanzreduktion können die Originaldaten nicht mehr aus den komprimierten Daten zurückgewonnen werden, das heisst, ein Teil der Information geht verloren. Solche Verfahren werden häufig zur Bild- Video- und Audiodatenkompression eingesetzt. Sie finden Informationen zur verlustbehafteten Kompression in den Multimedia-Fachartikeln unter Bildkompression.

1. Die Huffman-Kodierung

Die Huffman-Kodierung ist eine Form der Entropiekodierung. Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. Der Huffman-Code ist ein VLC (Variable Length Code)

Huffman-Kodierung am Textbeispiel «ERDBEERE»:

Das Wort «ERDBEERE» zählt 8 Buchstaben. Zuerst soll die Häufigkeit der einzelnen Buchstaben ermittelt werden.

Nun erstellt man einen binären Baum: Die am wenigsten häufigen Buchstaben werden zu einem übergeordneten Knoten zusammengefasst
Und so geht das entsprechend weiter bis zuoberst. Die Zahl 8 muss der Anzahl Buchstaben in Wort «ERDBEERE» entsprechen. Danach müssen die Äste des Baums beschriften werden - Nach Links 1 und nach Rechts 0 (Ginge auch umgekehrt)

Nun hat man den Huffman-Code für das Wort «ERDBEERE» ermittelt. (Mit nur 14 Bit ein Leichtgewicht gegenüber dem Wort «ERDBEERE» als ASCII-Text mit 8 x 8Bit (=64Bit)

Folgende Lösungen wären auch möglich bzw. das letzte Beispiel zeigt den Aufbau eines falschen binären Baums

2. RLC/RLE - Run Length Coding/Encoding

Mit Run Length Encoding ist eine Lauflängenkodierung gemeint. Jede Sequenz von identischen Symbolen soll durch deren Anzahl und ggf. das Symbol ersetzt werden. Somit werden nur die Stellen markiert, an denen sich das Symbol in der Nachricht ändert. Effizient bei langen Wiederholungen.

RLE-Bit-Berechnung für die ersten vier Zeilen:
Der Speicherbedarf für das normale Bitmap: 4 Zeilen zu je 20 Pixel = 80Bit

Der Speicherbedarf für das RLE-komprimierte Bild:
Ab erstem Pixel oben links 31 x Weiss,  2 x Schwarz,  11 x Weiss,  3 x Schwarz, 2 x Weiss,  6 x Schwarz,  6 x Weiss,  6 x Schwarz,  1 x Weiss,  8 x Schwarz,  4 x Weiss  ergibt 11 Zahlen oder Farbwechsel.
Die Zahlen in Dualcode:  11111  00010  01011 00011 00010 00110 00110 00001 01000 00100
Zusammenfassend RLE: 11 x 5Bit = 55Bit


3. Burrows-Wheeler-Transformation (BWT)

Neben RLE Run-Length-Encoding und Huffman-Codierung ist die Burrows-Wheeler-Transformation (BWT) eine weitere Art, wie Daten verlustlos komprimiert werden können. BWT ist allerdings kein Algorithmus, der Daten direkt komprimiert. Vielmehr besteht seine Aufgabe darin, das Datenmaterial für eine anschliessende effektive Datenreduktion mit z.B. RLC vorzubereiten.

Beispiel für BWT: Das Wort «ERDBEERE» soll mit BWT verlustlos datenreduziert bzw. komprimiert werden.

Und die Rücktransformation:

4. Lempel-Ziv-Welch-Algorithmus (LZW)

Auch der Lempel-Ziv-Welch-Algorithmus (LZW) ermöglicht es, Daten verlustlos zu komprimieren. LZW wird häufig bei der Datenreduktion von Grafikformaten (GIF, TIFF) verwendet.

Beispiel für LZW: Das Wort «ENTGEGENGENOMMEN» soll verlustlos datenreduziert bzw. komprimiert werden. Die Werte 0 bis 255 sind den ASCII-Zeichen vorbehalten. Die Werte ab 256 sind Indexe, die auf einen Wörterbucheintrag verweisen.

Und die Rücktransformation:

Weitere verlustlose Datenreduktionsverfahren entnehme man der entsprechenden Fachliteratur.