Arithmetisches Kodieren

Das arithmetische Kodieren wird zur verlustfreien Datenkompression eingesetzt und ist eine Form der Entropiekodierung.

Grundprinzip

Das Verfahren lässt sich am einfachsten mit unendlich genauen Fließkommazahlen beschreiben, auch wenn die eigentlichen Implementierungen dann wieder auf endlich genaue Integer-Zahlen zurück greifen müssen.

Eine (eigentlich unendlich lange) Symbolfolge wird beim Arithmetrischen Codieren durch eine Zahl x in einem definierten Intervall dargestellt (normalerweise gilt 0 <= x < 1). Um die Symbolkette zu erhalten für die x steht wird das Intervall, innerhalb dessen sich x befindet rekursiv in Subintervalle unterteilt. Die Größe der Intervalle hängt von der Häufigkeit der Symbole ab. Seltene Symbole erhalten kleine, oft vorkommende Symbole große Subintervalle zugeordnet.

Beim dekomprimieren startet der Algorithmus mit dem Intervall [0; 1[. Dieses wird in Subintervalle zerlegt. Es wird getestet, in welchem dieser Intervalle die Zahl x, die entschlüsselt werden soll liegt. Das Zeichen, zu dem das Intervall gehört ist das erste Symbol, das gesucht wird. Danach wird das soeben gefundene Subintervall wieder auf die gleiche Art und Weise zerlegt und überprüft, in welchem dieser Intervalle x liegt. Das wird so lange fortgesetzt, bis alle Symbole gefunden wurden.

Beim komprimieren läuft der Vorgang genauso ab. Man startet mit dem Intervall [0; 1[. Dieses Intervall wird zerteilt und das Subintervall gewählt, das zu dem zu kodierenden Symbol gehört. Dieses Intervall wird wieder zerlegt und ein weiteres noch kleineres Subintervall ausgewählt. Das Intervall wird so langer verkleinert, bis alle zu kodierenden Symbole abgearbeitet wurden. Dann wird eine Zahl, die in dem zuletzt erhaltenen Intervall liegt abgespeichert.

Die Subintervalle müssen so gewählt werden, dass der Codierer sowie der Decodierer die genaue Größe und Lage der Intervalle identisch wählen können. Der Codierer wird normalerweise vor Beginn des Verschlüssellungsprozesses eine Statistik über die Häufigkeit der einzelnen Symbole erstellen. Mit den Daten dieser Statistik wird die Größe der Subintervalle berechnet, das heißt, dass auch der Decoder diese Informationen erhalten muss. Das ist das gleiche Problem wie bei allen Entropiecodierern.

Die genaue Position der Intervalle ist für die Qualität des Algorithmus nicht von Bedeutung, sodass man hier eine feste Position für die einzelnen Symbole festlegen kann.

Beispiel

In diesem Beispiel wird die Zeichenkette "AAABAAAC" komprimiert. Zuerst muss die Größe der Subintervalle berechnet werden. Dazu dient eine Häufigkeitsanalyse.

Die optimale Bitzahl ergibt sich aus der Formel für die Entropie. Mit diesem Wert lässt sich errechnen, dass der Informationsgehalt der Zeichenkette 8,49 Bits entspricht.

Nun zum Algorithmus. Die folgende Tabelle zeigt die genauen Werte für das aktuelle Subintervall. Das Bild zeigt noch eine Grafik über den Ablauf beim De-Codieren diese Beispiels.

Gespeichert wird nun eine Zahl aus dem letzten Intervall, also z. B. 0.336.

Das entspricht zwischen 8 und 9 Bits. Huffman hätte für die gegebene Zeichenfolge dagegen 10 Bit benötigt (1 für jedes A und je 2 für B und C)

Der Unterschied beträgt in diesem Beispiel 10%. Der Gewinn wird größer, wenn die tatsächlich von der Huffmann Codierung verwendete Bitzahl mehr von der optimalen abweicht, also wenn ein Zeichen extrem häufig vorkommt.

Implementation

Da man bei einer konkreten Implementierung nicht mit unendlich genauen Gleitkommazahlen arbeiten kann muss die konkrete Umsetzung des Algorithmus etwas anders erfolgen.

Dabei werden hauptsächlich 2 Methoden angewandt:

• Vereinfache das Alphabet, arbeite nur noch mit einem Bit. Anstatt das Intervall also in n Teile zu zerlegen wird es nur in 2 Teile geteilt. Diese Vereinfachung führt zu weiteren Möglichkeiten bestimmte Berechnungen durch Näherungen darzustellen. 2 Vertreter dieses Herangehens sind der Q-Coder von IBM und der ELS-Coder

• Eine andere Variante ist die Annäherung der Intervallgrenzen mit Ganzen Zahlen. Dazu wird das Intervall so skaliert, dass es gerade noch durch die gewählten Integers dargestellt werden kann. Dann wird normal gerechnet. Zeichnet sich eine Stelle als gesichert ab, d.h. die untere und obere Intervallgrenze sind identisch in den ersten Stellen, dann können diese Stellen ausgegeben werden und das Intervall wieder skaliert werden. Der Coder läuft unter dem Namen Range-Coder

Beide Varianten führen zu einer Verschlechterung des Ergebnisses, die Anzahl der ausgegebenen Bits ist also nicht mehr optimal.

Weblinks

• ELS-Coder Dokument
• Q-Coder Seite von IBM
• Website des Range-Coders