Das arithmetische Kodieren ist eine Form der Entropiekodierung, die unter anderem zur verlustfreien Datenkompression eingesetzt wird.
Dieser Artikel beschreibt nur, wie man mit einem gegebenen Satz von Zeichen-Wahrscheinlichkeits-Paaren einzelne Zeichen so kodieren kann, dass man eine möglichst kleine mittlere Wortlänge benötigt. Dabei ist durch die Entropie (mittlerer Informationsgehalt) eine untere Schranke gegeben (Quellencodierungstheorem).
Das immer zu einem Entropiekodierer gehörende Modell der Zeichen-Wahrscheinlichkeiten ist unter Entropiekodierung#Modell beschrieben.
Zu den Begründern zählt Jorma Rissanen Ende der 1970er und Anfang der 1980er Jahre.
Das Verfahren funktioniert theoretisch mit unendlich genauen reellen Zahlen, auch wenn in den eigentlichen Implementierungen dann wieder auf endlich genaue Integer-, Festkomma- oder Gleitkommazahlen zurückgegriffen werden muss. Dies führt aber immer dazu, dass gerundet werden muss und somit das Ergebnis nicht mehr optimal ist.
Die Eingaben für den arithmetischen Kodierer werden im Folgenden als Symbol, ein Zeichen, bezeichnet. Die Ausgabe für den Kodierer ist eine reelle Zahl (hier mit x bezeichnet).
Zuerst müssen sich Kodierer und Dekodierer auf ein Intervall einigen, in dem sich die Zahl x befinden soll. Normalerweise wird hier der Bereich zwischen 0 und 1 (exklusive) benutzt, also das halboffene Intervall [math][0, 1) = \{x \in \mathbb{R} \,|\, 0 \le x \lt 1\}[/math].
Außerdem müssen Kodierer und Dekodierer bei der De- bzw. Kodierung eines Zeichens immer identische Tabellen mit den Wahrscheinlichkeiten aller möglichen dekodierbaren Zeichen zur Verfügung haben. Für die Bereitstellung dieser Wahrscheinlichkeiten ist das Modell verantwortlich.
Eine Möglichkeit ist, vor dem Kodieren speziell für die Eingabedaten eine Häufigkeitsanalyse zu erstellen und diese dem Dekodierer, zusätzlich zur eigentlichen Nachricht, mitzuteilen. Kodierer und Dekodierer verwenden dann für alle Zeichen diese Tabelle.
Der Dekodierer kann nun ein Zeichen nach dem anderen entschlüsseln, indem er folgende Schritte ausführt:
Bei diesem Algorithmus fällt auf, dass er nicht terminiert: Es ist allein an der Zahl x nicht erkennbar, wann das letzte Zeichen dekodiert wurde. Es muss dem Dekodierer also immer durch eine zusätzliche Information mitgeteilt werden, wann er seine Arbeit beendet hat. Dies wird üblicherweise in Form einer Längenangabe realisiert, kann aber auch (bspw. wenn bei der Kodierung nur ein einziger Datendurchlauf erwünscht ist) durch ein Sonderzeichen mit der Bedeutung „Ende“ geschehen.
Die Subintervalle müssen so gewählt werden, dass Kodierer und Dekodierer die Größe und Position gleich bestimmen. Wie oben schon erwähnt, ergibt sich die Größe der Subintervalle aus den Wahrscheinlichkeiten der Zeichen.
Die Anordnung (Reihenfolge) der Intervalle dagegen ist für die Qualität des Algorithmus nicht von Bedeutung, sodass man hier eine beliebige Reihenfolge fest vorgeben kann. Diese ist Gegenstand einer Vereinbarung (z. B. alphabetische Ordnung).
Eine Möglichkeit für die Berechnung der Intervalle ist folgende:
[math]I_l[/math] und [math]I_h[/math] sind die Grenzen des Intervalls. [math]I_s[/math] ist die Länge des Intervalls, also [math]I_h-I_l[/math]. Die beiden Werte [math]L[/math] und [math]H[/math] sind die Summe der Wahrscheinlichkeiten aller Zeichen mit einem Code kleiner, bzw. kleiner gleich dem zu kodierenden Zeichen [math]x[/math].
In diesem Beispiel wird die Zeichenkette „AAABAAAC“ komprimiert. Zuerst wird für die Größe der Subintervalle die Häufigkeiten aller Zeichen benötigt. Der Einfachheit halber wird eine statische Wahrscheinlichkeit für alle Zeichen verwendet.
Zeichen | Häufigkeit | optimale Bitzahl |
p(A) | 75 % | 0,415 |
p(B) | 12,5 % | 3 |
p(C) | 12,5 % | 3 |
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 Ablauf. Die folgende Tabelle zeigt die genauen Werte für die Subintervalle nach dem Codieren der einzelnen Zeichen. Die Grafik rechts veranschaulicht die Auswahl der Subintervalle noch einmal.
Intervall | Intervallgröße | ||
0 - | 1 | 1 | |
A | 0 - | 0,75 | 0,75 |
A | 0 - | 0,5625 | 0,5625 |
A | 0 - | 0,421875 | 0,421875 |
B | 0,31640625 - | 0,369140625 | 0,052734375 |
A | 0,31640625 - | 0,35595703125 | 0,03955078125 |
A | 0,31640625 - | 0,3460693359375 | 0,0296630859375 |
A | 0,31640625 - | 0,338653564453125 | 0,022247314453125 |
C | 0,335872650146484375 - | 0,338653564453125 | 0,002780914306640625 |
Gespeichert wird eine beliebige, möglichst kurze Zahl aus dem letzten Intervall, also z. B. 0,336.
Das entspricht zwischen 8 und 9 Bits. Die Huffman-Kodierung 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 Huffman-Kodierung verwendete Bitzahl mehr von der optimalen abweicht, also wenn ein Zeichen extrem häufig vorkommt.
Der Dekodierer nimmt diese Zahl zum Dekodieren. Dabei läuft Folgendes ab:
Arithmetisches Kodieren ist asymptotisch optimal[1]:
Nachdem das letzte Symbol verarbeitet wurde erhält man ein Intervall [math][r, r+s)[/math] mit
Das entspricht der Wahrscheinlichkeit, bei gegebenen Symbolwahrscheinlichkeiten [math]p(x_i)[/math], genau solch eine Sequenz zu erhalten.
Um nun binär einen Wert im Intervall [math][r, r+s)[/math] anzugeben, benötigt man
Da
und
können wir die Länge [math]l[/math] der arithmetisch kodierten Sequenz abschätzen:
Das bedeutet, man benötigt mindestens so viele Bits wie die Entropie, höchstens jedoch zwei Bits mehr.
Die mittlere Länge [math]l_{Sym} = \frac{l}{n}[/math] eines kodierten Symbols ist beschränkt auf
Für lange Sequenzen verteilen sich diese (höchstens zwei) zusätzlichen Bits gleichmäßig auf alle Symbole, so dass die mittlere Länge eines kodierten Symbols dann asymptotisch gegen die wahre Entropie geht[2]:
Die Huffman-Kodierung kann theoretisch eine optimale Kodierung erreichen, nämlich genau dann, wenn alle Symbolwahrscheinlichkeiten [math]p_i = 2^{-k_i}, k_i \in \mathbb{N^+}[/math] sind.[3]
Praktisch ist dies kaum der Fall, so dass die arithmetische Kodierung meist effizienter kodiert.
Da man bei einer konkreten Implementierung nicht mit unendlich genauen reellen Zahlen arbeiten kann, muss die konkrete Umsetzung des Algorithmus etwas anders erfolgen. Die maximale Genauigkeit der Zahlen ist im Allgemeinen fest vorgegeben (z. B. 32 Bits) und kann diesen Wert nicht überschreiten. Deshalb kann man einen Arithmetischen Kodierer nicht auf einem realen Computer umsetzen.
Um das Problem der begrenzten Genauigkeit zu umgehen, werden zwei Schritte unternommen:
Punkt 1 führt eigentlich dazu, dass der Algorithmus kein Arithmetischer Kodierer mehr ist, sondern nur ähnlich. Es gibt aber einige eigenständige Algorithmen, die vom Arithmetischen Kodierer abstammen; diese sind:
Trotz dieser Verfahren bleiben verschiedene Probleme mit der Arithmetischen Kodierung: