mbraetz - Kryptographiespielplatz 2.2 FAV MAIL 
  Huffman - Grundlegender Algorithmus hinter ZIP, MPEG, JPEG 092836ff766768cce036e88a62792ca3





Bei der Huffman-Kodierung handelt es sich um eine Entropiekodierung, ähnlich der von Shannon und Fano entwickelten (Bell Labs 1960 am MIT). Der Algorithmus wurde 1952 von David A. Huffman entwickelt. Anders als bei der anderen Technik wird bei der Huffman-Kodierung kein Wurzelbaum aufgebaut, jedenfalls nicht von der Wurzel ausgehend.

Doch wie geht man vor? Es gibt sicherlich verschiedene Ansätze, hier wird der Ansatz beschrieben, der auch implementiert wurde.

Zunächst werde die Häufigkeiten ermittelt und die zwei Blätter mit den kleinsten Häufigkeiten je in einen neuen Baum zusammengefasst. Das setzt man mit allen Blättern und Teilbäumen fort bis man einen Gesamtbaum hat.

Der folgende Baum ist durch Kodierung des Wortes ERDBEERE entstanden:





Der entstandene baum ist ein Binärbaum. Alle linken und rechten Kanten/Unterbäume werden je nach Seite gleich kodiert mit 0 oder 1. Nun wird, von der Wurzel ausgehend, der Pfad zu den einzelnen Buchstaben nachgezeichnet.

Dabei ergibt sich folgende Code-Tabelle:



ZeichenKodierung
e0
r10
d110
b111


Das Wort ergab voher, mit der ASCII-Tabelle kodiert:



01100101 01110010 01100100 01100010
01100101 01100101 01110010 01100101


mit der neuen Kodierung dagegen erhält man einen kürzeren Text:



0 10 110 111 0 0 10 0


Die Anwendung des Verfahren ist immer dann sinnvoll, wenn ein möglichst einfacher Algorithmus mit hohen Anforderungen an die Ausführungsgeschwindigkeit und geringem Programmierungsaufwand im Vordergrund steht. Ein Beispiel für die Anwendung ist das im ZIP-Format spezifizierte Kompressionsverfahren IMPLODE.


Signatur: Marcel Brätz 20150607 1.2

I: Release v1.0 20060601: erste Version
I: Update v1.1 20120629: Kosmetische Korrekturen
I: Update v1.2 20150607: Korrektur in der grafischen Darstellung, Dank an Jörg Uhlig




  © 2000-2015 - mbraetz-webprojects 0.11 sec, 560.5 kB, 667.5 kB (limit: 120 sec)