2.5 Adaptive Huffman-Komprimierung

Die relative Ordnung der Symbolgewichte bestimmt die Baumstruktur. Beim Lesen eines Zeichens wird der Zähler im Blatt erhöht, und die Gewichte der Vorfahren werden modifiziert. Ändert sich die relative Ordnung, so wird der Verursacher (mit Gewicht w + 1 ) mit dem ``letzten'' Knoten mit Gewicht w getauscht (incl. Teilbäume).

Z.B. 7 weitere c würden ergeben:

Ein weiteres c würde zu einem Tausch mit dem Vater von f und b führen:

Die neue Code-Tabelle

Symbol Code

a 110

b 10111

c 1110

d 100

e 0

f 10110

g 1010

h 1111

Der Baum wird nicht übertragen, sondern von Sender und Empfänger initialisiert und dynamisch verändert.

Komprimieren:

initialisiere_baum;
repeat
   x := get_char();
   y = codiere(x);
   aktualisiere_baum(x)
   put_bits(y)
until x = EOF

Dekomprimieren:

initialisiere_baum;
repeat
   y := get_bits();
   x = decodiere(y);
   aktualisiere_baum(x);
   put_char(x)
until x = EOF

1. Möglichkeit zur Initialisierung:
Initialisiere Baum mit Zähler = 0 für jedes mögliche Zeichen.
Nachteil: alle Codes haben zunächst Länge 8, schrumpfen nur langsam.
2. Möglichkeit zur Initialisierung:
Beginne mit leerem Baum, trage nur Symbole ein, die vorkommen. Problem: beim ersten Auftreten kann Symbol nicht codiert werden, da es noch nicht im Baum ist.
Lösung: Bei neuem Zeichen sende Escape-Code + ASCII-Darstellung des Zeichens. Zur Initialisierung des Baumes tragen Sender und Empfänger zwei Zeichen ein:

Nach Einlesen von abcdefghijklmno: a 1 0001

b 1 0010

c 1 0011

d 1 0100

e 1 0101

f 1 0110

g 1 0111

h 1 1000

i 1 1001

j 1 1010

k 1 1011

l 1 1100

m 1 1101

n 1 1110

o 1 1111

Nach Einlesen von eeeeeeee: e 9 0

o 1 1000

a 1 10011

b 1 10100

c 1 10101

d 1 10110

f 1 10111

g 1 11000

h 1 11001

i 1 11010

j 1 11011

k 1 11100

l 1 11101

m 1 11110

n 1 11111

Nach Einlesen von 12 mal abcdfghijklmno: o 13 000

e 9 00101

a 13 0011

b 13 0100

c 13 0101

d 13 0110

f 13 0111

g 13 1000

h 13 1001

i 13 1010

j 13 1011

k 13 1100

l 13 1101

m 13 1110

n 13 1111