Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Datenformate


Huffman-Kodierung

Beispiel

Eigenschaften

Varianten

dynamische Kodierung

adaptive Kodierung


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Huffman-Kodierung


Der von David Huffman beschriebene Algorithmus ordnet allen Zeichen, die in den betrachteten Daten auftreten können, einen Endknoten in einem binären Baum zu. Als Attribut erhalten diese Knoten die Auftrittshäufigkeiten der ensprechenden Zeichen.


Die Baumstruktur entsteht durch das schrittweise Zusammenfassen dieser Knoten. Dazu werden die beiden Knoten mit der geringsten Auftrittshäufigkeit einem neuen Knoten untergeordnet, der die Summe der beiden Auftrittshäufigkeiten zugewiesen bekommt. Bereits zusammengefaßte Knoten werden im weiteren Verlauf nicht mehr beachtet, da sie bereits in den Baum eingebettet sind. Das Prozedere wird solange durchlaufen, bis alle Knoten in einer Wurzel zusammengeführt sind.


Kodebaum nach Huffman


Zur En- bzw. Dekodierung werden den Kanten des Huffman-Baums die binären Werte 0 bzw. 1 zugeordnet. Der "Weg" von der Wurzel des Huffman-Baums zu dem entsprechenden Endknoten ergibt den Huffman-Kode des Zeichens, dem der Endknoten zugeordnet ist.



 <   ^   > 

Datenkompression 11. Zeichen: 'a' Huffman-Kodierung: Beispiel



Anzeigen:

Informations- und Kodierungstheorie