Arithmetisches Kodieren

Die arithmetische Kodierung ist eine Form der Entropiekodierung, die bei der verlustfreien Datenkompression verwendet wird und erzielt Kompressionsraten, welche sehr nahe am theoretischen Limit der Entropie liegen. Als Begründer der arithmetischen Kodierung gilt Jorma Rissanen, welcher ab 1976 bis Anfang der 1980er Jahre wesentliche Arbeiten zu diesem Teilgebiet der Informationstheorie leistete.

Herkömmliche Codierungen basieren in der Repräsentierung der Information mit einer festen Anzahl von ganzzahligen Bits, beispielsweise im ASCII-Code mit 7 Bit, oder es werden häufig verwendete Zeichen mit weniger Bits gespeichert, und weniger häufig vorkommende Zeichen werden mit mehr Bits gespeichert, wie es in der Huffman-Kodierung der Fall ist. Die arithmetische Codierung unterscheidet sich davon in dem wesentlichen Punkt, dass die Quellinformation nicht in einzelne Komponenten aufgeteilt wird, sondern die gesamte Quellinformation oder ein längerer Teilbereich daraus, als eine rationale Zahl dargestellt wird. Üblicherweise erfolgt die Abbildung in Form eines beliebig präzisen Bruchs q bestehend aus zwei natürlichen Zahlen mit den Intervallgrenzen 0,0 ≤ q < 1,0. Es gibt auch Variationen der arithmetischen Codierung für eine kürzere Berechnungszeit, welche nur eine einzelne, beliebig lange natürliche Zahl zur Informationsdarstellung verwenden. Generell ist die arithmetische Kodierung rechenintesiver als herkömmliche Verfahren, welche Codewörter mit einer Anzahl ganzzahliger Bits bilden.

Grundprinzip

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 $[0,1)=\{x\in \mathbb {R} \,|\,0\leq x<1\}$ (siehe ).

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.

Kodierer

1. Initialisiere das aktuelle Intervall mit dem vereinbarten Startintervall – wie oben erwähnt ist dies meist das Intervall $[0,1)$.
2. Unterteile das aktuelle Intervall in Subintervalle, wobei jedem kodierbaren Zeichen ein Subintervall zugewiesen wird. Die Größe der Subintervalle wird von der Häufigkeit des Auftretens des Zeichens bestimmt (Auftretenswahrscheinlichkeit). Die Reihenfolge der Intervalle ist durch eine Vereinbarung festgelegt (z. B. in alphabetischer Ordnung).
3. Das Subintervall, das dem nächsten Zeichen der Eingabe entspricht, wird zum aktuellen Intervall.
4. Sind noch weitere Zeichen zu kodieren, dann weiter bei Punkt 2. Sonst weiter beim nächsten Punkt.
5. Gib eine beliebige Zahl aus dem aktuellen Intervall und zusätzlich die Anzahl der kodierten Zeichen aus. Dieses ist die Zahl x, die vom Dekodierer wie oben beschrieben entschlüsselt werden kann. Diese Zahl wird so gewählt, dass sie möglichst wenig Nachkommastellen hat, also möglichst „rund“ ist und sich daher mit relativ wenigen Bits darstellen lässt.

Dekodierer

Der Dekodierer kann nun ein Zeichen nach dem anderen entschlüsseln, indem er folgende Schritte ausführt:

1. Initialisiere das aktuelle Intervall mit dem vereinbarten Intervall – meist das Intervall $[0,1)$.
2. Zerlege das aktuelle Intervall auf die identische Art wie der Kodierer in Subintervalle, und weise jedem Subintervall ein Zeichen zu (siehe oben).
3. Finde heraus, in welchem dieser Subintervalle die Zahl x liegt und gib das Zeichen aus, das diesem Subintervall zugeordnet ist. Außerdem wird dieses Subintervall nun zum aktuellen Intervall.
4. Sind noch weitere Zeichen zu dekodieren, fahre fort bei Punkt 2, mit dem neuen aktuellen Intervall.

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.

Intervallteilung

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:

${\begin{aligned}I_{l}(n+1)&=I_{l}(n)+I_{s}L\\I_{h}(n+1)&=I_{l}(n)+I_{s}H\end{aligned}}$

