Datenkompression: RLE, Huffman und LZW erklärt

Bei der Datenkompression wird die Menge digitaler Daten kleiner gemacht. Dadurch sinkt der Speicherbedarf, und die Daten kommen schneller an. Das Gegenstück heißt Dekompression: Die Daten werden wieder entpackt.

Bei der verlustfreien Kompression kannst du aus den komprimierten Daten wieder exakt die Originaldaten gewinnen. Das ist zum Beispiel bei ausführbaren Programmdateien notwendig. Solche Verfahren nutzen Redundanz. Das sind überflüssige, wiederholte Informationen, die man kürzer aufschreiben kann.

Bei der verlustbehafteten Kompression geht ein Teil der Information verloren. Die Originaldaten lassen sich meist nicht mehr exakt zurückgewinnen. Die Verfahren versuchen, möglichst nur „unwichtige“ Informationen wegzulassen. Man nutzt sie häufig bei Bildern, Video und Ton. Ein bekanntes Beispiel ist MP3: Es entfernt Frequenzmuster (Tonanteile), die der Mensch schlecht oder gar nicht hört.

Bei Live-Übertragungen sind Qualitätseinbußen vertretbar, wenn dafür die mögliche Übertragungsrate eingehalten wird. Bei Telefongesprächen wird der Gesprächspartner oft auch bei schlechter Tonqualität noch verstanden.

Bei der Lauflängencodierung (englisch run-length encoding, kurz RLE) werden gleiche Zeichen, die hintereinander stehen, nur einmal gespeichert – mit der Anzahl ihrer Wiederholungen. RLE ist verlustfrei und eignet sich für längere Wiederholungen von Symbolen.

Aus einer Folge aus fünf A wird zum Beispiel „A5“. Bei Texten brauchst du also beides: das Zeichen und die Anzahl.

Wie gut RLE wirkt, hängt von der Länge der Wiederholungen ab. Für 10 Wiederholungen brauchst du zwei Dezimalstellen, für 100 drei, für 1000 vier. Die Zahl wächst also viel langsamer als die Folge. Bei langen Wiederholungen spart man deshalb erheblich Speicherplatz. Umgekehrt ist die Einsparung umso geringer, je kürzer die Wiederholungen sind. Im ungünstigsten Fall, ganz ohne Wiederholungen, ist die „komprimierte“ Nachricht größer als das Original: Aus ABCD würde A1B1C1D1.

Gute Ergebnisse erzielt RLE zum Beispiel bei Schwarz-Weiß-Seiten, die per Fax gesendet werden. Dort wechseln sich lange weiße Bereiche mit kürzeren schwarzen ab. Bei Bitfolgen gibt es nur Nullen und Einsen. Sender und Empfänger vereinbaren, mit welchem Bit man beginnt. Danach werden abwechselnd die Längen der Null-Folgen und der Eins-Folgen übertragen.

Die Huffman-Kodierung wurde 1952 von David A. Huffman entwickelt. Sie gibt jedem Zeichen ein Codewort aus Bits. Die Codewörter haben unterschiedliche Längen. Häufiger vorkommende Zeichen bekommen weniger Bits als seltener vorkommende. Üblicherweise wird die Huffman-Kodierung für verlustfreie Kompression benutzt.

Damit man die Bits ohne Trennzeichen wieder entschlüsseln kann, muss der Code präfixfrei sein: Kein Codewort darf der Beginn eines anderen sein. So prüfst du das: Nimm jedes Codewort und schau, ob ein anderes Codewort mit genau diesen Bits anfängt. Wenn ja, ist der Code nicht präfixfrei. Bei den Codewörtern 1 und 10 ist zum Beispiel 1 der Beginn von 10. Ein solcher Code braucht Trennzeichen.

Die mittlere Codewortlänge sagt, wie viele Bits ein Zeichen im Durchschnitt braucht. Du multiplizierst die Länge jedes Codeworts mit der Häufigkeit seines Zeichens und addierst alles. Häufigkeiten schreibst du als Anteile, zum Beispiel 0,4 für 40 Prozent.

Der Huffman-Baum liefert garantiert eine optimale und präfixfreie Kodierung. Es gibt dann kein Verfahren, das jedes Zeichen einzeln codiert und einen kürzeren Code liefert, wenn die Wahrscheinlichkeiten der Zeichen bekannt sind. Zum Entpacken braucht man beim klassischen Verfahren außerdem das Codebuch, das beim Komprimieren erstellt wurde.

LZW (nach Lempel, Ziv und Welch) ist ein verlustfreies Verfahren. Es arbeitet mit einem Wörterbuch. Das ist eine Tabelle, in der Zeichenketten eine Nummer bekommen. Das Wörterbuch wächst während des Komprimierens und passt sich so dem Inhalt an.

Am Anfang sind die Einträge 0 bis 255 schon mit den einzelnen Bytes gefüllt. Neue Einträge beginnen deshalb bei der Nummer 256.

So geht der Algorithmus vor: Erst suchst du am Anfang der restlichen Eingabe das längste Muster, das schon im Wörterbuch steht, und gibst seine Nummer aus. Dann hängst du das nächste Zeichen der Eingabe an dieses Muster an und speicherst das Ergebnis als nächsten Eintrag. So geht es immer weiter.

Das Wörterbuch muss nicht mitgeschickt werden. Der Dekompressor, also das Programm zum Entpacken, baut es aus den komprimierten Daten selbst wieder auf. Im Beispiel unten hat die Eingabe 22 Zeichen zu je 8 Bit, das sind 176 Bit. Am Ende stehen dort 16 Zeichen zu je 12 Bit, das sind 192 Bit. Bei dieser kurzen Eingabe ist das Ergebnis also nicht kürzer.

Verlustfrei lassen sich nur Daten komprimieren, die in irgendeiner Form redundant sind. Hat eine Datei keinerlei erkennbare Struktur, gibt es nichts, was man kürzer aufschreiben könnte.

Dazu kommt das Taubenschlagprinzip: Gibt es weniger Nistplätze als Tauben, müssen sich zwei oder mehr Tauben einen Nistplatz teilen. Auf n Bit passen 2ⁿ mögliche Informationen. Mit einem Bit weniger gibt es nur halb so viele. Auf 16 Bit passen 2¹⁶ = 65536 Informationen, auf 15 Bit nur 2¹⁵ = 32768.

Angenommen, jede Datei ließe sich um ein Bit verkleinern. Dann müssten sich zwei verschiedene Originale dasselbe kürzere Muster teilen. Bei verlustfreier Kompression muss aber jede komprimierte Datei zu genau einem Original gehören. Das geht nicht.

Ein zweiter Gedanke: Gäbe es ein Verfahren, das jede Datei um mindestens ein Bit kürzt, könnte man es immer wieder auf das Ergebnis anwenden. Jede Information ließe sich dann auf 0 Bit reduzieren. Das kann nicht stimmen.

Also lassen sich zwar viele, aber nicht alle Daten komprimieren. Rein zufällige Daten sind höchstwahrscheinlich unkomprimierbar. Verlustbehaftete Kompression ist dagegen stets möglich, denn man kann immer mehr „Unwichtiges“ weglassen.