Entropiekodierung
Die Entropiekodierung ist eine
verlustfreie Datenkompression, die jedem Zeichen eines Textes ein
neues Symbol optimierter Länge zuordnet.
Häufige Zeichen erhalten ein kurzes Symbol, seltene ein langes.
Die Entropie-Optimierung bestimmt die Anzahl der Bits n, aus denen ein Symbol zusammen gesetzt sein soll, wenn es ein Zeichen ersetzt, dass mit einer Wahrscheinlichkeit (Häufigkeit) von p im Text auftritt:
n = - log2(-p) Bit/Symbol
Nach Shannon und Fano lautet der Berechnungsalgorithmus:
- Zähle Häufigkeiten der Zeichen.
- Ordne die Zeichen nach ihrer Häufigkeit.
- (*) Teile die Menge so, daß Summe der Häufigkeiten der Teilmengen möglichst gleich ist.
- (*) Nenne die Mengen 0 und 1 bzw. erweitere ihre Namen entsprechend.
- (*) Wiederhole mit den Teilmengen die Schritte (*) , bis sie nur noch ein Element enthalten.
Die neuen Symbolnamen lassen sich auch in einer Baumstruktur darstellen (leider sind die Zeichenmöglichkeiten des Autors begrenzt...).
Die Entropiekodierung liefert die kleinstmögliche Zeichenfolge zur Darstellung eines Textes, aber nicht notwendigerweise die beste Komprimierung.
Andere Verfahren betrachten Zeichenketten statt Einzelzeichen und erreichen u.U. deutlich höhere Kompressionsraten. Das Lempel-Ziv-Welch- Verfahren wandelt zum Beispiel die entropiekomprimierte Zeichenkette ABABABABABABABABABAB um in einen Ausdruck der Art 10*AB.
Beispiel
Die Sequenz ABBCAADA soll entropiekodiert werden. Um den Vergleich mit
dem Ergebnis zu erleichern, nehmen wir folgende Binärschreibweise für die
Zeichen A,B,C,D an: 00,01,10,11.
Für ABBCAADA schreiben wir alternativ: 00,01,01,10,00,00,11,00.
Algorithmus für die Entropiekodierung der Zeichenfolge ABBCAADA:
- Die Buchstabenhäufigkeiten p sind:
A - 50%, B - 25%, C - 12,5%, D - 12.5% - Die Werte sind bereits geordnet.
- Teilen der Menge A,B,C,D in A und B,C,D.
Sie heißen: A: 0; B,C,D: 1. - Teilmenge 0 besteht nur aus einem Zeichen, fertig: A -> 0.
- Teilen der Menge B,C,D in B und C,D.
Sie heißen: B: 10. C,D: 11. - Teilmenge 10 besteht nur aus einem Zeichen, fertig: B -> 10.
- Teilen der Menge C,D in C und D
Sie heißen: C: 110 und D: 111. - Alle Teilmengen bestehen nur noch aus einem Zeichen, fertig!
Ergebnis:
A -> 0 p=0.5 n= - log2(1/2) Bit/Symbol = 1 Bit/Symbol B -> 10 p=0.25 n= 2 Bit/Symbol C -> 110 p=0.125 n= 3 Bit/Symbol D -> 111
Aus ABBCAADA wird: 0,10,10,110,0,0,111,0. Verglichen mit der Alternativ-Schreibweise oben sparen wir 2 Stellen. Zeichentrenner sind nicht erforderlich, da der Bitstrom als sog. Präfixcode vorliegt. Gültige Zeichen treten nicht als Präfix anderer Zeichen auf.
Beispiel: Das Zeichen für A, 0, tritt in keinem anderen Symbol als Präfix auf. Der Ausdruck 11 ist Präfix in C und D, ist aber nicht als eigenes Zeichen definiert.
Betrachtung der Entropie
* Entropie von ABBCAADA: 1.75 Bit/Zeichen * Maximalentropie von 4 Zeichen (A,B,C,D): 2 Bit/Zeichen * Die relative Entropie beträgt: 1.75/2 = 0.88 * Entropie von 01010110001110: 1 Bit/Zeichen * Maximalentropie von 2 Zeichen (1,0): 1 Bit/Zeichen * Die relative Entropie beträgt: 1/1 = 1 (der Maximalwert!)
Die Ausgangszeichenfolge stellt 2 Bit/Zeichen zur Verfügung, nutzt aber nur 1.75 Bit/Zeichen. Die neue Zeichenfolge stellt 1 Bit/Zeichen zur Verfügung. Die Zeichen 0 und 1 treten gleichhäufig auf und erreichen die Maximalentropie.
Anwendungen der Entropiekodierung: