Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Arithmetische Codierung

zurück

5 Verlustfreie Verfahren

5.1 Statistische Verfahren

5.1.1 Der Morse Code

5.1.2 Shannon-Fano Codierung

5.1.3 Huffman Codierung

5.1.4 Präfixfreie Codes

5.1.5 MNP - MicroCom Network Protokoll

5.1.6 Arithmetische Codierung

5.1.7 Adaptive Arithmetische Codierung

5.1.8 Quasiarithmetische Codierung

5.1.9 CABAC

5.1.10 Dynamische Markov Codierung

5.1.11 PPM

5.1.12 BWT - Burrows-Wheeler-Transformation

5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus

Arithmetische Codierung

5.1.6 Arithmetische Codierung

Sowohl die Huffman-Codierung als auch die Shannon-Fano-Codierung sind nur selten in der Lage, die bestmögliche Codierung zu erreichen. Zwar führt die Anwendung des Huffman-Algorithmus zu einem effizienteren Codebaum, doch die untere Shannonsche-Informations-Grenze ist nur sehr selten erreichbar. Im Grunde genommen immer nur dann, wenn allen Symbolen eine Wahrscheinlichkeit p zugeordnet ist, die eine negative Potenz des Wertes 2 darstellt. Dann ist der Informationsgehalt des Symbols durch ein Codewort darstellbar, dessen Länge ein ganzzahliger positiver Wert größer als 0 ist. Die Arithmetische Codierung ist in der Lage, dieses Problem zu lösen. Das heißt es können Codes verwendet werden, deren Informationsgehalt exakt mit der Länge des gewählten Codewortes übereinstimmt.

An einem Beispiel festgemacht bedeutet es bei einem Huffman-Code, dass eine Wahrscheinlichkeit von 0.36 zu einem Codewort führt, welches entweder die Länge 1 oder die Länge 2 besitzt. Der reale Entscheidungs bzw. Informationsgehalt liegt jedoch zwischen den beiden Werten 1 und 2. Der Informationsgehalt dieses Wortes beträgt etwa 1.47 Bit. Sowohl mit dem Huffman-Algorithmus als auch mit dem Shannon-Fano-Algorithmus ist es nicht möglich, diesen fraktionalen Anteil irgendwie darzustellen.

Das Problem liegt darin begründet, dass jedem Symbol ein Codewort zugeordnet wird und diese unabhängig voneinander im Ausgabestrom ausgegeben werden. Begreift man den Ausgabestrom (Code) jedoch nicht als eine Folge aneinandergereihter Symbole, sondern als eine Einheit, bis zum letzten vorhandenen Bit, so können 'Überträge' mitgeführt werden. Das ist jedoch im übertragenen Sinne gemeint. Real ist es so, dass alle codierten Symbole vom ersten codierten Symbol an als abhängig voneinander angesehen werden müssen. Geht ein Teil der Information verloren, so kann das Ergebnis mit an Sicherheit grenzender Wahrscheinlichkeit nicht korrekt decodiert werden.

Es stellt sich die Frage, wie dieser Zusammenhang der Ausgabesymbole (Code) hergestellt werden kann. Dazu bediente man sich der folgenden Idee: Das offene Intervall [0..1), also jede erdenkliche Zahl zwischen 0 und 1 außer der Eins selbst, wird wie folgt betrachtet. Annahme ist, man möchte ein Symbol mit einer Wahrscheinlichkeit von 60 Prozent darstellen, weil es mit einer Wahrscheinlichkeit von 60 Prozent als Eingabe zu erwarten ist. Dann kann das Gesamtintervall in k verschiedene Teilintervalle zerlegt werden. Geht man nur von einer Gegenwahrscheinlichkeit von 40 Prozent aus, so gibt es demnach nur 2 Teilintervalle. Durch Angeben einer Zahl kann man aussagen, welches der beiden Ereignisse - Eintreffen(60 Prozent) oder Nichteintreffen (40 Prozent) - nach dem Lesen eines Eingabesymbols eingetreten ist. Beispielhaft soll das Eintreten eines Ereignisses durch das Intervall [0..0.6) und das Nichteintreten durch das Intervall [0.6..1) beschrieben werden. Wenn jemand eine beliebige Zahl aus dem ersten Intervall [0.0...0.6) (Es gibt überabzählar unendlich viele.) überträgt (bspw. 0.5), so meint er das konkrete Eintreten eines Ereignisses, überträgt jemand eine Zahl aus dem Intervall [0.6..1) bspw. 0.75, so meint er das Nichteintreten eines konkreten Ereignisses.

Welche Zahl aus diesem Intervall übertragen wird, scheint anfangs unerheblich. Ein Kriterium ist, die Zahl lässt sich durch möglichst wenige Ziffern darstellen und das andere Kriterium wiegt noch weitaus mehr. Niemand hindert uns daran, das erste oder zweite Teilintervall in weitere Teilintervalle zu zerlegen. Damit lassen sich schon zwei verschiedene Entscheidungen mit einer einzelnen Zahl zwischen 0 und 1 codieren. Denkt man über das Prinzip weiter nach, so gelangt man möglicherweise zu dem Schluss, dass das Intervall so oft geteilt werden kann, wie es Zeichen im Eingabestrom gibt. Wichtig ist nur, sich für das richtige Teilintervall anhand des jeweiligen Eingabesymbols zu entscheiden. Die Größe des Teilintervalls entspricht immer dem sicheren Ereignis (100 Prozent). Das Teilintervall ist proportional zu den zu erwartendenden Wahrscheinlichkeiten der folgenden Eingabesymbole aufzuteilen.

Arithmetische Codierung - Algorithmus

1. Beginne mit einer Definition des aktuellen offenen Intervalls (Beginnen Sie mit dem Intervall $I=[0;1)$ )
2. Wende für jedes Symbol der Eingabe die folgenden Schritte an :
   1. Teile das aktuelle Intervall in Teilintervalle, die proportional zu den Wahrscheinlichkeiten der Eingabesymbole sind
   2. Selektiere das Teilintervall des Eingabesymbols und definiere es als das aktuelle Intervall
3. Wenn die Codierung abgeschlossen ist, finde eine Zahl innerhalb des letzten Intervalls, welches dieses Teilintervall exakt beschreibt
4. Schreibe die ermittelte Zahl in eine Datei.

Durch die Verwendung eines Arithmetischen Codierers kann eine Bit-Allokation von fraktionalen Anteilen bei der Codierung erfolgen. Das bedeutet auch, dass damit Signalentropien von unter einem Bit pro Symbol möglich erreichen kann. Diese spielen insbesondere dann eine Rolle, wenn ein binäres Alphabet codiert wird. Jede noch so kleine Abweichung von der Wahrscheinlichkeit P=0.5 für das eine oder andere Symbol ist ein Codiergewinn. Man ist heute mittlerweile dazu übergegangen Binärinformationen/Binärentscheidungen mit arithmetischen Codierern zu codieren. Man bezeichnet einen derartigen Codierer als binären arithmetischen Codierer.

Es ist ebenso möglich, eine beliebige Aufteilung in k>=2 Teilintervalle vorzunehmen. Es spielt für den arithmetischen Codierer keine Rolle, ob eine Binärentscheidung codiert wird oder eines von k Teilintervallen verwendet werden soll. So lassen sich auch ternäre/k-näre Alphabete problemlos codieren. Der einzige Unterschied ist, dass k Teilintervalle bestimmt werden müssen. Auch spielt die Sortierung der Teilintervalle keine Rolle, so lange dem Codierer und dem Decodierer die gleiche Reihenfolge bekannt ist.

Bild: Entropie einer binären Quelle