Huffman
So, nun wird's etwas komplizierter. Voraussetzung für Huffman: man muss einzelne Bits schreiben können, da die erzeugten Codes variable Bitlänge haben (siehe Modelle oben).
Huffman codiert die einzelnen Zeichen anhand einer Baumstruktur. In dieser Baumstruktur sind die zu kodierenden Zeichen in den Blättern, der Weg zum Blatt gibt den Code an, wobei der Baum ein Binärbaum ist, d.h. jeder Knoten hat maximal 2 Söhne. Der Code wird gebildet indem jedem linken Sohn das Bit 1 und jedem rechten Sohn das Bit 0 zugeordnet wird.
Beispiel:
/\
/\ a
b c
In diesem recht einfachen Beispiel werde
a=0
b=11
c=10
codiert.
Die Decodierung erfolgt genauso einfach. Man liest die Datei Bitweise und startet einfach von der Wurzel aus - 0 heisst rechter Sohn, 1 heisst linker Sohn. Wenn man im Blatt ankommt, so schreibt man das Zeichen im Blatt und fängt wieder bei der Wurzel an.
Wie kommt man zum Baum?
Zuerst liest man die Datei komplett und zählt wie oft jeder Bytewert vorkommt. Diese Tabelle (bytewert, Häufigkeit) wird nach Häufigkeit sortiert.
Nun werden die beiden Werte mit der geringsten Häufigkeit zu einem Knoten zusammengefasst, die ursprünglichen werte gelöscht und der neue Knoten in der Tabelle einsortiert. Die Häufigkeit des Knotens ist die Summe der Häufigkeiten der Söhne.
Dies macht man solange bis nur noch 1 Knoten in der Liste steht, dies ist die Wurzel.
Beispiel: aabacabc
a=4, b=2, c=2
a=4 a=4 (a(bc))=8
b=2 (bc)=4
c=2
gibt den Baum:
/\
a /\
b c
gibt die codes: a=1 b=01 c=00
der String aabacabc wird nun als 11010010100 codiert
Orginalstring: 8*8 bit (ASCII) = 64bit
Orginalstring mit 2bit pro Zeichen: 8*2bit= 16bit
Huffman: 11 bit
Noch fragen?