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.^[1]

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 $0\leq q<1$ , siehe ^[2]

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 $q$ im Bereich $0\leq q<1$ , die die Eingabezeichenfolge repräsentiert
eine natürliche Zahl $n$ , die die Länge der Eingabezeichenfolge angibt

Ablauf:

Das Zielintervall für $q$ geht von der unteren Grenze $u$ bis zur oberen Grenze $o$ , anfangs ist $u:=0,o:=1$ .
Die Anzahl der eingelesenen Zeichen $n$ beginnt mit $n:=0$ .
Für jedes Zeichen $z$ aus der Eingabe:
1. Erhöhe die Anzahl der eingelesenen Zeichen $n$ um 1.
2. Bestimme die Auftrittswahrscheinlichkeit $p_{z}$ für das Zeichen $z$ anhand der Wahrscheinlichkeitstabelle.
3. Bestimme die Auftrittswahrscheinlichkeit $p_{v}$ für alle Zeichen, die im Alphabet vor $z$ kommen, indem die einzelnen Wahrscheinlichkeiten aufsummiert werden.
4. Schränke das Zielintervall so ein, dass nur noch das Teilintervall, das zu $z$ gehört, übrig bleibt:
  - $u_{neu}:=u+p_{v}\cdot (o-u)$
  - $o_{neu}:=u+(p_{v}+p_{z})\cdot (o-u)$
Wähle eine beliebige Zahl $q$ aus dem Intervall $u\leq q<o$ , 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: $p_{A}={\frac {6}{8}},p_{B}={\frac {1}{8}},p_{C}={\frac {1}{8}}$ .
Die zu kodierende Zeichenfolge ist AAABAAAC.

Ablauf
Schritt	Aktion	Anmerkungen
1	$u:=0,o:=1$	Das Zielintervall geht von 0 bis 1.
2	$n:=0$	Es wurden noch keine Zeichen gelesen.
3	$z:={\textrm {'A'}}$	Das erste Zeichen der Zeichenfolge ist ein A.
3.1	$n:=0+1=1$	Das erste Zeichen wurde gelesen.
3.2	$p_{z}:={\dfrac {6}{8}}$	Die Wahrscheinlichkeit $p_{A}$ für das A.
3.3	$p_{v}:={\dfrac {0}{8}}$	In dem Alphabet gibt es keine Zeichen vor dem A.
3.4	${\begin{array}{llll}u&:={\dfrac {0}{8}}+\left(0{\phantom {{}+{\dfrac {6}{8}}}}\right)\cdot 1&={\dfrac {0}{8}}\\o&:={\dfrac {0}{8}}+\left(0+{\dfrac {6}{8}}\right)\cdot 1&={\dfrac {6}{8}}\\\end{array}}$
3 bis 3.3	$z:={\textrm {'A'}};\;n:=2;\;p_{z}:={\frac {6}{8}};\;p_{v}:={\dfrac {0}{8}}$	das zweite Zeichen der Zeichenfolge ist ebenfalls A
3.4	${\begin{array}{lllll}u&:={\dfrac {0}{8}}&+\left({\dfrac {0}{8}}{\phantom {{}+{\dfrac {6}{8}}}}\right)\cdot {\dfrac {6}{8}}&={\dfrac {0}{8^{2}}}\\o&:={\dfrac {0}{8}}&+\left({\dfrac {0}{8}}+{\dfrac {6}{8}}\right)\cdot {\dfrac {6}{8}}&={\dfrac {36}{8^{2}}}\\\end{array}}$
3 bis 3.3	$z:={\textrm {'A'}};\;n:=3;\;p_{z}:={\dfrac {6}{8}};\;p_{v}:={\dfrac {0}{8}}$
3.4	${\begin{array}{llll}u&:={\dfrac {0}{8^{2}}}+\left({\dfrac {0}{8}}{\phantom {{}+{\dfrac {6}{8}}}}\right)\cdot {\dfrac {36}{8^{2}}}&={\dfrac {0}{8^{3}}}\\o&:={\dfrac {0}{8^{2}}}+\left({\dfrac {0}{8}}+{\dfrac {6}{8}}\right)\cdot {\dfrac {36}{8^{2}}}&={\dfrac {216}{8^{3}}}\\\end{array}}$
3 bis 3.3	$z:={\textrm {'B'}};\;n:=4;\;p_{z}:={\dfrac {1}{8}};\;p_{v}:={\dfrac {6}{8}}$	das vierte Zeichen der Eingabefolge ist ein B
3.4	${\begin{array}{llll}u&:={\dfrac {0}{8^{3}}}+\left({\dfrac {6}{8}}{\phantom {{}+{\dfrac {1}{8}}}}\right)\cdot {\dfrac {216}{8^{3}}}&={\dfrac {1296}{8^{4}}}\\o&:={\dfrac {0}{8^{3}}}+\left({\dfrac {6}{8}}+{\dfrac {1}{8}}\right)\cdot {\dfrac {216}{8^{3}}}&={\dfrac {1512}{8^{4}}}\\\end{array}}$	das Intervall beginnt jetzt nicht mehr bei 0
…	…	3 weitere A werden eingelesen und verrechnet
3 bis 3.3	$z:={\textrm {'C'}};\;n:=8;\;p_{z}:={\dfrac {1}{8}};\;p_{v}:={\dfrac {7}{8}}$	das letzte Zeichen ist ein C
3.4	${\begin{array}{llll}u&:={\dfrac {663552}{8^{7}}}+\left({\dfrac {7}{8}}{\phantom {{}+{\dfrac {1}{8}}}}\right)\cdot {\dfrac {46656}{8^{7}}}&={\dfrac {5635008}{8^{8}}}\\o&:={\dfrac {663552}{8^{7}}}+\left({\dfrac {7}{8}}+{\dfrac {1}{8}}\right)\cdot {\dfrac {46656}{8^{7}}}&={\dfrac {5681664}{8^{8}}}\\\end{array}}$	Die gesuchte Zahl $q$ liegt im Bereich ${\dfrac {5635008}{8^{8}}}\leq q<{\dfrac {5681664}{8^{8}}}$ .
4	$q:={\dfrac {43}{128}}$	Dies ist der kürzeste Bruch im gesuchten Intervall, dessen Nenner eine Zweierpotenz ist. Die Zweierpotenz bietet sich an, um die Zahl $q$ im Binärsystem zu kodieren.