$I_{l}$ und $I_{h}$ sind die Grenzen des Intervalls. $I_{s}$ ist die Länge des Intervalls, also $I_{h}-I_{l}$. Die beiden Werte $L$ und $H$ sind die Summe der Wahrscheinlichkeiten aller Zeichen mit einem Index kleiner, bzw. kleiner gleich dem zu kodierenden Zeichen $x$.

${\begin{aligned}L&=\sum p(i),i<x\\H&=\sum p(i),i\leq x\end{aligned}}$

Wird beispielsweise ein Alphabet A = {A,B,C} verwendet, dessen Wahrscheinlichkeiten p(A) = 0.75, p(B) = 0.125, p(C) = 0.125 betragen und das nächste zu kodierende Zeichen x sei C, dann werden $L$ und $H$ wie folgt berechnet:

${\begin{aligned}L&=p(A)+p(B)=0.875\\H&=p(A)+p(B)+p(C)=1\end{aligned}}$

Beispiel

Intervallschachtelung beim Arithmetischen Kodieren

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	Wahrscheinlichkeit	optimale Bitzahl
A	6	p(A) = 75 %	$I(A)=-\log _{2}(A)=-\log _{2}(0{,}75)=0{,}415$
B	1	P(B) = 12,5 %	$I(B)=-\log _{2}(B)=-\log _{2}(0{,}125)=3$
C	1	P(C) = 12,5 %	$I(C)=-\log _{2}(C)=-\log _{2}(0{,}125)=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.

$I_{\text{ges}}=\sum _{i=1}^{3}n_{i}\cdot I({z_{i}})=6*0{,}415+1*3+1*3=8{,}49$

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:

• Gestartet wird mit dem Startintervall [0; 1]. Dieses Intervall wird vom Dekodierer in die drei Teilintervalle zerlegt (so wie in der ersten Zeile des Bildes).
• 0,336 liegt im Subintervall A [0; 0,75]. Also ist das erste Zeichen A.
• Das aktuelle Subintervall wird [0; 0,75]
• [0; 0,75] wird wieder nach dem bekannten Schema zerlegt
• 0,336 liegt wieder im ersten Intervall [0; 0,5625], also A ausgeben.
• [0; 0,5625] wird wieder nach dem bekannten Schema zerlegt
• 0,336 liegt wieder im ersten Intervall [0; 0,421875], also A ausgeben.
• [0; 0,421875] wird wieder nach dem bekannten Schema zerlegt
• 0,336 liegt dieses Mal im zweiten Intervall [0,31640625; 0,369140625], also wird B ausgeben.
• [0,31640625; 0,369140625] wird wieder nach dem bekannten Schema zerlegt
• ...

Optimalität

Arithmetisches Kodieren ist asymptotisch optimal:

Nachdem das letzte Symbol verarbeitet wurde erhält man ein Intervall $[r,r+s)$ mit

$s=\prod _{i=1}^{N}p(x_{i})$

Das entspricht der Wahrscheinlichkeit, bei gegebenen Symbolwahrscheinlichkeiten $p(x_{i})$, genau solch eine Sequenz zu erhalten.

Um nun binär einen Wert im Intervall $[r,r+s)$ anzugeben, benötigt man

• mindestens $-\lceil \log _{2}(s)\rceil =-\log _{2}(s)$ Bits, falls $\exists \;x=0\mod 2^{-\lceil \log _{2}(s)\rceil },x\in [r,r+s)$
• höchstens jedoch $-\lceil \log _{2}(s)\rceil +1$ Bits (um das Intervall mit einer Genauigkeit von s/2 zu beschreiben, was im Binärsystem gerade noch genügt, um unterscheiden zu können, ob der Wert innerhalb liegt).

Da

${\begin{aligned}-\log _{2}(s)&=-\log _{2}{\big (}\prod _{i=1}^{N}p(x_{i}){\big )}\\&=-\sum _{i=1}^{N}\log _{2}p(x_{i})\\&=:n\cdot H(X)\end{aligned}}$

und

$-\lceil \log _{2}(s)\rceil +1<-\log _{2}(s)+2$

können wir die Länge $l$ der arithmetisch kodierten Sequenz abschätzen:

$n\cdot H(X)\leq l<n\cdot H(X)+2$

Das bedeutet, man benötigt mindestens so viele Bits wie die Entropie, höchstens jedoch zwei Bits mehr.

