Arithmetisches Kodieren

Was ist arithmetisches Kodieren?

Die arithmetische Kodierung ist eine Form der Entropiekodierung und wird zur verlustfreien Datenkompression eingesetzt. Sie erreicht Kompressionsraten, die sehr nahe am theoretischen Limit der Entropie liegen. Als Begründer gilt Jorma Rissanen, der ab 1976 bis Anfang der 1980er Jahre wesentliche Beiträge leistete. Die Grundidee: Aus einer Folge von Eingabesymbolen und deren Auftrittswahrscheinlichkeiten wird eine einzelne, möglichst kurze rationale Zahl (Bruchzahl) gebildet, aus der sich die ursprüngliche Symbolfolge wiederherstellen lässt. Anders als Kodierungen, die die Eingabe in kurze Teile zerlegen und jedes Teil einzeln in Bits kodieren (wobei Bits unvollständig genutzt werden können), verrechnet die arithmetische Kodierung alle Zeichen gemeinsam zu einer Zahl und vermeidet so die unvollständig genutzten Bits.

Vorbereitung und Kodieralgorithmus

Vor dem Kodieren müssen Kodierer und Dekodierer sich einigen auf: das Alphabet und die Reihenfolge der Zeichen, die Auftrittswahrscheinlichkeiten der Zeichen (gemäß dem Modell für die Entropiekodierung) und das Intervall für das Ergebnis, üblicherweise 0 ≤ q < 1. Der Kodierer erhält als Eingabe eine Zeichenfolge und eine Wahrscheinlichkeitstabelle; er erzeugt eine rationale Zahl q mit 0 ≤ q < 1 und die Länge n der Eingabefolge. Ablauf: Start mit u := 0, o := 1 (untere/obere Intervallgrenze) und n := 0. Für jedes Zeichen z: n erhöhen, die Wahrscheinlichkeit p_z für z aus der Tabelle bestimmen, die Summe p_v der Wahrscheinlichkeiten aller im Alphabet vor z liegenden Zeichen berechnen, und das Intervall einschränken auf: u_neu := u + p_v · (o − u) sowie o_neu := u + (p_v + p_z) · (o − u). Am Ende wählt man aus dem Intervall u ≤ q < o eine Zahl mit möglichst kurzer Schreibweise.

Beispiel

Alphabet: A, B, C mit Wahrscheinlichkeiten p_A = 6/8, p_B = 1/8, p_C = 1/8. Zu kodieren: AAABAAAC. Start: u = 0, o = 1. Beim ersten A (p_v = 0/8) wird das Intervall [0/8, 6/8]. Nach drei A liegt es bei [0/8³, 216/8³]. Beim B (p_v = 6/8, p_B = 1/8) ergibt sich [1296/8⁴, 1512/8⁴] – das Intervall beginnt jetzt nicht mehr bei 0. Nach drei weiteren A und dem letzten C liegt das Ergebnisintervall bei 5635008/8⁸ ≤ q < 5681664/8⁸. Gewählt wird q = 43/128 – der kürzeste Bruch im Intervall mit Zweierpotenz als Nenner, weil sich so q einfach im Binärsystem kodieren lässt.

Dekodieralgorithmus

Der Dekodierer erhält die rationale Zahl q und die Länge n der ursprünglichen Zeichenfolge. Er wiederholt n-mal: Er bestimmt das Zeichen z, in dessen Teilintervall q liegt (mit den Grenzen u_z und o_z des Teilintervalls), gibt z aus und rechnet die relative Position von q in das Standardintervall 0 ≤ q < 1 um: q := (q − u_z) / (o_z − u_z). Beispiel: Für q = 43/128 und n = 8 legt man zuerst die Intervalltabelle an: A [0/8, 6/8), B [6/8, 7/8), C [7/8, 8/8). Die 43/128 liegt im Intervall von A; das neue q wird 43/96, dann 43/72, dann 43/54 – dieses liegt im B-Intervall, das neue q wird 10/27, dann wieder A usw., bis alle 8 Zeichen dekodiert sind. Statt n mitzuteilen kann das Alphabet auch ein besonderes „Ende“-Zeichen enthalten.

Optimalität und Vergleich zur Huffman-Kodierung

Arithmetisches Kodieren ist asymptotisch optimal. Nach dem letzten Symbol erhält man ein Intervall [r, r + s) mit s = ∏ p(x_i), also der Wahrscheinlichkeit, genau diese Sequenz zu erhalten. Um binär einen Wert darin anzugeben, braucht man mindestens −log₂(s) Bits (in einem günstigen Fall) und höchstens −⌈log₂(s)⌉ + 1 Bits. Da −log₂(s) = −Σ log₂ p(x_i) = n·H(X) mit der Entropie H(X) und n Symbolen, gilt für die Länge l der kodierten Sequenz: n·H(X) ≤ l < n·H(X) + 2 – also mindestens so viele Bits wie die Entropie, höchstens zwei Bits mehr. Die mittlere Länge pro Symbol l_Sym = l/n ist auf H(X) ≤ l_Sym < H(X) + 2/n beschränkt; für lange Sequenzen geht sie asymptotisch gegen die Entropie. Vergleiche zur Huffman-Kodierung: Lassen sich alle Wahrscheinlichkeiten als p_i = 2^(−k_i) mit natürlichen k_i schreiben, erzeugen beide Verfahren einen identisch langen Datenstrom und sind gleich effizient – in der Praxis ist das aber so gut wie nie der Fall.

Implementierung und Varianten

In der Praxis sind die Intervallgrenzen Brüche mit beliebig genauer Genauigkeit; große Zähler und Nenner sind langsam zu berechnen. Zwei Gegenmaßnahmen: 1) Die Wahrscheinlichkeiten werden auf eine Mindestgenauigkeit gerundet – das verschlechtert leicht die Kompressionsrate; streng genommen ist der Algorithmus dann nicht mehr exakt ein arithmetischer Kodierer. 2) Das Intervall wird gelegentlich vergrößert, indem feststehende höherwertige Stellen ausgegeben und von den Grenzen abgezogen werden; danach skaliert man mit 10 weiter (Beispiel: nach dem B ist sicher, dass das Ergebnis mit 0,3 beginnt). Bekannte Abkömmlinge: der Range-Coder (direkte Umsetzung mit ganzen Zahlen), der Q-Coder (IBM, patentiert; reduziert das Alphabet auf zwei Zeichen, Intervallaufteilung näherungsweise durch Additionen statt Multiplikationen) und der ELS-Coder (ebenfalls zwei Zeichen, effizienter bei etwa gleich wahrscheinlichen Zeichen). Probleme: Geschwindigkeit (Range-Coder braucht pro Zeichen eine Division; die anderen kodieren jedes Bit mehrfach), Patente (meist erteilt in den 1980ern/frühen 1990ern, inzwischen ausgelaufen; der Q-Coder ist für JPEG zulässig, wird aber wegen der IBM-Patentierung kaum genutzt) und nur kleiner Gewinn, da die schnellere Huffman-Kodierung mit Tricks wie dem Behandeln von Zeichenketten als eigenständige Zeichen nur unwesentlich schlechtere Ergebnisse liefert. Eine weitere Variante ist Context-Adaptive Binary Arithmetic Coding (CABAC) für Videokompression: Alphabet nur 0 und 1, die Wahrscheinlichkeit der Bits wird während der Kompression kontextabhängig angepasst. Generell ist arithmetische Kodierung rechenintensiver als Kodierungen mit ganzzahliger Bitlänge pro Wort.