Arithmetisches Kodieren

Die arithmetische Kodierung ist eine Form der Entropiekodierung, die bei der verlustfreien Datenkompression verwendet wird. Sie erzielt Kompressionsraten, die sehr nahe am theoretischen Limit der Entropie liegen.

Die Grundidee der arithmetischen Kodierung ist, aus einer Folge von Eingabesymbolen und deren Auftrittswahrscheinlichkeiten eine einzelne, möglichst „kurze“ rationale Zahl zu bilden. Aus dieser Zahl kann die ursprüngliche Folge von Eingabesymbolen wiederhergestellt werden.

Geschichte 
Als Begründer der arithmetischen Kodierung gilt Jorma Rissanen, der ab 1976 bis Anfang der 1980er Jahre wesentliche Arbeiten zu diesem Teilgebiet der Informationstheorie leistete.

Grundprinzip 
Die meisten Kodierungen teilen die Folge von Eingabezeichen in kurze Teile auf und kodieren jeden dieser Teile einzeln in Bits. Dabei kommt es vor, dass ein solcher kurzer Teil einen Informationsgehalt hat, der sich nicht in ganzen Bits ausdrücken lässt. Dadurch müssen „unvollständig genutzte“ Bits gespeichert werden, und das sorgt dafür, dass die kodierten Daten länger werden als unbedingt nötig.

Die arithmetische Kodierung unterscheidet sich von diesen Kodierungen dadurch, dass die Eingabezeichen nicht in kurze Teile unterteilt werden, sondern alle zusammen zu einer einzigen rationalen Zahl (Bruchzahl) zusammengerechnet werden. Dadurch werden die unvollständig genutzten Bits in der Ausgabe vermieden.

Vorbereitung 
Vor dem Kodieren oder Dekodieren müssen sich der Kodierer und der Dekodierer auf diese Dinge einigen:
 das Alphabet, aus dem die Zeichen der Zeichenfolge stammen
 die Reihenfolge der Zeichen im Alphabet
 die Auftrittswahrscheinlichkeiten der einzelnen Zeichen (gemäß dem Modell für die Entropiekodierung)
 das Intervall für das Ergebnis des Kodierers, üblicherweise , siehe

Kodieralgorithmus 

Der Kodierer bekommt als Eingabe:
 eine Folge von Zeichen
 eine Tabelle, die für jedes Zeichen die Auftrittswahrscheinlichkeit festlegt 

Er erzeugt daraus:
 eine rationale Zahl  im Bereich , die die Eingabezeichenfolge repräsentiert
 eine natürliche Zahl , die die Länge der Eingabezeichenfolge angibt

Ablauf:
 Das Zielintervall für  geht von der unteren Grenze  bis zur oberen Grenze , anfangs ist .
 Die Anzahl der eingelesenen Zeichen  beginnt mit .
 Für jedes Zeichen  aus der Eingabe:
 Erhöhe die Anzahl der eingelesenen Zeichen  um 1.
 Bestimme die Auftrittswahrscheinlichkeit  für das Zeichen  anhand der Wahrscheinlichkeitstabelle.
 Bestimme die Auftrittswahrscheinlichkeit  für alle Zeichen, die im Alphabet vor  kommen, indem die einzelnen Wahrscheinlichkeiten aufsummiert werden.
 Schränke das Zielintervall so ein, dass nur noch das Teilintervall, das zu  gehört, übrig bleibt:
 
 
 Wähle eine beliebige Zahl  aus dem Intervall , mit möglichst kurzer Schreibweise.

Beispiel 

Eingabe:
 Das Alphabet besteht aus den Zeichen A, B, C, in dieser Reihenfolge.
 Die Auftrittswahrscheinlichkeiten sind: .
 Die zu kodierende Zeichenfolge ist AAABAAAC.

Dekodieralgorithmus 

Der Dekodierer bekommt als Eingabe:
 eine rationale Zahl 
 die Länge  der ursprünglichen Eingabezeichenfolge

