Entropiekodierung

Die Entropiekodierung ist eine Methode zur verlustfreien Datenkompression, die einen aus einzelnen Zeichen bestehenden Text in eine Bitfolge umwandelt. Typische Vertreter sind die Huffman-Kodierung und die arithmetische Kodierung.

Im Gegensatz dazu stehen Stringersatzverfahren, die eine Folge von Zeichen des Originaltextes durch eine Folge von Zeichen eines anderen Alphabets ersetzen.

Da eine bestimmte Mindestanzahl von Bits notwendig ist, um alle Zeichen voneinander zu unterscheiden, kann die Anzahl der Bits, die den Zeichen zugeordnet werden, nicht unbegrenzt klein werden. Die optimale Anzahl von Bits, die einem Zeichen mit einer gegebenen Wahrscheinlichkeit zugeordnet werden sollte, wird durch die Entropie bestimmt.

Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern. Häufig sind dies Prädiktionsverfahren, Verfahren wie die Burrows-Wheeler-Transformation, aber oft auch andere Komprimierer. LHarc zum Beispiel verwendet einen LZ-Kodierer und gibt die von diesem Kodierer ausgegebenen Zeichen an einen Huffman-Kodierer weiter. Auch Deflate und Bzip besitzen als letzte Stufe einen Entropiekodierer.

Kodierung

Die Entropiekodierung bestimmt zunächst die Häufigkeit von Symbolen (Zeichen). Jedes Symbol wird durch ein bestimmtes Bitmuster dargestellt. Dabei sollen häufige Symbole durch kurze Bitmuster dargestellt werden, um die Gesamtzahl der benötigten Bits zu minimieren.

Mathematische Algorithmen zur Abschätzung der optimalen Länge des Codes eines jeden Symbols führen meist zu nicht ganzzahligen Ergebnissen. Bei der Anwendung müssen die Längen auf ganzzahlige Werte gerundet werden, wodurch man einen Teil der Verdichtung verliert.

Mit ganzen Bits

Die Shannon-Fano-Kodierung schlägt eine Möglichkeit vor, die die Anzahl der Bits auf ganze Zahlen rundet. Dieser Algorithmus liefert aber in bestimmten Fällen nicht die optimale Lösung. Deshalb wurde der Huffman-Code entwickelt, der beweisbar immer eine der optimalen Lösungen mit ganzen Bits liefert. Beide Algorithmen erzeugen einen präfixfreien Code variabler Länge, indem ein binärer Baum konstruiert wird. In diesem Baum stehen die „Blätter“ für die zu kodierenden Symbole und die inneren Knoten für die abzulegenden Bits.

Neben diesen Verfahren, die individuelle Tabellen speziell angepasst auf die zu kodierenden Daten erstellen, gibt es auch Varianten, die feste Codetabellen verwenden. Der Golomb-Code kann zum Beispiel bei Daten verwendet werden, bei denen die Häufigkeitsverteilung bestimmten Regeln unterliegt. Diese Codes haben Parameter, um ihn auf die exakten Parameter der Verteilung der Häufigkeiten anzupassen.

Verbesserung

Diese Verfahren treffen aber die von der Entropie vorgeschriebene Anzahl von Bits nur in Ausnahmefällen. Das führt zu einer nicht optimalen Kompression.

Ein Beispiel: Eine Zeichenkette mit nur 2 verschiedenen Symbolen soll komprimiert werden. Das eine Zeichen hat eine Wahrscheinlichkeit von ${\displaystyle \mathrm {p} (A)=0{,}75}$, das andere von ${\displaystyle \mathrm {p} (B)=0{,}25}$. Die Verfahren von Shannon und Huffman führen dazu, dass beide Zeichen mit je einem Bit abgespeichert werden. Das führt zu einer Ausgabe, die so viele Bits enthält wie die Eingabe an Zeichen.

Ein optimaler Entropie-Kodierer würde aber nur ${\displaystyle -\log _{2}(0{,}75)\approx 0{,}41}$ Bits für das Zeichen A verwenden und dafür ${\displaystyle -\log _{2}(0{,}25)=2}$ Bits für B. Das führt zu einer Ausgabe, die nur ${\displaystyle -0{,}75\cdot \log _{2}(0{,}75)-0{,}25\cdot \log _{2}(0{,}25)\approx 0{,}81}$ Bits pro Zeichen enthält (maximale Entropie), also fast 20 % Ersparnis.

