WikiDer > Arithmetische Codierung
Arithmetische Codierung ist verlustfrei Kompressionsverfahren und eine Form von Entropiekodierung. Es ist eine Alternative zum Huffman-Codierung.
Prinzip
Es gibt zwei Methoden der arithmetischen Codierung: Gleitkommaausführung und mit ganze Zahlen
Gleitkomma-Beispiel
In diesem Beispiel wird der Text "AAABAAAC" komprimiert. Zunächst muss geprüft werden, wie oft jedes Zeichen vorkommt, damit die Teilintervalle berechnet werden können. Der Einfachheit halber wird für alle Zeichen eine feste Wahrscheinlichkeit verwendet.
| Schild | Prozentsatz | optimale Zahl Bits |
| p(A) | 75% | 0,415 |
| p(B) | 12,5% | 3 |
| p(C) | 12,5% | 3 |
Die optimale Bitzahl ergibt sich aus dem Entropie berechnen. Daraus folgt, dass die Summe Informationsdichte des Beispieltextes ist 8,49 Bit.
Die folgende Tabelle zeigt die genauen Teilintervalle nach der Kodierung der einzelnen Zeichen. Das Bild unten zeigt dies grafisch.
| Intervall | Intervallgröße | ||
| 0 - | 1 | 1 | |
| ein | 0 - | 0,75 | 0,75 |
| ein | 0 - | 0,5625 | 0,5625 |
| ein | 0 - | 0,421875 | 0,421875 |
| B | 0,31640625 - | 0,369140625 | 0,052734375 |
| ein | 0,31640625 - | 0,35595703125 | 0,03955078125 |
| ein | 0,31640625 - | 0,3460693359375 | 0,0296630859375 |
| ein | 0,31640625 - | 0,338653564453125 | 0,022247314453125 |
| C | 0,335872650146484375 - | 0,338653564453125 | 0,002780914306640625 |
Nun wird eine zufällige, aber möglichst kurze Zahl aus dem letzten Intervall gespeichert. Zum Beispiel 0,336.
Dies erfordert zwischen 8 und 9 Bit, um dies zu speichern. Im Gegensatz dazu würde die Verwendung der Huffman-Codierung 10 Bits erfordern (1 Bit für jedes A und 2 Bits für B und C).
In diesem Beispiel beträgt der Gewinn 10 %. Die Verstärkung erhöht das tatsächliche Auftreten eines Zeichens, wenn die Huffman-Codierung weiter vom optimalen Wert abweicht. Dies geschieht zum Beispiel, wenn ein Zeichen extrem häufig auftritt.
Die Zahl 0.336 kann auch wieder dekodiert werden.
- Das Startintervall [0; 1]. Der Decoder teilt diese in 3 Teile auf, wie im Bild zu sehen ist.
- 0,336 liegt im xub-Intervall A [0; 0,75). Daraus folgt, dass das erste Zeichen A ist.
- Das neue Teilintervall wird [0; 0,75]
- [0; 0,75] wird wieder in neue Teilintervalle unterteilt.
- 0,336 liegt im ersten Intervall [0; 0,5625]. Also ist auch das nächste Zeichen ein A.
- usw...
Integer-Version
Diese Methode basiert auf der Hardware-Sicht am zutreffendsten.
Das Prinzip der Encoder und Decoder basiert auf a Intervall die nach folgenden Eigenschaften in Teilintervalle unterteilt ist:
- Die Anzahl der Unterintervalle ist gleich der Anzahl unterschiedlicher zu codierender Zeichen.
- Pro Charakter Gibt es ein Teilintervall, dessen Größe proportional zum Auftreten dieses Zeichens ist.
Beim Codieren eines Zeichens wird das aktuelle Intervall auf ein Subintervall reduziert, das dem Subintervall dieses Zeichens entspricht. Dabei müssen die inneren Grenzen jedes Teilintervalls bezüglich der neuen Unter- und Obergrenzen neu bestimmt werden. Die untere und obere Grenze des neuen Intervalls werden nach jeder Iteration betrachtet.
Wenn die höchstwertigen Zahlen der unteren und oberen Grenze gleich sind, können sie nicht durch weitere Division geändert werden. Folglich gibt der Decoder diese Daten weiter, woraufhin die restlichen Ziffern nach links verschoben werden (mit Einfügen von Nullen an den freien Stellen). Die erste Ziffer der unteren und oberen Grenze ist dann gleich und wird an den Ausgang übergeben.
Danach werden alle Grenzen des Intervalls neu berechnet und somit das Intervall angepasst.