Dieses Datenkompressionsverfahren spart beträchtlich Platz bei Textdateien.
Nehmen wir an wir wollen eine Zeichenfolge "ABRACADABRA" kodieren, und dieses mit dem herkömmlichen Verfahren des binären-Codes, bei einer Binärdarstellung mit Hilfe von 5 Bits zur
Darstellung eines Buchstabens.
Dann lautet die Bitfolge so:
0000100010100100000100011000010010000001000101001000001
Um diese zu dekodieren, nimmt man sich 5 Bits her und wandelt sie nach dem Binärcode um.
Nun ist dieses ziemlich unpraktisch, denn der Buchstabe D kommt nur einmal vor und der Buchstabe A jedoch 5 mal und man muß A jedesmal, die selbe Bitfolge, aufschreiben und wieder dekodieren.
Es wäre doch besser, wenn man versuchen würde, häufig verwendete Buchstaben eine kürzere Bitfolge zuzuweisen, indem man sagt A wird mit 0 kodiert, B mit 1, R mit 01, C mit 10 und D
mit 11, so daß dann aus ABRACADABRA dann diese
0 1 01 0 10 0 11 0 1 01 0
Bitfolge dann werden würde. Diese ist schon wesentlich kürzer denn diese Bitfolge benutzt nur mehr 15 Bits anstatt 55 Bits, so wie die vorhergehende. Dieser Code hat jedoch einen Haken, denn es ist kein wirklicher Code, da er abhängig ist von den Leerzeichen, ohne diese Leerzeichen würde nämlich
010101001101010 als
RRRARBRRA heraus kommen.
Also muß man die Zahl mit Begrenzern dekodieren, aber dann noch ist die Zahl von 15 Bits plus
10 Begrenzern noch immer kleiner als der Standard-Code.
Wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt werden keine Begrenzer benötigt. Deswegen werden wir die zu kodierenden Buchstaben anders wählen, nämlich:
A mit 11, B mit 00, C mit 010,D mit 10 und R mit 011
so gäbe es nur eine Möglichkeit, die 25 Bits Zeichenfolge
1100011110101110110001111
zu dekodieren.
Eine noch einfachere Methode zur Darstellung eines Codes ist ein Trie.
Dazu ein Bsp.: Wir wollen wieder ABRACADABRA kodieren, aber dieses mal mit dem Trie.
Dazu sollte man wissen, daß man bei einem Trie immer von der "Wurzel"
ausgeht und so sein Zeichen bestimmt. Wenn man bei einem Knoten angelangt
ist, muß man sich entscheiden ob nach links oder rechts.
Für links muß man mit 0 codieren und für rechts mit 1.
Nun, man sieht hier, daß der rechte Code um 2 Bits kürzer ist als der linke.
Die Trie-Darstellung garantiert also, daß kein Code für ein Zeichen mit dem Anfang eines anderen Zeichen übereinstimmt, so daß sich die Decodierung für die Zeichenfolge eindeutig
festlegen läßt.
Doch welchen Trie soll man Benutzen? Hier gibt es eine Lösung bei der man bei gegebener Zeichenfolge einen Trie berechnen kann und der eine minimale Bitfolge hat.
Dieses Verfahren wird Huffman Kodierung genannt.
|
