Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


Huffman-Kodierung

Beispiel

Eigenschaften

Varianten

dynamische Kodierung

adaptive Kodierung


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Eigenschaften des Huffman-Kodes


Aus den Betrachtungen für allgemeine Kodebäume heraus ergeben sich alle wesentlichen Eigenschaften in punkto Interpretierbarkeit (Präfixkode).


Darüber hinaus erlaubt der Huffman-Algorithmus eine "Bit-genaue" Abbildung der theoretisch erzielbaren Kodeeffizienz. Die maximale Abweichung der Kodelänge von Huffman-Kodes vom idealen Wert ist kleiner als 1 Bit.


Beispiel:


Zeichen  P(x)    I(x)  Kode-   H(x)
                       länge
  A     0,387   1,369   1     0,530
  B     0,194   2,369   3     0,459
  C     0,161   2,632   3     0,425
  D     0,129   2,954   3     0,381
  E     0,129   2,954   3     0,381
--------------------------------------
 theoretischer Minimalwert:   2,176 Bit/Z.
    Kodelänge nach Huffman:   2,226 Bit/Z.

Aus der Berechnung der Entropie dieser Daten ergibt sich bei der zugrunde gelegten Verteilung ein idealer Wert von 2,176 Bit pro Zeichen für die Enkodierung. Ein Huffman-Kode erreicht demgegenüber einen realen Wert von 2,226 Bit pro Zeichen. Damit nähert sich die Huffman-Kodierung dem Ideal auf 97,74% an.


Eine noch bessere Abbildung läßt sich nur mit Hilfe der arithmetischen Kodierung erreichen, für die allerdings patentrechtliche Einschränkungen gelten.


 <   ^   > 

 Kodebäume 
 arithmetische Kodierung 

Huffman-Kodierung Beispiel Varianten



Anzeigen:

Informations- und Kodierungstheorie