Filter: 2013-09-22

Huffman-Kodierung

Die Huffman-Kodierung stellt neben der arithmetischen Kodierung bzw. der Bereichskodierung eine der häufigsten Formen der Entropiekodierung dar. Es wird und wurde vor allem, wegen der hohen Geschwindigkeit in älteren Kompressionsverfahren eingesetzt, von ZIP/Deflate über RAR bis hin zu JPEG. Allerdings gibt es auch einen kleinen Nachteil: Die Kodierung erreicht nicht immer die theoretische Entropie, da sie nur auf Bitbasis arbeitet.

Beispiel (Quellcode): huffman.cpp
Download (Quellcode): huffman.zip

Beschreibung

Diese Art der Kodierung, errechnet mit Hilfe der Symbolauftrittswahrscheinlichkeiten (oder auch Häufigkeiten), einen möglichst kurzen und eindeutigen Code. Kommt ein Symbol häufiger vor, wird es durch einen kürzeren binären Code ausgedrückt. Werden nicht alle Symbole des Alphabets benötigt, fließen diese nicht weiter in die Bearbeitung ein. Grundsätzlich kann unterschieden werden zwischen statischer, dynamischer und adaptiver Huffman-Kodierung. Die statische hat festgelegte Symbolhäufigkeiten, die…