Mit einem arithmetischen Kodierer kann man sich der optimalen Codierung weiter annähern. Dieses Verfahren sorgt implizit für eine gleichmäßigere Verteilung der Bits auf die zu codierenden Zeichen, ohne dass explizit für jedes Zeichen ein individuelles Codezeichen konstruiert wird. Aber auch mit diesem Verfahren kann im Allgemeinen nicht die maximale Entropie erreicht werden. Dies liegt daran, dass es weiterhin einen „Verschnitt“ gibt, der darauf beruht, dass nur ganzzahlige Bitwerte tatsächlich auftreten können, während die Entropie meist Bruchteile von Bits erfordert. Im oben genannten Beispiel erreicht auch der Arithmetische Codierer nur eine Codelänge von einem Bit. Der Verschnitt verschwindet allerdings im Allgemeinen mit zunehmender Länge der zu codierenden Daten, so dass im Grenzwert die Entropie maximiert werden kann.

Modell

Um die Anzahl der Bits für jedes Zeichen festlegen zu können, muss man zu jedem Zeitpunkt des Kodierungsprozesses möglichst genaue Angaben über die Wahrscheinlichkeit der einzelnen Zeichen machen. Diese Aufgabe hat das Modell. Je besser das Modell die Wahrscheinlichkeiten vorhersagt, desto besser die Kompression. Das Modell muss beim Komprimieren und Dekomprimieren genau die gleichen Werte liefern. Im Laufe der Zeit wurden verschiedene Modelle entwickelt.

Statisches Modell

Das Statische Modell nimmt an, dass jedes Zeichen für sich genommen eine bestimmte Auftrittswahrscheinlichkeit hat, die sich innerhalb der Zeichenfolge nicht ändert. Vor dem eigentlichen Kodieren werden die Auftrittswahrscheinlichkeiten der einzelnen Zeichen in der gesamten Zeichenfolge bestimmt und ergeben eine Wahrscheinlichkeitstabelle. Die Auftrittswahrscheinlichkeiten werden anschließend zur Kodierung der gesamten Zeichenfolge verwendet.

Vorteile:

• Die Kodiertabelle lässt sich einfach und schnell berechnen.
• Die Kodiertabelle muss nicht für weitere Zeichenfolgen aufbewahrt werden.
• Die reine Ausgabe der Kodierung (also ohne die Wahrscheinlichkeitstabelle) ist garantiert nicht größer als die Eingabezeichenfolge.

Nachteile:

• Beim Kodieren muss die gesamte Zeichenfolge zugreifbar sein, da sie zweimal durchlaufen wird. Dadurch lässt das Modell keinen Datenstromalgorithmus zu.
• Die Wahrscheinlichkeitstabelle muss an den Dekodierer übermittelt werden und erhöht dadurch den Speicherbedarf der kodierten Daten.
• Die Auftrittswahrscheinlichkeiten beziehen sich auf die gesamte Zeichenfolge, d. h. die Wahrscheinlichkeiten passen sich nicht an lokale Veränderungen in der Eingabezeichenfolge an.

Dynamisches Modell

In diesem Modell verändern sich die Wahrscheinlichkeiten im Laufe des Kodierungsprozesses. Dabei gibt es mehrere Möglichkeiten:

Vorwärts dynamisch

Die Wahrscheinlichkeiten beziehen sich auf bereits kodierte Zeichen, das heißt, hier wird nach dem Kodieren eines Zeichens die Wahrscheinlichkeit dieses Zeichens erhöht.

Rückwärts dynamisch

Hier wird vor dem Kodieren ausgezählt, wie oft jedes Zeichen vorkommt. Aus diesen Zählern lassen sich genaue Wahrscheinlichkeiten ermitteln. Im Laufe des Kodierungsprozesses wird für jedes kodierte Zeichen der dazugehörende Zähler um 1 verringert. Da gegen Ende die Zähler für alle Zeichen gegen 0 streben, werden die Wahrscheinlichkeiten für nicht mehr vorkommende Zeichen auch 0. Diese Zeichen können nicht mehr kodiert werden. Andere Zeichen können dafür mit weniger Bits kodiert werden, da deren Wahrscheinlichkeit steigt. Die Kodiereffizienz steigt auf diese Weise so weit an, dass das letzte Zeichen mit 0 Bits kodiert werden kann.

