Arithmetische Kodierung
Shortlinks
Allgemein
Die arithmetische Kodierung ist ein Verfahren der Entropiekodierung, das Kompressionsraten erziehlt, die sehr nahe am theoretischen Limit liegt. Die arithmetische Kodierung unterscheidet sich in einem wesentlichen Punkt von herkömmlichen Kodierungen, wie zum Beispiel im ASCII-Code oder der Huffman-Kodierung wo Zeichen mit Bitfolgen gespeichert werden. In der arithmetischen Kodierung hingegen wird die gesamte Quellinformation in Form einer rationalen Zahl dargestellt und nicht in einzelne Komponenten (Zeichen) aufgeteilt. Der Nachteil der arithmetischen Kodierung ist, dass sie generell rechenintensiver ist als die herkömmlichen Verfahren.
Die Quellinformation wird nach der arithmetischen Kodierung als Zahl 0.0 ≤ q < 1.0 abgespeichert, wobei so wenige Nachkommastellen wie möglich verwendet werden.
Konzept Kodierer
Intervalle
Meistens für die arithmetische Kodierung das Intervall {q ∈ ℝ | 0 ≤ x < 1} benutzt. Das Intervall wird in Subintervalle unterteilt, wobei jeweils ein Subintervall einem Zeichen zugeordnet ist und die Grösse des Subintervalles von der Auftrittswahrscheinlichkeit des Zeichens abhängt.
Die Subintervalle können dabei beliebig angeordnet werden, da dies für die Qualität des Algorithmus keine Rolle spielt. Deswegen wird auf dieser Seite eine alphabetische Reihenfolge gewählt.
Dies wird am Beispiel AABBACAA veranschaulicht. Die Auftrittswahrscheinlichkeiten betragen dabei.
Nun wird das Startintervall [0,1[ in drei Subintervalle unterteilt, deren Grösse jeweils der Auftrittswahrscheinlichkeit des Zeichens entsprechen.
Der erste Buchstabe der Zeichenkette AABBACAA, die hier kodiert wird ist ein A. Deswegen wird das Gesamtinvervall nun in das vorherige Subintervall des Zeichens A gesetzt (das Intervall [0,0.625[). Das Intervall wird wieder in die drei Subintervalle unterteilt, wobei deren Grösse gleich der Auftrittswahrscheinlichkeit multipliziert mit 0.625 (der Länge des Gesamtintervalls) ist.
Das nächste Zeichen ist wieder ein A, womit das ganze wieder in das vorgerige Subintervall von A gesetzt. Das Gesamtintervall, das wieder in drei Subintervalle unterteilt wird ist also nun [0,0.390625[.
Nun folgt ein B, womit das nächste Gesamtintervall dem vorherigen Gesamtintervall vom Zeichen B entspricht. Das neue Gesamtintervall ist also [0.244141,0.341797[.
Es kommt wieder ein B, das aufzuteilende Gesamtintervall ist also [0.305176,0.329590[.
In der Zeichenkette AABBACAA wurde jetzt bereits der Teil AABB umgesetzt. Der nächste Buchstabe ist also wieder ein A, womit das neue Gesamtintervall [0.305176,0.320435[ ist.
Weil als nächstes ein C vorkommt erhalten wir das wesentlich kleinere Gesamtintervall [0.318527,0.320435[.
Das nächste Gesamtintervall ist das letzte Subintervall von A: [0.318527,0.319719[.
Das letzte Zeichen ist wieder ein A, womit das letzte Gesamtintervall [0.318527,0.318993[ wird.
Gespeichert wird nun eine beliebige, möglichst kurze Zahl aus dem letzten Subintervall: [0.318527, 0.318993]. Diese Zahl ist jetzt der Code für die ganze Zeichenkette AABBACAA, es wurden also keine einzelnen Zeichen kodiert, sondern direkt die Gesamtinformation. Hier kann also beispielsweise die Zahl 0.3186 abgespeichert werden.
Aufgaben zur Kodierung
Kodiere die folgenden Strings mit der arithmetischen Kodierung. Gib jeweils den Anfang und das Ende des letzten Intervalls gerundet auf sechs Stellen nach dem Komma an.
| String | Code |
|---|---|
Konzept Dekodierer
Der Dekodierer erhält als Inputs die Auftrittswahrscheinlichkeiten der einzelnen Zeichen, sowie eine Zahl aus dem letzten Subintervall (die, die vom Kodierer abgespeichert wurde). Gleich wie beim Kodierer legt der Dekodierer das Startintervall [0, 1[ fest und teilt es an die Zeichen mit den zugehörigen Zeichen in alphabetischer Ordnung auf. Danach wird getestet, in welchem Subintervall die Inputzahl liegt. Das diesem Subintervall zugeordnete Zeichen ist also das nächste Zeichen der Information. Danach wird das nächste Intervall initialiesiert und es geht so weiter, bis die Information vollständig dekodiert wurde.
Hier werden wir das oben kodierte Beispiel wieder dekodieren, wir erhalten also folgende Inputs.
Wenn wir die Zeichen also wieder wie vorhin nach ihrer Auftrittswahrscheinlichkeit in alphapetischer Ordnung im Intervall [0, 1[ darstellen erhalten wir.
Die Zahl, die wir als Input erhalten haben: 0.3186 liegt im Subintervall [0, 0.625[. Demnach ist das erste Zeichen ein A. Nun wird das Intervall im Subintervall von A wieder erstellt.
Der Input liegt wieder im Subintervall des Zeichens A, womit auch das zweite Zeichen ein A ist. Das nächste Intervall ist nun.
Jetzt liegt der Input 0.3186 im Subintervall [0.2441, 0.3417[. Damit ist das dritte Zeichen ein B und das nächste Intervall wird im Subintervall von B initialisiert.
Das vierte Zeichen ist wieder ein B und das Intervall wird wieder neu initialisiert.
Beim fünften Zeichen handelt es sich wieder um ein A. Das nächste Intervall wird also wieder im Subintervall von A initialisiert.
Es folgt ein C und das Intervall wird wieder neu initialisiert.
Als siebtes Zeichen folgt ein A und das Intervall wird wieder neu initialisiert.
Das letzte Zeichen ist auch wieder ein A und damit erhalten wir insgesamt die Information AABBACAA.
Aufgaben zur Dekodierung
In diesen Aufgaben werden dir das erste Intervall, damit du daraus die Wahrscheinlichkeiten berechnen kannst und das letzte Subintervall, woraus du die Inputzahl herauslesen kannst gegeben. Finde damit den String heraus, der Kodiert wurde.
| String | Code |
|---|---|