Huffman
aus RHWiki, der freien Romhacking-Enzyklopädie
Bei der Huffman-Komprimierung nutzt man die Eigenschaft der Daten, dass unterschiedliche Bytes unterschiedlich häufig auftreten. Je nach Häufigkeit werden unterschiedlich lange Bitfolgen zur Codierung verwendet. Auf diese Weise wird in den meisten Fällen eine kürzere Codierung der Gesamtdaten möglich.
| Inhaltsverzeichnis |
Die Idee
Ein Byte kann in einer Datei sehr häufig auftreten, dann will man möglichst wenig Bits zur Codierung verwenden (also insbesondere weniger als die standardmäßigen 8 pro Byte).
Kommt dagegen ein Byte sehr selten oder gar nicht vor, so stört es nicht wenn dieses Byte mit einer sehr langen Bitfolge codiert wird. Für Bytes die gar nicht auftreten muss überhaupt keine Bitfolge reserviert sein.
Beispiel: Die Daten "xxxxyxxxxyxxxxyz" sollen codiert werden. x kommt sehr häufig vor, es soll die kürzeste Codierung bekommen. y und z sollen eine längere Codierung bekommen. Andere Zeichen treten nicht auf und brauchen daher auch keine Bitfolge. Daher setzt man nun (willkürlich): x = 0 (Bit) y = 10 z = 11 und codiert damit die Daten so: x x x x y x x x x y x x x x y z (Original) 0 0 0 0 10 0 0 0 0 10 0 0 0 0 10 11 (Komprimiert, Binärdarstellung) Das sind 16 Bits, also 2 Byte, was wesentlich kürzer ist als die Länge der Originaldaten (16 Byte). Hier hat die Huffman-Komprimierung eine Verringerung der Datenlänge um 87,5 % bewirkt.
Allerdings ist man damit noch nicht ganz fertig. Damit die Daten wieder korrekt dekomprimiert werden können muss man noch die Codierungstabelle mit anhängen.
In obigem Beispiel: [Anzahl=3] [x]=[0] [y]=[10] [z]=[11]
Weiter unten werden noch effizientere Möglichkeiten zur Speicherung der Tabelle vorgestellt.
Hier sei nur angemerkt dass dadurch sehr kleine Datenmengen evtl. nicht mehr effizient komprimiert werden können, d.h. es kann passieren dass die komprimierten Daten inklusive Tabelle länger sind als die Originaldaten.
Dieses Problem kann durch spezielle Verfahren wie z.B. Adaptive Huffman umgangen werden.
Dazu unten mehr.
Aufgabe der Komprimierung
Ziel ist es nun eine optimale Codierung der Bytes zu finden. Einfach zu sagen, dass häufig auftretende Bytes eine kurze Bitfolge bekommen und seltene Bytes eine lange Bitfolge, ist unzureichend und keinesfalls eindeutig.
Die Bitfolgen müssen eindeutig sein, und - damit die Codierung optimal ist - sollten keine 'Löcher' vorhanden sein.
Beispiel: Daten: "aaaaaaab" 0 = a 11 = b Was ist mit 10 ? -> Hier könnte man optimaler codieren indem man "b = 1" setzt. Dass b dabei weniger häufig als a vorkommt spielt hier keine Rolle.
Der Huffman-Algorithmus
Der Huffman-Algorithmus löst oben genannte Aufgabe ziemlich effizient.
Durch den Algorithmus wird ein Binärbaum, ein sogenannter Huffman-Baum erstellt.
Das funktioniert folgendermaßen:
Huffman-Baum erstellen
1. Erstelle eine Liste aller Zeichen einer Datei und notiere zu jedem Zeichen wie oft es auftritt. Im folgenden nennen wir jeden Eintrag dieser Liste "Knoten".
Knoten: [Blatt=ja][Häufigkeit][Zeichen] (Die Angabe Blatt bezieht sich auf die Baumstruktur. In der durch Schritt 1 erstellten Liste sind alle Knoten Blätter.)
2. Wähle die beiden Knoten mit der geringsten Häufigkeit, erstelle einen neuen Knoten, der die beiden Knoten als Zweige hat. Etwa so:
Knoten: [Blatt=nein][Häufigkeit][Linker Zweig][Rechter Zweig]
Häufigkeit ist dabei die addierte Häufigkeit der beiden verwendeten Knoten. Die beiden Knoten werden als Zweige an den neuen Knoten angehängt und aus der Liste gelöscht. Als 'Ersatz' wird der neue Knoten der Liste hinzugefügt.
3.
Widerhole Schritt 2 bis nur noch ein Knoten in der Liste ist.
Dieser Knoten repräsentiert die Wurzel des Huffman-Baumes.
Erklärung des Baumes
Anhand des Baumes lässt sich nun jedes Zeichen eindeutig codieren:
Zunächst wird das zu codierende Zeichen im Baum gesucht. Dann wird der Weg bis zu dem Zeichen als Codierung des Zeichens verwendet, wobei man definieren kann:
- 0 = gehe nach links und
- 1 = gehe nach rechts
(sofern nicht vorgeschrieben steht es aber jedem frei das auch andersrum zu codieren.)
Beispiel:
Daten: "17872222"
1. Liste erstellen:
Liste: [B,1,"1"], [B,2,"7"], [B,1,"8"], [B,4,"2"]
Nummerierung: 1 2 3 4
2. Knoten mit geringster Häufigkeit: 1 und 3
Fasse zusammen zu:
[K,2,[B,1,"1"],
[B,1,"8"]] (Beachte die Schachtelung)
Damit ist die neue Liste:
[B,2,"7"], [B,4,"2"], [K,2,[B,1,"1"],[B,1,"8"]]
1 2 3
Jetzt haben die geringste Häufigkeit: 1 und 3
Fasse zusammen zu:
[K,4,[B,2,"7"],
[K,2,[B,1,"1"],
[B,1,"8"]]]
Fasse dies nun mit dem letzten in der Liste verbliebenen Knoten zusammen und erhalte:
[K,8,[B,4,"2"],
[K,4,[B,2,"7"],
[K,2,[B,1,"1"],
[B,1,"8"]]]
Dies kann man sich als Baum dann so vorstellen:
8
/ \
/ 4
4("2") / \
/ 2
2("7") / \
/ \
1("1") 1("8")
Daraus folgen die Codierungen der Zeichen:
"2" = 0 (links)
"7" = 10 (rechts, links)
"1" = 110 (rechts, rechts, links)
"8" = 111 (rechts, rechts, rechts)
Und der String ist somit komprimiert:
110 10 111 10 0 0 0 0 (Komprimiert)
1 7 8 7 2 2 2 2 (Original)
Oft wird das ganze mit Nullen zu ganzen Bytes aufgefüllt:
11010111 10000000
Das entspricht einer Verringerung der Größe von 8 auf 2 Bytes, also etwa um 75 %.
Dekomprimierung der Daten
Damit die Daten korrekt dekomprimiert werden können, braucht man:
- 1. Den Huffman-Baum der zur Codierung verwendet wurde
- 2. Die Komprimierten Daten
Sofern nicht im Baum eine Kombination als Endcode reserviert ist außerdem:
- 3. Die Länge der Komprimierten Daten
Die komprimierten Daten läuft man dann Bit für Bit ab. Je nach dem ob ein Bit 0 oder 1 ist wird im Huffman-Baum ein linker oder rechter Weg genommen (jeweils einen Schritt). Kommt man bei einem Blatt an, so wird das zugehörige Zeichen ausgegeben und wieder an der Wurzel mit dem nächsten Bit fortgefahren.
Beispiel:
Baum:
/\
_/ \_
/\ /\
/ \ D E
Ende /\
/ \
B C
Komprimierte Daten: 10110110 10101111 00110101
1(r) -> 0(l) -> D
1(r) -> 1(r) -> E
0(l) -> 1(r) -> 1(r) -> C
0(l) -> 1(r) -> 0(l) -> B
1(r) -> 0(l) -> D
1(r) -> 1(r) -> E
1(r) -> 1(r) -> E
0(l) -> 0(l) -> Fertig. (restliche Bits 110101 haben keine Bedeutung mehr)
Damit sind die dekomprimierten Daten: "DECBDEE"
Speicherung des Huffman-Baumes
Es gibt viele Möglichkeiten einen Huffman-Baum zu codieren und zu speichern. Eine ziemlich primitive ist, alle konstruierbaren Bitfolgen und das jeweils zugehörige Zeichen aufzulisten.
Für eine effektive Codierung siehe: Huffman auf dem GBA
Grenzen und Verbesserungen
Das Huffman-Verfahren ist nur effektiv, wenn Bytes in einer Datei unterschiedlich häufig verteilt sind. Bei sehr großen Dateien und/oder Binärdateien ist dies jedoch selten der Fall. Wahrscheinlicher ist hier eine annähernd gleichmäßige Verteilung.
Um solche Daten mit Huffman effektiv komprimieren zu können, kann ein Adaptiver Huffman-Algorithmus verwendet werden. Das würde gleichzeitig die Speicherung des Huffman-Baumes in der komprimierten Datei ersparen. Dazu im folgenden.
Wie oben bereits festgestellt kann eine komprimierte Datei durch das (notwendige) Anhängen der Codierungstabelle länger sein als das Original. Das ist insbesondere bei kurzen Datenmengen wahrscheinlich.
Weiß man um was für Daten es sich handelt, bietet sich evtl. die Verwendung eines statischen Huffman-Baumes an, der für alle Dateien gleich wäre. Man kann sich aber denken dass eine solche Codierung nicht immer optimal ist.
Eine andere Lösung des Problems bietet Adaptive Huffman. Dabei wird zu Anfang ebenfalls immer von demselben Baum ausgegangen, in der Regel ein normalverteilter bei dem jedes Byte gleiche Wahrscheinlichkeit hat. Während der Komprimierung erkennt der Komprimierer, dass bestimmte Bytes häufiger auftreten als andere und konstruiert dabei den Baum so um, dass fortan diese Bytes kürzer codiert werden können. Bei der Dekomprimierung wird der Baum auf dieselbe Weise umgestaltet, sodass Komprimierer und Dekomprimierer an jeder Stelle mit demselben Baum arbeiten.
Auf diese Weise können auch unterschiedliche Verteilungen der Häufigkeiten innerhalb derselben Datei berücksichtigt werden. Kommt ein Zeichen z.B. am Anfang sehr häufig vor, so bekommt es dort sehr kurze Bitfolgen. Kommt es dann später nur noch selten vor, sind die Bitfolgen später auch länger.
Ein weiteres Problem wurde oben deutlich:
Bestehen die Daten z.B. nur aus zwei unterschiedlichen Zeichen, so muss jedes mit einem Bit codiert werden. Effektiver wäre aber oft wenn z.B. eines der Zeichen nur mit einem halben Bit codiert würde. Eine solche Komoprimierung kann man mit Arithmetischer Codierung erreichen.
Bekannte Implementierungen
Eine reine Huffman-Komprimierung wird aufgrund oben genannter Schwierigkeiten nur noch selten verwendet. Allerdings ist die einfache Huffman-Komprimierung relativ schnell (auch im Vergleich zu den anderen), sodass sie u.a. noch auf einigen Konsolen Anwendung findet:
