Huffman Coding
Die Huffman-Kodierung, 1952 von David Huffman veröffentlicht, ist ein Konstruktionsalgorithmus für Präfixcodes, der häufigen Symbolen kurze und seltenen lange Codes zuweist und die Entropie-Untergrenze erreicht.
Zweck
Sie baut optimale Präfixcodes für verlustfreie Kompression, wenn die Symbolfrequenzen bekannt sind, und ist das Backend von DEFLATE, JPEG und MP3.
Mechanismus
Symbolfrequenzen zählen und einen Huffman-Baum bauen: Die zwei niederfrequentesten Knoten werden wiederholt zu einem neuen Elternteil verschmolzen, bis nur die Wurzel bleibt; der Pfad Wurzel-zu-Blatt (links 0, rechts 1) liefert jedes Symbolcode. Häufige Symbole erhalten kurze Pfade.
Anwendungsfälle
- Entropiekodierungsstufe in DEFLATE
- Entropiekodierungsstufe in JPEG/MP3
- Backend der Textkompression