5. Komprimierung von Daten (3)

Das RLE-Verfahren setzt voraus, dass oft längere Folgen gleicher Bytes auftreten. Bei Texten ist das z.B. selten der Fall. Eine weitere Möglichkeit ist, die unterschiedliche Häufigkeit mit der Zeichen bzw. deren kodierte Bytes auftreten, auszunutzen.
Wechseln die Bytes häufig, so untersucht man die Häufigkeit, mit der gleiche Bytes in der Gesamtdatei auftreten. Häufig auftretende Bytes werden mit kurzen Codes - ab 1 Bit - kodiert. Für selten auftretende Bytes können längere Bitfolgen zur Kodierung gewählt werden. Dieses Verfahren eignet sich daher zur Komprimierung von normalen Texten.

Wir betrachten z.B. die Buchstabenverteilung in einem deutschen Text:

Bekanntermaßen tritt e als häufigster Buchstabe auf, gefolgt von n und r. Wählt man also für e den Code 1, so kann der Code von n nicht mehr mit 1 beginnen, da der Code allein aus 1 bestehend bereits das e identifiziert. Die Codes sind ja unterschiedlich lang und müssen eindeutig sein, da sie auch über keine Abschlussmarkierung verfügen. Ihr Code-Anfang (Prefix) muss daher so beschaffen sein, dass dieser zu keinem anderen Zeichen passt. Für n müssen wir also als Prefix 0 wählen. Da noch weitere Zeichen zu kodieren sind, ist ein zweistelliger Code nötig, also z.B. 01. Nun darf für das nächste Zeichen 01 nicht mehr als Prefix gewählt werden. Wir müssen daher 00 wählen. Da weitere Zeichen zu kodieren sind, muss eine weitere Stelle zugefügt werden: r erhält somit 001 als Code. Fährt man in dieser Weise fort, ergibt sich für i der Code 0001, für s 00001, für t 000001 usw. Die Länge der Codes wächst daher rasch an.

Die Darstellung als Baum zeigt eine starke Einseitigkeit:

Wir fordern, dass der Baum mehr ausgeglichen sein soll. Daher müssen als kurze Codes bereits mehrere Bits verwendet. Die Bitfolgen für ein Zeichen müssen im Prefix zu anderen Zeichen unterscheidbar sein. Das Ziel ist schließlich, dass eine geringst mögliche durchschnittliche Codelänge pro Zeichen entsteht.

Die durchschnittliche Codelänge bestimmt sich wie folgt:

Ein optimaler Code muss also optimal minimieren.

Der Huffman-Algorithmus erzeugt einen Code, der optimal ist, da die Symbole sortiert sind mit p₁ ≥ p₂ ≥ p₃ ≥ ... ≥ p_n und für ihre Codelängen gefordert wird l₁ ≤ l₂ ≤ l₃ ≤ ... ≤ l_n.

Beispiel

Wir betrachten folgende Wahrscheinlichkeitsverteilung für 8 Zeichen:

Die Zeichen werden nach fallender Wahrscheinlichkeit sortiert:

Die n Zeichen fassen wir als Blätter eines Baumes auf. Dieser ist zunächst ausgeglichen:

Huffman-Algorithmus:

Wiederhole solange mehr als ein Knoten/Blatt
in der obersten Ebene vorhanden ist
{
   Fasse in der obersten Ebene die beiden Blätter/Knoten
   mit der geringsten Wahrscheinlichkeit zu einem
   Teilbaum mit gemeinsamer Wurzel zusammen.

   Ersetze die zusammengefassten Elemente durch die
   Wurzel des neuen Teilbaumes.
}

Mit jedem Schritt verringert sich die Zahl der Äste, bis nur noch ein Ast vorhanden ist, der weggelassen werden kann, wodurch der entsprechende Knoten zur Wurzel wird.

Zunächst werden also die Blätter d und c mit den Wahrscheinlichkeiten 0,05 und 0,01 zusammengefasst:

In den Knoten tragen wir die Summe der Wahrscheinlichkeiten ein.

Die entsprechenden Blätter werden nun ersetzt:

Das Verfahren wird fortgesetzt, indem nun das Blatt b und der Knoten mit den nun kleinsten Wahrscheinlichkeiten 0,08 und 0,06 zusammengefasst werden zu einem Teilbaum:

Auch hier tragen wir die Summe der Wahrscheinlichkeiten in den Knoten ein.

Wieder werden die entsprechenden Elemente im Baum durch den Teilbaum ersetzt:

Die Neusortierung nach fallenden Wahrscheinlichkeiten führt zu:

Setzt man das Verfahren in derselben Weise fort, so ergibt sich schließlich folgender Baum:

Man hat nun einen Binärbaum erhalten, der nur noch kodiert werden muss. Um zu einem Zeichen zu gelangen, muss man den Baum durchlaufen mit entsprechenden Links- und Rechtsabzweigungen. Jedem Zeichen wird hierbei ein eindeutiger und doch unterschiedlich langer Code zugeordnet.
Z.B. kann "links" mit 1 und "rechts" mit 0 kodiert werden:

Um a zu erreichen muss man den Baum an den Ästen 0, 1, 1 durchlaufen. Der Code für a ist also 001.

Insgesamt ergibt sich folgende Code-Tabelle:
 

 
Für die durchschnittliche Codelänge ergibt sich:
 

 
Zum Vergleich nochmals das Shannonsche Informationsmaß:
 

In einer Datei muss die Code-Tabelle mit eingetragen werden. Hierdurch verlängert sich die Datei entsprechend. Für kurze Texte ist daher das Verfahren ungeeignet.

1. Kodiere folgenden "Text": abghddefhcbbaadabcbc.
2. Dekodiere folgenden Dateiinhalt: 010000100101010010000111000101.011111001111000010000100100111

Weitere Information:

ETH Zürich   Applet zum Testen des Huffman-Algorithmus

1. Einführung   2. RLE-Verfahren   4. LZW-Verfahren  

[Index]

Autor:Jürgen Dehmer
Letzte Änderung: 11.10.2004