Huffman-Codierung erklärt

Computer speichern meist jeden Buchstaben in derselben Anzahl Bit, acht im einfachen ASCII. Das ist einfach, aber verschwenderisch, denn manche Buchstaben sind weit häufiger als andere. 1951 fand ein Student den besten Weg, jedem Symbol einen Code eigener Länge zu geben, häufigen Symbolen kurze und seltenen lange, mit einer Konstruktion, die so einfach ist, dass sie in wenige Zeilen passt. Die Huffman-Codierung steckt heute in fast jeder komprimierten Datei, jedem Bild und jedem Ton, die Sie öffnen.

Ein Huffman-Baum mit den Buchstaben von ABRACADABRA als Blättern, mit 0 und 1 beschrifteten Kanten und dem hervorgehobenen kurzen Code von A
Ein Huffman-Baum mit den Buchstaben von ABRACADABRA als Blättern, mit 0 und 1 beschrifteten Kanten und dem hervorgehobenen kurzen Code von A

Kurze Codes für häufige Symbole

Der Morsecode nutzte die Idee schon in den 1830er-Jahren: E, der häufigste Buchstabe im Englischen, ist ein einziger Punkt, während Q Strich Strich Punkt Strich ist. Ein solcher Code spart Zeit und Platz, wann immer manche Symbole öfter vorkommen als andere. Doch variable Längen werfen ein Problem auf, das der Morsecode mit Pausen löste: Woher weiß man, wo ein Code endet und der nächste beginnt? Und welche Längen sollte jedes Symbol bekommen, damit die Gesamtlänge so klein wie möglich wird?

Präfixcodes

Das erste Problem verschwindet, wenn kein Code der Anfang eines anderen ist. Mit den Codes A = 0, B = 10, C = 110 und D = 111 lassen sich die Bits 0101100 nur als A B C A lesen: Sobald die bisher gelesenen Bits einen Code bilden, ist dieser Code vollständig. Solche Präfixcodes entsprechen genau den Binärbäumen mit den Symbolen an den Blättern, in denen jeder linke Zweig für 0 und jeder rechte für 1 steht. Einen Code wählen heißt einen Baum wählen.

Huffmans Konstruktion

Beginnen Sie mit einem Blatt pro Symbol, gewichtet damit, wie oft es vorkommt. Nehmen Sie die zwei leichtesten Bäume, verbinden Sie sie unter einem neuen Knoten, dessen Gewicht ihre Summe ist, und wiederholen Sie das, bis ein einziger Baum übrig ist. Das ist der ganze Algorithmus. Seltene Symbole werden zuerst verbunden und landen tief im Baum, mit langen Codes; häufige werden zuletzt verbunden und bleiben nahe der Spitze, mit kurzen Codes. Mit einer Prioritätswarteschlange braucht er eine Zeit proportional zu n log n bei n Symbolen.

Warum sie optimal ist

In einem bestmöglichen Baum lassen sich die zwei seltensten Symbole immer als Geschwister auf die tiefste Ebene setzen: Sie mit dem zu tauschen, was dort steht, kann die Gesamtlänge nur verkürzen. Fasst man sie zu einem Symbol mit ihrem gemeinsamen Gewicht zusammen, ist der Rest dasselbe Problem mit einem Symbol weniger, sodass der gierige Schritt die beste Lösung nie verbaut. Die Gesamtzahl der verwendeten Bits ist gleich der Summe der Gewichte aller inneren Knoten, und das Verbinden hält sie so klein wie möglich.

Eine Hausarbeit statt einer Prüfung

1951 besuchte David Huffman, Doktorand am MIT, den Kurs von Robert Fano über Informationstheorie. Fano ließ seinen Studenten die Wahl: die Abschlussprüfung ablegen oder eine Hausarbeit darüber schreiben, wie man den effizientesten Binärcode findet. Huffman hätte die Arbeit beinahe aufgegeben, sah dann aber, dass der Aufbau des Baums von unten nach oben, statt der Teilung von oben nach unten wie beim Shannon–Fano-Verfahren, immer das beste Ergebnis liefert. Er veröffentlichte es 1952; das Verfahren des Studenten schlug das, das sein Professor mit Claude Shannon ausgearbeitet hatte.