Die mittlere Länge $l_{Sym}={\frac {l}{n}}$ eines kodierten Symbols ist beschränkt auf

$H(X)\leq l_{Sym}<H(X)+{\frac {2}{n}}$

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:

$\lim _{n\to \infty }{\Big (}H(X)+{\frac {2}{n}}{\Big )}=H(X)$

Vergleich zur Huffman-Kodierung

Wenn sich alle Symbolwahrscheinlichkeiten $p_{i}$ in der Form $p_{i}=2^{-k_{i}},k_{i}\in \mathbb {N^{+}}$ darstellen lassen, dann erzeugen arithmetische Kodierung und Huffman-Kodierung einen identisch langen Datenstrom und sind gleich (d. h. optimal) effizient. In der Praxis ist dies aber so gut wie nie der Fall.

Implementierung

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:

1. Die Stellen nach der oberen Grenze der Genauigkeit werden abgeschnitten. Das führt dazu, dass die Intervallgrößen nicht mehr exakt mit den geforderten Werten übereinstimmen. Das führt zu einer Verschlechterung des Ergebnisses.
2. Das Intervall muss ab und an wieder vergrößert werden, da sonst nach einigen kodierten Zeichen die Genauigkeit der Zahlen aufgebraucht ist. Deshalb werden höherwertige Stellen, die feststehen, ausgegeben und aus den Zahlen entfernt. Im Beispiel von oben kann man also nach dem Kodieren des Zeichens B sicher sagen, dass die Ergebniszahl mit 0,3 beginnt. Man kann also bereits hier 0,3 ausgeben und von den Intervallgrenzen abziehen. Danach wird die Intervallgrenze mit 10 skaliert, und es wird mit diesem Wert weitergerechnet.

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:

Der Range-Coder

Dieser Kodierer ist eine relativ direkte Umsetzung des Arithmetischen Kodierers mit Integerzahlen.

Der Q-Coder (von IBM entwickelt und patentiert)

Dieser vereinfacht zusätzlich das Alphabet auf nur zwei Zeichen. Dieses Vorgehen erlaubt eine Annäherung der Intervallaufteilung mit Additionen anstatt Multiplikationen wie beim Range-Coder.

Der ELS-Coder

Dieser arbeitet auch nur mit zwei Zeichen, ist aber effizienter bei relativ gleich wahrscheinlichen Zeichen, während beim Q-Coder beide Zeichen möglichst unterschiedliche Wahrscheinlichkeiten haben sollten.

Trotz dieser Verfahren bleiben verschiedene Probleme mit der Arithmetischen Kodierung:

Geschwindigkeit

Arithmetische Kodierer sind relativ aufwendig und langsam. Für jedes Zeichen muss beim Range-Coder eine Division ausgeführt werden. Die anderen Kodierer erfordern das mehrmalige Ausführen des Kodierprozesses für alle Bits des Zeichens.

Patente

Die meisten Softwarepatente im Bereich des arithmetischen Kodierens wurden in den 1980er und frühen 1990er Jahren erteilt und sind mittlerweile ausgelaufen. Der Q-Coder ist zwar neben dem Huffman Coder für JPEG zulässig, wird aber fast nie verwendet, da er von IBM patentiert war.

Kleiner Gewinn

Mit verschiedenen Methoden lässt sich erreichen, dass die viel schnellere Huffman-Kodierung nur unwesentlich schlechtere Ergebnisse liefert als der aufwendige Arithmetische Kodierer. Dazu gehört, dass manchmal Zeichenketten als eigenständige Zeichen behandelt werden. Somit lässt sich der „Verschnitt“ senken, der dadurch entsteht, dass jedes Zeichen mit einer ganzzahligen Bitlänge dargestellt wird.

Weblinks

• Ausarbeitung zu Grundlagen der arithmetischen Kodierung, einschließlich Quelltext (E. Bodden et al. 2002; PDF-Datei; 568 kB)
• Q-Coder-Seite von IBM
• Website des Range-Coders, Quellcode zum Download
• Beschreibung des Algorithmus des Range-Coders in Pseudocode
• Das elektronische Buch Information Theory, Inference, and Learning Algorithms von David J. C. MacKay erklärt in Kapitel 6 das arithmetische Kodieren.