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:

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

Beispiel

Intervallschachtelung beim Arithmetischen Kodieren

Eingabe:

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

Ablauf

Schritt	Aktion	Anmerkungen
1		Das Zielintervall geht von 0 bis 1.
2		Es wurden noch keine Zeichen gelesen.
3		Das erste Zeichen der Zeichenfolge ist ein A.
3.1		Das erste Zeichen wurde gelesen.
3.2		Die Wahrscheinlichkeit für das A.
3.3		In dem Alphabet gibt es keine Zeichen vor dem A.
3.4
3 bis 3.3		das zweite Zeichen der Zeichenfolge ist ebenfalls A
3.4
3 bis 3.3
3.4
3 bis 3.3		das vierte Zeichen der Eingabefolge ist ein B
3.4		das Intervall beginnt jetzt nicht mehr bei 0
…	…	3 weitere A werden eingelesen und verrechnet
3 bis 3.3		das letzte Zeichen ist ein C
3.4		Die gesuchte Zahl liegt im Bereich .
4		Dies ist der kürzeste Bruch im gesuchten Intervall, dessen Nenner eine Zweierpotenz ist. Die Zweierpotenz bietet sich an, um die Zahl im Binärsystem zu kodieren.

Dekodieralgorithmus

Der Dekodierer bekommt als Eingabe:

• eine rationale Zahl
• die Länge der ursprünglichen Eingabezeichenfolge

Ablauf:

1. Wiederhole -mal:
   1. Bestimme das Zeichen , in dessen Teilintervall die Zahl liegt, sowie die Grenzen und dieses Teilintervalls.
   2. Gib das Zeichen aus.
   3. 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:

Zeichen und ihre zugehörigen Intervalle

Zeichen	Untergrenze	Obergrenze	Breite
A
B
C

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:

1. 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.
2. 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:

Trotz dieser Verfahren bleiben verschiedene Probleme mit der Arithmetischen Kodierung:

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

1. Jorma Rissanen: Generalized Kraft inequality and arithmetic coding. Hrsg.: IBM Journal of Research and Development. Nr. 20. IBM (Firmenschrift), 1976, S. 198–203. 
2. Strutz: Bilddatenkompression. SpringerVieweg, 2009
3. Khalid Sayood: Introduction to Data Compression. Morgan Kaufmann, 2000, ISBN 978-1-55860-558-9, Chapter 4: Arithmetic Coding. 
4. Guy E. Blelloch, Introduction to Data Compression (PDF; 408 kB), S. 18, 2010
5. Amir Said, Introduction to Arithmetic Coding - Theory and Practice (PDF; 462 kB), S. 13
6. E. Bodden, et al., Ausarbeitung zu Grundlagen der arithmetischen Kodierung, einschließlich Quelltext (PDF; 581 kB), 2002, S. 41