Ablauf:
 Wiederhole -mal:
 Bestimme das Zeichen , in dessen Teilintervall die Zahl  liegt, sowie die Grenzen  und  dieses Teilintervalls.
 Gib das Zeichen  aus.
 Transformiere die relative Position der Zahl  aus dem Intervall  ins Intervall , also .

Beispiel 

Der Dekodierer bekommt die Zahl  und die Anzahl der Zeichen  zum Dekodieren. Um zu einer Position im Intervall das zugehörige Zeichen zu bestimmen, wird die Tabelle vor dem eigentlichen Dekodieren berechnet:

Das Dekodieren passiert in diesen Schritten:
 Die Zahl  gehört zum Zeichen A, mit  und .
 Das neue  ergibt sich zu .
 Die Zahl  gehört zum Zeichen A, mit  und .
 Das neue  ergibt sich zu .
 Die Zahl  gehört zum Zeichen A, mit  und .
 Das neue  ergibt sich zu .
 Die Zahl  gehört zum Zeichen B, mit  und .
 Das neue  ergibt sich zu .
 Die Zahl  gehört zum Zeichen A, mit  und .
 … und so weiter, bis alle 8 Zeichen dekodiert sind.

Varianten 

Statt dem Dekodierer die Anzahl der kodierten Symbole  mitzuteilen, kann das Alphabet auch ein spezielles Zeichen mit der Bedeutung „Ende“ enthalten.

Es gibt auch Varianten der arithmetischen Kodierung für weniger Rechenaufwand, die statt eines Bruchs nur eine einzelne, beliebig lange natürliche Zahl zur Informationsdarstellung verwenden. Generell ist die arithmetische Kodierung rechenintensiver als Kodierungen, bei denen jedes kodierte Wort eine ganzzahlige Anzahl Bits hat.

Das Verfahren Context-Adaptive Binary Arithmetic Coding wird zum Komprimieren von Videodaten verwendet, das Eingabealphabet besteht aus den beiden Binärziffern 0 und 1, und die Auftrittswahrscheinlichkeit der Bits wird während der Kompression kontextabhängig angepasst.

Optimalität 
Arithmetisches Kodieren ist asymptotisch optimal:

Nachdem das letzte Symbol verarbeitet wurde, erhält man ein Intervall  mit

Das entspricht der Wahrscheinlichkeit, bei gegebenen Symbolwahrscheinlichkeiten , genau solch eine Sequenz zu erhalten.

Um nun binär einen Wert im Intervall  anzugeben, benötigt man

 mindestens  Bits, falls 
 höchstens jedoch  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

und

lässt sich die Länge  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  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:

Vergleich zur Huffman-Kodierung 
Wenn sich alle Symbolwahrscheinlichkeiten  in der Form  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 
Bei einer konkreten Umsetzung ergibt sich die Schwierigkeit, dass die Grenzen des Intervalls beliebig genaue Bruchzahlen sind. Da das Rechnen mit großen Zählern und Nennern entsprechend lange dauert, wird der Algorithmus für die praktische Umsetzung etwas abgewandelt.

Um das Problem der großen Zähler und Nenner Genauigkeit abzumildern, werden zwei Schritte unternommen:
 In der Tabelle mit den Auftrittswahrscheinlichkeiten wird eine Mindestgenauigkeit festgelegt, auf die einzelnen Auftrittswahrscheinlichkeiten gerundet werden. Durch dieses Runden stimmen die Intervallgrößen nicht mehr exakt mit den optimalen Wahrscheinlichkeiten überein. Das führt zu einer Verschlechterung der Kompressionsrate.
 Das Intervall muss ab und an wieder vergrößert werden, da sonst nach einigen kodierten Zeichen die Genauigkeit der Zahlen unverhältnismäßig groß wird. 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 ganzen Zahlen.
 Der Q-Coder (von IBM entwickelt und patentiert) Dieser Kodierer 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 Kodierer 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)
 Website des Range-Coders, Quellcode zum Download
 Das elektronische Buch Information Theory, Inference, and Learning Algorithms von David J. C. MacKay erklärt in Kapitel 6 das arithmetische Kodieren.

Einzelnachweise 

Datenkompression