David Huffman, fotografiert als Professor an der UC Santa Cruz. Als Doktorand am MIT fand er 1951 seinen optimalen Code in einer Hausarbeit für Robert Fanos Kurs.
David Huffman, fotografiert als Professor an der UC Santa Cruz. Als Doktorand am MIT fand er 1951 seinen optimalen Code in einer Hausarbeit für Robert Fanos Kurs.
Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.
Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.

Nahe an der Entropie

Claude Shannon zeigte, dass kein Code im Mittel weniger Bit pro Symbol verwenden kann als die Entropie der Quelle. Ein Huffman-Code erreicht die Entropie genau dann, wenn jede Wahrscheinlichkeit eine Potenz von einhalb ist, und liegt nie ein volles Bit pro Symbol darüber. Die Lücke zählt, wenn ein Symbol sehr häufig ist: Ein Symbol mit einem Anteil von 99 % braucht immer noch mindestens ein ganzes Bit, obwohl es nur etwa 0,015 Bit Information trägt. Die arithmetische Codierung und die asymmetrischen Zahlensysteme (ANS) neuerer Kompressoren umgehen diese Grenze.

Huffman-Codes überall

Die Huffman-Codierung wird selten allein verwendet, bildet aber die letzte Stufe vieler Formate. Deflate, in ZIP, gzip und PNG, ersetzt zuerst Wiederholungen durch Verweise und schreibt das Ergebnis dann mit Huffman-Codes. JPEG verwendet sie für die Zahlen, die nach seiner Transformation des Bildes übrig bleiben, MP3 für seine Audiodaten und Faxgeräte für die Längen schwarzer und weißer Läufe. Formate übertragen meist einen kanonischen Huffman-Code, bei dem nur die Codelängen gespeichert werden müssen, weil sich die Codes selbst daraus rekonstruieren lassen.

Probieren Sie es aus

Öffnen Sie den Huffman-Codierer, um den Baum von ABRACADABRA, MISSISSIPPI RIVER, einem eigenen Satz oder einem beliebigen anderen Text Schritt für Schritt aufzubauen. Sehen Sie zu, wie sich bei jedem Schritt die zwei leichtesten Bäume verbinden, klicken Sie auf ein Blatt, um seinen Code zu sehen, verfolgen Sie ein Symbol durch die codierten Bits und vergleichen Sie die Gesamtlänge mit einem Code fester Länge, UTF-8 und der Entropie.

Häufig gestellte Fragen

Was ist der Unterschied zwischen Huffman- und Shannon–Fano-Codierung?

Die Shannon–Fano-Codierung baut den Baum von oben auf, indem sie die Symbole immer wieder in zwei Gruppen von nahezu gleichem Gewicht teilt. Sie ist oft gut, aber nicht immer optimal. Huffman baut den Baum von unten auf, indem er die zwei leichtesten Bäume verbindet, und liefert immer den kürzestmöglichen Präfixcode.

Braucht der Decoder den Baum?

Ja, er braucht denselben Code. Komprimierte Dateien speichern ihn deshalb, meist als Liste von Codelängen für einen kanonischen Code, was nur einige Dutzend Byte belegt. Bei kurzen Texten kann dieser Zusatzaufwand die Ersparnis übersteigen; der Codierer zählt nur die codierten Bits.

Kann die Huffman-Codierung eine Datei vergrößern?

Die codierten Symbole belegen nie mehr Bit als ein Code fester Länge für dieselben Symbole. Aber die Codetabelle muss ebenfalls gespeichert werden, sodass das Ergebnis bei sehr kurzen oder nahezu zufälligen Daten etwas größer als das Original sein kann.

Was besagt die Kraft-Ungleichung?

Dass ein Präfixcode mit den Codelängen l₁, l₂, … genau dann existiert, wenn die Summe von 2 hoch −l über alle Symbole höchstens 1 ist. Für einen vollständigen Baum, wie jeden Huffman-Baum mit mindestens zwei Symbolen, ist die Summe genau 1.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Huffman-Codierer öffnen