Vorteile:

• Anpassung des Modells an lokale Gegebenheiten
• Statistik-Informationen müssen im vorwärts-dynamischen Modell nicht übertragen werden.

Nachteile:

• Tabellen müssen nach jedem Zeichen überarbeitet werden. Das kostet Rechenzeit.
• Die Statistik eilt den wahren Gegebenheiten hinterher. Im schlimmsten Fall stimmt die Statistik nie mit den wahren Wahrscheinlichkeiten überein, was dazu führt, dass mehr Bits benötigt werden.

Normalerweise arbeitet man bei dynamischen Modellen nicht mit Wahrscheinlichkeiten, sondern mit den Häufigkeiten der Zeichen.

Dynamische Modelle lassen auch noch andere Variationsmöglichkeiten zu.

Man kann Statistik-Daten altern, indem man von Zeit zu Zeit die Häufigkeiten der Zeichen halbiert. Damit verringert man den Einfluss von weit zurückliegenden Zeichen.

Für noch nie vorgekommene Zeichen gibt es mehrere Varianten:

• Man nimmt eine Häufigkeit von mindestens 1 für jedes Zeichen an, so dass alle Zeichen kodiert werden können.
• Man fügt dem Alphabet ein neues Zeichen hinzu. Dieses Zeichen deutet ein Verlassen des Kontextes an. Nachdem diese Zeichen kodiert wurden, können alle Zeichen des Alphabetes mit einem festen Code geschrieben oder gelesen werden. Das Zeichen wird normalerweise Escape-Zeichen genannt. Einige der besten Komprimieralgorithmen, die der Familie PPM, benutzen dieses Vorgehen.

Level des Modells

Das Level eines Modells bezieht sich darauf, wie viele Zeichen der Historie vom Modell für die Berechnung der Wahrscheinlichkeiten herangezogen werden. Ein Level-0-Modell betrachtet keine Historie und gibt die Wahrscheinlichkeiten global an. Ein Level-1-Modell dagegen betrachtet das Vorgängerzeichen und trifft in Abhängigkeit von diesem Zeichen seine Aussage über die Wahrscheinlichkeit. (Soll deutscher Text kodiert werden, ist zum Beispiel die Wahrscheinlichkeit des Buchstabens „U“ nach einem „Q“ viel höher, oder die Wahrscheinlichkeit eines Großbuchstabens in der Mitte eines Wortes viel kleiner als nach einem Leerzeichen). Das Level kann theoretisch beliebig hoch sein, erfordert dann aber enormen Speicherplatz und große Datenmengen, um aussagekräftige Statistiken zu erhalten.

PPM-Algorithmen verwenden einen arithmetischen Kodierer mit einem dynamischen Modell des Levels 5.

Literatur

• Mark Nelson, Jean-Loup Gailly: The Data Compression Book, zweite Ausgabe. M & T Books, New York 1996, ISBN 1-55851-434-1.

Dieses Buch bereitet einen relativ guten Einstieg. Es beschäftigt sich allerdings mehr mit der Implementierung in C als mit der Theorie der Datenkompression.

• Khalid Sayood: Introduction to Data Compression, zweite Ausgabe. Morgan Kaufmann Publishers, San Francisco 2005, ISBN 1-55860-558-4.

Dieses Buch ist ein Standardwerk zu den theoretischen und anwendungsrelevanten Grundlagen der Datenkompression.

• Stefan Weinzierl (Hrsg.): Handbuch der Audiotechnik. Springer Verlag, Berlin 2008, ISBN 978-3-540-34300-4.
• Tilo Strutz: Bilddatenkompression. Grundlagen, Codierung, Wavelets, JPEG, MPEG, H.264. 4. überarbeitete und ergänzte Auflage, Vieweg + Teubner, Wiesbaden 2009, ISBN 978-3-8348-0472-3.