Entropiekodierung

Die Entropiekodierung ist eine Methode zur verlustfreien Datenkompression, die jedem einzelnen Zeichen eines Textes eine unterschiedlich lange Folge von Bits zuordnet. Im Gegensatz zu Stringersatzverfahren (wie LZ77 oder LZ78), die einer Folge von Zeichen des Originaltextes durch eine Folge von Zeichen eines anderen Alphabets ersetzt.

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. LHARC, zum Beispiel verwendet einen LZ Kodierer und gibt die von diesem Kodierer ausgegebenen Zeichen an einen Huffman-Kodierer. Auch ZIP und BZIP haben als letzte Stufe einen Entropiekodierer.

Kodierung

Die Kodierung der Zeichen mit einer variablen Anzahl von Bits stellt ein Problem dar. Insbesondere, wenn man bedenkt, dass die Entropie für fast alle Wahrscheinlichkeiten eine rationale Zahl ergibt.

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. 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 z.B. bei Daten verwendet werden, bei denen die Häufigkeitverteilung 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 verschiedenen 2 Symbolen soll komprimiert werden. Das eine Zeichen hat eine Wahrscheinlichkeit von $\mathrm {p} (A)=0{,}75$, das andere von $\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 $\log _{2}(0{,}75)\approx 0{,}41$ Bits für das Zeichen A verwenden und dafür $\log _{2}(0{,}25)=2$ Bits für B. Das führt zu einer Ausgabe, die nur $0{,}75*\log _{2}(0{,}75)+0{,}25*\log _{2}(0{,}75)\approx 0.81$ Bits pro Zeichen enthält.

Mit einem Arithmetischen Kodierer kann man Zeichen Entropie-Optimal abspeichern.

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 zu 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

Beim Statischen Modell wird vor der Kodierung der Zeichenfolge eine Statistik über die gesamte Folge erstellt. Die dabei gewonnenen Wahrscheinlichkeiten werden zur Kodierung der gesamten Zeichenfolge verwendet.

• Vorteile
  • Kodiertabellen müssen nur einmal erstellt werden. Das Verfahren ist deshalb sehr schnell.
  • Die Ausgabe, ohne die zum dekomprimieren notwendigen Statistiken sind garantiert nicht größer als der Originaltext

• Nachteile
  • Die Statistik muss an den Decoder übermittelt werden (entweder als Statistik oder in Form der Huffman oder Shannon-Fano Codes) was Speicher kostet
  • Die Statistik bezieht sich auf die gesamte Zeichenfolge, d.h. die Werte passen sich nicht an lokale Gegebenheiten in der Zeichenkette 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, d.h. 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 vor kommt. Aus dieser Anzahl lassen sich genaue Wahrscheinlichkeiten ermitteln. Im Laufe des Kodierungsporozesses werden die Anzahlen erniedrigt, sodass gegen Ende die Wahrscheinlichkeiten für die einzelnen Zeichen sehr exakt werden.

• 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 waren Gegebenheiten hinterher. Im schlimmsten Fall stimmt die Statistik nie mit den wahren Wahrscheinlichkeiten überein, was dazu führt, das mehr Bits benötigt werden.

Normalerweise arbeitet man bei dynamischen Modellen nicht wirklich 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, sodass 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 Kode geschrieben oder gelesen werden. Das Zeichen wird normalerweise Ecape-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 Buchstaben "U" nach einem "Q" viel höher, oder die Wahrscheinlichkeit eines großen Buchstaben in der Mitte eines Wortes viel größer als nach einem Leerzeichen). Das Level kann theoretisch beliebig hoch sein, erfordert dann aber enormen Speicherplatz gigantische Datenmengen, um aussagekräftige Statistiken zu erhalten.

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

Literatur

Es gibt nur sehr wenige Bücher zum Thema Datenkompression

• Mark Nelson - The Data Compression Book

bereitet einen relativ guten Einstig. Das Buch beschäftigt sich allerdings mehr mit der Implementation als mit der Theorie der Datenkompression.

Weblinks

• Compression Pointers

Enthält eine lange Liste mit Links zum Thema Datenkomprimierung, u.a. auch für PPM