Beim Huffman-Code werden die einzelnen Zeichen so kodiert, dass die Zeichen, die am seltensten vorkommen, möglichst durch lange Codewörter dargestellt werden. Andererseits werden häufige Zeichen durch möglichst kurze Codewörter dargestellt.
Dazu müssen zuerst alle Zeichen ausgezählt werden. Aus dieser Häufigkeitsverteilung wird dann ein Baum erstellt. Die vorgehensweise hier ist, dass man mit einem Wald aus verschiedenen Bäumen beginnt. Diese Bäume sind ganz zu Beginn noch die einzelnen Zeichen. Aus dieser Menge an Bäumen werden die zwei Bäume herausgenommen, die den zwei seltensten Zeichen entsprechen. Es wird ein neuer Knoten bzw. Baum erstellt, wobei die zwei herausgenommenen Bäume die Kinder des neuen Knotens sind. Dieser neue Knoten hat als Häufigkeit die Summe der Häufigkeiten der beiden Kinder. Der Knoten wird dann dem Wald hinzugefügt. Jetzt werden wieder die zwei Bäume mit den zwei seltensten Häufigkeiten herausgenommen usw. Bei jedem Schritt verschwindet ein Baum aus dem Wald. Wenn nur noch ein Baum im Wald vorhanden ist, ist der Huffman-Baum fertig gestellt. Dieser letzte Baum im Wald ist dann die Wurzel des Huffman-Baumes. Die einzelnen Zeichen sind die Blätter. Der Huffman-Baum wird also von den Blättern zur Wurzel hin aufgebaut.
Der Huffman-Baum eignet sich aber nur zum Dekomprimieren; dabei kann der Baum von der Wurzel aus durchlaufen werden bis man zu einem Blatt kommt. Das ist dann das Kennzeichen, dass das gegebene Codewort zu Ende ist.
Ein Codewort sieht z.B. so aus: "01101". Man beginnt an der Wurzel. Bei "0" geht man zum linken Kind, bei "1" zum rechten Kind. Das wiederholt man solange, bis man an einem Blatt angekommen ist, d.h. bis zu einem Knoten, der keine Kinder hat.
Zum Komprimieren eignet sich aber eine Codetabelle besser. In der Codetabelle steht explizit für jedes Zeichen das zugehörige Codewort. Die Codetabelle kann aber aus dem Baum erstellt werden, in dem man den Baum von den Blättern aus durchläuft bis man an der Wurzel angekommen ist.
Eine so komprimierte Datei lässt sich nur wieder dekomprimieren, wenn der zum Komprimieren verwendete Huffman-Baum bekannt ist. Dazu wird die Codetabelle an den Anfang der komprimierten Datei gestellt. Beim Dekomprimieren muss aus dieser Codetabelle dann der Huffman-Baum wieder erstellt werden.
Diese Klasse steuert das ganze Programm. Zuerst werden die Kommandozeilen-Parameter interpretiert. Dabei kann angegeben werden, ob komprimiert oder dekomprimiert werden soll. Wird eine Datei angegeben und soll komprimiert werden, dann wird für die Ausgabedatei der ursprüngliche Dateiname mit der zusätzlichen Endung ".huffman" verwendet. Beim Dekomprimieren werden nur Eingabedateien akzeptiert, die schon die Endung ".huffman" haben; die Endung wird dann entfernt.
Dann wird die Datei geöffnet (sofern eine angegeben wurde) und der Inhalt der Datei wird in ein StringBuffer eingelesen. Ansonsten wird als InputStream "System.in" verwendet. Dadurch, dass zum Einlesen aus dem InputStream die Methode read() verwendet wird, wandelt Java die Zeichen intern nicht um (z.B. ASCII zu Unicode).
Während die Datei Byte für Byte eingelesen wird, werden auch gleich die Häufigkeiten ausgezählt. Dabei wird die Methode addData(int c) der Klasse HuffmanTree verwendet. Zusätzlich wird das Zeichen natürlich dem StringBuffer hinzugefügt (über append(char c)).
Wenn komprimiert werden soll, wird anschließend die Methode buildTree() der Klasse HuffmanTree aufgerufen. Dabei wird dann der Huffman-Baum nach den ausgezählten Häufigkeiten erstellt. Es ist also wichtig, dass zuvor mit addData(int c) die Zeichenhäufigkeit festgelegt wurde. Dann wird die Codetabelle mit createRawCodetable() (Klasse HuffmanTree) erstellt und über write(int b) (Klasse OutputStream) ausgebenen. Dadurch, dass die Methode write(int b) verwendet wird, wandelt Java bei der Ausgabe die Zeichen nicht in den Zeichsatz des Betriebssystems um (z.B. von Unicode nach ASCII). Anschließend wird encode(StringBuffer data) der Klasse HuffmanTree aufgerufen. Diese Methode gibt wieder einen StringBuffer zurück, wobei die einzelnen Zeichen wieder mit der write()-Methode ausgegeben werden. Zusätzlich wird am Ende noch der Kompressionsgrad ausgerechnet und ausgegeben.
Sollen Daten dekomprimiert werden, wird zuerst die Methode readRawCodetable() der Klasse HuffmanTree aufgerufen. Diese Methode gibt dann die Position im StringBuffer zurück, ab der die eigentlichen Daten beginnen. Mit decode(StringBuffer data, int startindex) werden die Daten dann dekodiert. Der erhaltene StringBuffer wird dann wieder Zeichen für Zeichen mit write(int b) ausgegeben.
In dieser Klasse wird der Huffman-Baum erstellt, gespeichert und verwendet. Gespeichert vom Baum wird letztendlich nur der Wurzel-Knoten (private Node root). Bevor ein Baum erstellt werden kann, muss zur Vorbereitung, wie oben schon erwähnt, die Methode addData(int c) verwendet werden, um die Häufigkeit der einzelnen Zeichen zu speichern. Dazu wird das Array "private long characters[]" verwendet, das 256 Elemente hat. Jedes Element entspricht dabei einem Zeichen. Da ein Zeichen ja ein Byte ist, sind 256 verschiedene Elemente nötig.
Nachdem in "characters[]" gespeichert wurde, wie oft jedes Zeichen vorkommt, kann die Methode "buildTree()" aufgerufen werden. Hier wird der Huffman-Baum, wie oben im Abschnitt "Huffman-Code" beschrieben, erstellt. Außerdem wird aus dem Baum die Codetabelle erzeugt. Dazu wird der zweite Vector "blaetter2" verwendet. Hier sind nämlich noch direkte Referenzen auf die einzelnen Blätter des Baumes; dann wird der Baum von den Blättern zur Wurzel zurückgegangen und dabei gespeichert, welches Codewort dazu gehört, indem festgestellt wird, ob sich der aktuelle Knoten links oder rechts vom übergeordneten Knoten befindet. Das Codewort wird dann im Array "private String codetable[]" als String-Objekt gespeichert. Das Array hat auch 256 Elemente.
Anschließend kann die Methode "encode(StringBuffer data)" aufgerufen werden, um die Daten zu komprimieren. Hier werden nacheinander alle Zeichen vom übergebenen StringBuffer in ihre Codewörter umgewandelt. Wenn jeweils 8 Bits zusammen sind, werden diese als ein Byte interpretiert und in den StringBuffer geschrieben, der die komprimierten Zeichen enthält. Dieser wird dann am Ende zurückgegeben.
Soll jedoch dekomprimiert werden, dann muss zuerst mittels "readRawCodetable()" die Codetabelle, die am Anfang der komprimierten Datei steht, eingelesen werden. Aus dieser Codetabelle wird dann wieder der Huffman-Baum erstellt, der dann in der Methode "decode()" verwendet wird. In dieser Methode werden die einzelnen Zeichen der Eingabedaten in Bitmuster umgewandelt. Anschließend wird mit diesen Bitmustern der Huffman-Baum durchlaufen. Wenn man an einem Blatt angekommen ist, dann ist das Codewort fertig und das Zeichen, das zu dem Knoten gehört, wird in den zurückzugebenden StringBuffer geschrieben.
Die Klasse Node stellt einen Knoten im Huffman-Baum dar. Ein Knoten kann einen Vorgänger besitzen (parent) und zwei Nachfolger (leftChild, rightChild). Besitzt ein Knoten keinen Vorgänger (parent == null), dann ist der Knoten die Wurzel des Baumes. Existieren keine Nachfolger, dann ist der Knoten ein Blatt. Bei Blättern wird das Zeichen, das sie repräsentieren, in der Eigenschaft "data" gespeichert. Die Eigenschaft "count" speichert wie oft der Knoten/das Zeichen vorkam. Dies wird in der Methode "buildTree()" beim Aufbauen des Huffman-Baums verwendet.
Diese Klasse dient dazu, einen Integerwert in eine Folge von 4 Bytes umzuwandeln und auch wieder zurück. Das entspricht im Prinzip der Funktionalität von java.io.DataOutputStream.writeInt(). Verwendet wird diese Klasse in den Methode "createRawCodetable()" und "readRawCodetable()".
Das Format einer komprimierten Datei ist wie folgt aufgebaut: In den ersten 4 Bytes steht die Größe der (unkomprimierten) Datei. Diese Angabe ist wichtig, da beim Dekomprimieren sonst ein Zeichen zuviel herauskommen kann (beim Komprimieren werden am Schluss noch bis zu 7 Füll-Bits hinzugefügt, damit ein vollständiges Byte entsteht). Nach der Dateigröße kommt die Codetabelle. Dabei werden nur die Zeichen aufgelistet, die auch im Baum vorkommen. Zuerst wird ein Integerwert gespeichert, der angibt, wieviele Bytes lang das Codewort ist. Dann kommt das Zeichen (1 Byte) und dann entsprechend viele Bytes lang das Codewort. Danach wieder holt sich das ganze. Beendet wird die Codetabelle, indem der Integerwert "0" verwendet wird (4 Null-Bytes). Danach kommen die Zeichen.
Die Codewörter in der Codetabelle sind noch auf spezielle Weise abgespeichert. Und zwar könnte ein Codewort beispielsweise "011100" lauten. Es ist 6 Bits lang. Würde man es einfach so als Zeichen schreiben, ginge die Information verloren, wie viele "0" am Anfang sind. Deshalb wird zuerst noch eine führende "1" hinzugefügt. Das Codewort in der Codetabelle in der Datei sieht dann so aus "1011100". Die 7 Bits können dann (mit einer zusätzlichen "0" am Anfang) als 1 Byte geschrieben werden. Beim Einlesen der Codetabelle muss die führende "1" dann natürlich wieder entsprechend entfernt werden.
Hier noch ein Hexdump einer komprimierten Datei:
00000000 00 00 1f 19 00 00 00 01 0a 29 00 00 00 01 20 07 |.........).... .| 00000010 00 00 00 02 21 05 bb 00 00 00 01 22 60 00 00 00 |....!.»...."`...| 00000020 02 25 2a fe 00 00 00 02 26 06 25 00 00 00 02 27 |.%*þ....&.%....'| [...] 00000220 2a fd 00 00 00 02 f6 15 7c 00 00 00 00 56 6d 4e |*ý....ö.|....VmN| 00000230 db b1 20 ec f3 2b b8 6a f1 5f 6e 37 95 f4 e2 bc |Û± ìó+?jñ_n7.ôâ?| 00000240 6f 37 9b a8 9d b5 3b 6e c1 15 b8 8b b0 5f a6 4b |o7.?.µ;nÁ.?.°_?K| [...]
Die unkomprimierte Datei ist also 0x00001f19 Bytes groß (7961 Bytes). Das erste Codewort ist ein Byte lang (0x00000001), es ist das Zeichen 0x0a (10, '\n') und das Codewort ist in diesem Byte gespeichert: 0x29. Binär ist das 00101001. Werden die führenden "0" und die führende "1" entfernt, erhält man für das Zeichen das Codewort "01001". Das Codewort des zweiten Zeichens ist auch ein Byte lang, das Zeichen selber ist 0x20, also das Leerzeichen (32, ' '). Das Codewort ist in 0x07 gespeichert, Binär: 00000111, Codewort also: 11.
Ab Position 0x229 in der Datei kommt der Integerwert "0" (0x00000000), der das Ende der Codetabelle kennzeichnet. Das folgende Zeichen ist dann schon das erste komprimierte: 0x56 ist Binär 01010110 (führende Nullen müssen jetzt beachtet werden!). Geht man dem Baum entlang so kommt man auf das Zeichen "/" (siehe auch die Codetabelle weiter hinten). Das nächste Zeichen ist 0x6d (01101101), was dem "*" entspricht. Dann kommt 0x4e (01001110). Dabei entsprechen die ersten 5 Bits (01001) einem Zeilenumbruch ('\n'), die restlichen drei Bits sind der Anfang für die nächsten Zeichen. Das nächste Zeichen hat ein sehr kurzes Codewort ("11"), das Leerzeichen. Es bleibt jetzt noch ein Bit übrig. Mit den Bits aus dem nächsten Byte kann auch das wieder dekomprimiert werden.
Textdateien werden meist sehr gut komprimiert, oft auf weniger als die Hälfte. Wird die komprimierte Datei nocheinmal mit dem Programm komprimiert, wird sie wieder größer. Das liegt daran, dass in der komprimierten Datei viel mehr verschiedene Zeichen auftauchen, wodurch die Codetabelle größer wird. Das gleiche gilt auch für andere Binärdateien (z.B. JPEG-Bilder). Um dieses Problem teilweise zu umgehen, müsste die Codetabelle effizienter in der komprimierten Datei abgespeichert werden. Wie das geht, steht beispielsweise im Wikipedia-Artikel zur Huffman-Kompression (http://de.wikipedia.org/wiki/Huffman).
Die maximale Dateigröße ist theoretisch durch den Wertebereich eines Integers begrenzt. Die Dateigröße wird ja als Integerwert in die komprimierte Datei geschrieben. Beim Dekomprimieren wird dieser Wert u.a. als Abbruchkriterium verwendet. D.h. die theoretische maximale Dateigröße ist ca. 2GB (2 Milliarden Bytes = 231 Bytes). Die Dateigröße wird jedoch schon vorher von dem der Java Virtual Machine zur Verfügung stehendem Speicher begrenzt.
Der Speicherverbrauch ist recht hoch, da die Daten, die komprimiert werden sollen, komplett im Speicher sein müssen. Dies ist notwendig, da für die Auswertung der Häufigkeitsverteilung zuerst alle Zeichen analysiert werden müssen. Ein möglicher Ausweg wäre, die zu komprimierenden Daten in Blöcke aufzuteilen und jeden Block für sich zu komprimieren.
> java -jar Huffman.jar
Syntax: java -jar Huffman.jar [-x|-y] {c|d} [filename]
-x = print codetable
-y = print tree
c = compress
d = decompress
if no filename ist given, then stdin to stdout is compressed/decompressed
Datei komprimieren:
> java -jar Huffman.jar c textdatei.txt "textdatei.txt" to "textdatei.txt.huffman" compressed... compression ratio: 38.0%Datei dekomprimieren und gleichzeitig Codetabelle ausgeben:
> java -jar Huffman.jar -x d textdatei.txt.huffman
10 [.]: 01001
32 [ ]: 11
33 [!]: 0110111011
34 ["]: 100000
37 [%]: 0101011111110
38 [&]: 1000100101
39 [']: 101000101
40 [(]: 011010
41 [)]: 011001
42 [*]: 01101101
43 [+]: 00101110
44 [,]: 00100011011
45 [-]: 011000111
46 [.]: 011100
47 [/]: 01010110
48 [0]: 011011110
49 [1]: 001000101
50 [2]: 01010111100
52 [4]: 0101011111111
53 [5]: 0110111010100
54 [6]: 0101011111010
56 [8]: 0101011111011
58 [:]: 101000100
59 [;]: 001001
60 [<]: 1000100100
61 [=]: 100111
62 [>]: 011011101000
63 [?]: 01010100101
64 [@]: 0101011111100
65 [A]: 10100011
66 [B]: 0110111111
67 [C]: 01100010
68 [D]: 0110111000
69 [E]: 00101111
70 [F]: 001000111
71 [G]: 0010001100
72 [H]: 0110111001
73 [I]: 01101100
74 [J]: 01010100100
75 [K]: 011011101001
77 [M]: 001000100
78 [N]: 01100001
79 [O]: 1000101
80 [P]: 010101000
82 [R]: 010101110
83 [S]: 100001
84 [T]: 01100000
85 [U]: 0110111010101
87 [W]: 011011101011
91 [[]: 01010111101
92 [\]: 100010011
93 []]: 00100011010
95 [_]: 100011
97 [a]: 10110
98 [b]: 01010101
99 [c]: 101001
100 [d]: 001010
101 [e]: 0011
102 [f]: 010111
103 [g]: 0010110
104 [h]: 100100
105 [i]: 0001
106 [j]: 0110111110
107 [k]: 01010100111
108 [l]: 10101
109 [m]: 010100
110 [n]: 0000
111 [o]: 10111
112 [p]: 010110
114 [r]: 01000
115 [s]: 011101
116 [t]: 01111
117 [u]: 100110
118 [v]: 011000110
119 [w]: 1010000
120 [x]: 10001000
121 [y]: 0010000
122 [z]: 010101001100
123 [{]: 1001010
124 [|]: 010101001101
125 [}]: 1001011
223 [ß]: 0101011111101
246 [ö]: 010101111100
zurück zum Anfang