Dekodieralgorithmus

Der Dekodierer bekommt als Eingabe:

eine rationale Zahl $q$
die Länge $n$ der ursprünglichen Eingabezeichenfolge

Ablauf:

Wiederhole $n$ -mal:
1. Bestimme das Zeichen $z$ , in dessen Teilintervall die Zahl $q$ liegt, sowie die Grenzen $u_{z}$ und $o_{z}$ dieses Teilintervalls.
2. Gib das Zeichen $z$ aus.
3. Transformiere die relative Position der Zahl $q$ aus dem Intervall $u_{z}\leq q<o_{z}$ ins Intervall $0\leq q<1$ , also $q:={\frac {q-u_{z}}{o_{z}-u_{z}}}$ .

Beispiel

Der Dekodierer bekommt die Zahl $q={\dfrac {43}{128}}$ und die Anzahl der Zeichen $n=8$ 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	${\dfrac {0}{8}}$	${\dfrac {6}{8}}$	${\dfrac {6}{8}}$
B	${\dfrac {6}{8}}$	${\dfrac {7}{8}}$	${\dfrac {1}{8}}$
C	${\dfrac {7}{8}}$	${\dfrac {8}{8}}$	${\dfrac {1}{8}}$

Das Dekodieren passiert in diesen Schritten:

Die Zahl ${\dfrac {43}{128}}$ gehört zum Zeichen A, mit $u={\dfrac {0}{8}}$ und $o={\dfrac {6}{8}}$ .
Das neue $q$ ergibt sich zu ${\dfrac {{\frac {43}{128}}-{\frac {0}{8}}}{{\frac {6}{8}}-{\frac {0}{8}}}}={\dfrac {43}{96}}$ .
Die Zahl ${\dfrac {43}{96}}$ gehört zum Zeichen A, mit $u={\dfrac {0}{8}}$ und $o={\dfrac {6}{8}}$ .
Das neue $q$ ergibt sich zu ${\dfrac {{\dfrac {43}{96}}-{\frac {0}{8}}}{{\frac {6}{8}}-{\frac {0}{8}}}}={\dfrac {43}{72}}$ .
Die Zahl ${\dfrac {43}{72}}$ gehört zum Zeichen A, mit $u={\dfrac {0}{8}}$ und $o={\dfrac {6}{8}}$ .
Das neue $q$ ergibt sich zu ${\dfrac {{\dfrac {43}{72}}-{\frac {0}{8}}}{{\frac {6}{8}}-{\frac {0}{8}}}}={\dfrac {43}{54}}$ .
Die Zahl ${\dfrac {43}{54}}$ gehört zum Zeichen B, mit $u={\dfrac {6}{8}}$ und $o={\dfrac {7}{8}}$ .
Das neue $q$ ergibt sich zu ${\dfrac {{\dfrac {43}{54}}-{\frac {6}{8}}}{{\frac {7}{8}}-{\frac {6}{8}}}}={\dfrac {10}{27}}$ .
Die Zahl ${\dfrac {10}{27}}$ gehört zum Zeichen A, mit $u={\dfrac {0}{8}}$ und $o={\dfrac {6}{8}}$ .
… und so weiter, bis alle 8 Zeichen dekodiert sind.

Varianten

Statt dem Dekodierer die Anzahl der kodierten Symbole $n$ 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.^[3]

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^[4]:

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\in [r,r+s)\mathrel {|} x=0\mathbin {\textrm {mod}} 2^{-\lceil \log _{2}(s)\rceil }$
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

lässt sich 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^[5]:

\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,^[6] 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

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

[riss76-1] Jorma Rissanen: Generalized Kraft inequality and arithmetic coding. Hrsg.: IBM Journal of Research and Development. Nr. 20. IBM (Firmenschrift), 1976, S. 198–203.

[Strutz-2] Strutz: Bilddatenkompression. SpringerVieweg, 2009

[Khal1-3] Khalid Sayood: Introduction to Data Compression. Morgan Kaufmann, 2000, ISBN 978-1-55860-558-9, Chapter 4: Arithmetic Coding.

[Blelloch10-4] Guy E. Blelloch, Introduction to Data Compression (PDF; 408 kB), S. 18, 2010

[Amir04-5] Amir Said, Introduction to Arithmetic Coding - Theory and Practice (PDF; 462 kB), S. 13

[Bodden02-6] E. Bodden et al., Ausarbeitung zu Grundlagen der arithmetischen Kodierung, einschließlich Quelltext (PDF; 581 kB), 2002, S. 41

[1]

[2]

[3]

[4]

[5]

[6]