Was ist Huffman-Kodierung?
Ein Verfahren, das aus den Wahrscheinlichkeiten der Symbole einen Präfixcode mit möglichst kleiner mittlerer Codewortlänge bildet. Durch wiederholtes Zusammenfassen der 2 Symbole (oder Knoten) mit den kleinsten Wahrscheinlichkeiten entsteht ein Baum, und an jeder Verzweigung werden 0 und 1 zugewiesen, um die Codewörter zu bilden. Je häufiger ein Symbol, desto kürzer sein Codewort. Der entstehende Huffman-Code ist unter den Präfixcodes, die Symbol für Symbol kodieren, optimal, und seine mittlere Codewortlänge ist mindestens die Entropie und kleiner als die Entropie + 1 Bit. Das Verfahren wird zusammen mit anderen Verfahren in Deflate (ZIP, gzip), JPEG und anderswo eingesetzt. Huffman veröffentlichte es 1952.
Japanische Bezeichnung: ハフマン符号
„Huffman-Kodierung“ kommt in 5 Übungsfragen aus 1 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung.
Fachgebiet: Grundlagen der Informationstheorie und Kodierung
Aufbau
Bei Symbolen mit den Wahrscheinlichkeiten 1/2, 1/4, 1/8 und 1/8 werden zuerst die beiden 1/8 zu 1/4 zusammengefasst, dann dieses mit dem 1/4 zu 1/2 und zuletzt mit dem verbleibenden 1/2. Beschriftet man die Verzweigungen von der Wurzel bis zu jedem Symbol mit 0 und 1, ergeben sich die Codewörter 0, 10, 110 und 111 und eine mittlere Codewortlänge von 1,75 Bit, gleich der Entropie. Ist jede Wahrscheinlichkeit der Kehrwert einer Zweierpotenz, stimmt die mittlere Codewortlänge auf diese Weise mit der Entropie überein.
Die Codewörter sind nicht eindeutig
Die Codewörter hängen davon ab, wie 0 und 1 zugewiesen werden und welche von zwei gleichen Wahrscheinlichkeiten zuerst zusammengefasst wird. Bei den Wahrscheinlichkeiten 0,4; 0,2; 0,2; 0,1 und 0,1 können die Codewortlängen zum Beispiel 1, 2, 3, 4, 4 oder 1, 3, 3, 3, 3 oder 2, 2, 2, 3, 3 sein, die mittlere Codewortlänge beträgt aber in jedem Fall 2,2 Bit. Deshalb wird in Prüfungen eher nach der mittleren Codewortlänge als nach den Codewörtern selbst gefragt.
Grenzen und Verbesserungen
Codewortlängen sind auf ganze Bits beschränkt; bei einer Quelle mit einem Symbol, dessen Wahrscheinlichkeit nahe 1 liegt, wird die Differenz zur Entropie daher groß. Kodiert man binäre Symbole einzeln, braucht man pro Symbol 1 Bit, wie ungleich sie auch verteilt sind. Gemeinsames Kodieren mehrerer Symbole oder ein Verfahren, das nicht an ganze Bits gebunden ist, wie die arithmetische Kodierung, bringt die Länge näher an die Entropie.
Häufige Fragen
Was wird benötigt, um mit einem Huffman-Code komprimierte Daten wiederherzustellen?
Man muss wissen, welchem Symbol welches Codewort zugeordnet wurde (eine Codetabelle oder die Codewortlänge jedes Symbols). Komprimierte Daten enthalten daher die Codetabelle oder verwenden eine vorab vereinbarte Tabelle. Deflate überträgt nur die Codewortlängen, und der Empfänger bildet die Codewörter nach derselben Regel neu (kanonische Huffman-Codes).
Kann ein Huffman-Code beliebige Daten verkleinern?
Nein. Sind die Symbolwahrscheinlichkeiten nicht ungleich verteilt, schrumpfen die Daten kaum. Treten zum Beispiel alle 256 Bytewerte gleich wahrscheinlich auf, ist jedes Codewort 8 Bit lang, und durch die Codetabelle wird das Ergebnis sogar größer.