Vorlesung: Codierung und Kryptographie
  Huffman-Codierung interaktiv
 

Vorbemerkungen | Codierung | Eigenschaften | Experimentiersystem | Anwendungsbeispiel | VortragMathematica-ProgrammLiteratur

   
   
 

Kompressionsverfahren wie MP3, JPEG, MPEG-Video, Zip, usw. erfreuen sich großer Beliebtheit. Beinahe ohne merkliche Einbußen machen sie es möglich, große Dateien wie Musik, Bilder und Videos platzsparend zu speichern oder schnell im Internet zu übertragen.

David Huffman (1925-1999) entwickelte im Jahre 1952 ein heute noch sehr beliebtes Verfahren zur verlustlosen Kompression von Daten. Verlustlos bedeutet, dass die Ursprungsdaten nach der Kompression orginalgetreu wiederhergestellt werden können. Das Verfahren findet meist Anwendung als (verlustloser) Teilschritt in verlustbehafteten Verfahren wie MP3 oder JPEG.

Die Idee des Verfahren beruht auf einem einfachen Prinzip: Statt jedem Wort einen gleichlangen Code zuzuordnen (beispielweise 8 Bit im Falle von ASCII), bekommen Zeichen, die häufig im Text vorkommen einen kürzeren Code als seltene Zeichen. Der Huffman-Algorithmus generiert einen solchen - sogar bezüglich der Codewortlänge optimalen - Code.

Als Hilfsmittel verwendet das Huffman-Verfahren Codebäume, mit denen sich Codewörter grafisch als Baum darstellen lassen. Den Code eines Zeichens liest man aus dem Codebaum ab, indem man von oben - der so genannten Wurzel - ausgehend im Baum bis zum gesuchten Zeichen am Ende des Baumes wandert und die dabei gefundenen Beschriftungen an den Verzweigungen notiert.

zugehöriger Code:

A = 00
B = 01
C = 1


--> Der Huffman-Algorithmus - ein Beispiel