Deutsch (DE-CH-AT)English (United Kingdom)
 
 
 
 
 
   


 

Huffman-Kodierung

 

Hintergrund

Der Huffman-Code wurde 1952 von David Albert Huffman (* 9. April 1925; † 7. Oktober 1999 in Santa Cruz, Kalifornien) entwickelt. Es handelt sich um einen Algorithmus, der einen Binärbaum erzeugt, wodurch eine verlustfreie Datenkompression erzielt wird.

 

Funktionsweise

Der zu kodierende Text sei „ERDBEERE“. Für jeden Buchstaben wird ein eigenes Blatt erstellt. Anschließend werden jeweils die Buchstaben, die am seltensten vorkommen, zu einem neuen Baum zusammengefasst, bis nur noch ein Baum übrig bleibt.1

huffman_tree2

Abb. 1: Binärbaum Huffman-Code1


Es ergibt sich die Code-Tabelle:

Zeichen Kodierung
E 0
R 10
B 110
D 111


Soll nun wieder, anhand des Binärbaumes, das Wort „erdbeere“ gebildet werden, so ergibt sich die Bitfolge: „0 10 111 110 0 0 10 0“. Die ursprüngliche ASCII-Kodierung war deutlich länger: „01100101 01110010 01100100 01100010 01100101 01100101 01110010 01100101“

 

Details

Bei dem Huffman-Code handelt es sich um eine so genannte Entropiekodierung.

 

Weblinks

FH-Flensburg

 

Einzelnachweise

1 Kryptographiespielplatz


   
     
 
 
Copyright © 1998 - 2017 PROJECT / Contributors