Asymmetric Numeral Systems (ANS, asymmetrische Zahlensysteme) sind eine Familie von Entropiekodierungen, die von Jarosław „Jarek“ Duda an der Jagiellonen-Universität entwickelt wurden. ANS kombiniert die Kompressionsrate der arithmetischen Kodierung, die eine nahezu exakte Wahrscheinlichkeitsverteilung nutzt, mit einem zur Huffman-Kodierung vergleichbaren Rechenaufwand.
ANS findet unter anderem Verwendung in den Kompressionsalgorithmen Zstandard und LZFSE, bei der Kompression der Bildformate PIK und JPEG XL.
Entropiekodierung Bearbeiten
Die Sequenz von 1000 Nullen und Einsen würde bei direkter Speicherung 1000 Bits umfassen. Wenn über die Sequenz bekannt ist, dass sie nur eine Eins und 999 Nullen enthält, ist es ausreichend, nur die Stelle der Eins zu speichern, wodurch nur noch Bits benötigt werden.
Die Anzahl von Kombinationen aus Symbolen mit Einsen und Nullen entspricht bei einer Wahrscheinlichkeit von für Einsen nach der Stirlingformel näherungsweise
Daher sind zur Speicherung einer solchen Sequenz ungefähr Bits erforderlich, wobei der Entropie eines Symbols entspricht. Im Falle von sind also weiterhin Bits erforderlich, bei asymmetrischer Wahrscheinlichkeit allerdings weit weniger. Beispielsweise werden bei nur noch etwa Bits benötigt.
Ein Entropiekodierer ermöglicht die Kodierung einer Symbolfolge mit einer ungefähr der Entropie entsprechenden Anzahl von Bits pro Symbol.
Grundkonzept von ANS Bearbeiten
Die grundlegende Idee ist, Informationen in eine einzelne natürliche Zahl zu kodieren. Im üblichen Binärsystem kann ein Bit an Information mithilfe der Kodierfunktion zu hinzugefügt werden, sodass . Durch Anwendung der Kodierfunktion verschieben sich alle Bits um eine Stelle und wird an der niedrigstwertigen Stelle ergänzt. Die Dekodierfunktion ermöglicht die Extraktion der vorherigen Zahl sowie des hinzugefügten Symbols . Durch mehrfache Anwendung der Kodierfunktion kann eine Sequenz kodiert und durch mehrfache Anwendung der Dekodierfunktion in umgekehrter Reihenfolge wieder dekodiert werden.
Das beschriebene Vorgehen ist optimal, wenn die Wahrscheinlichkeitsverteilung der beiden möglichen Symbole symmetrisch ist, also . Dieser Prozess wird von ANS für beliebige Mengen von Symbolen mit einer zugehörigen, oft asymmetrischen Wahrscheinlichkeitsverteilung generalisiert.
Nach dem Hinzufügen der Information von zu ist bzw. , wobei der Anzahl von Bits an Information in der Zahl und der ungefähren Anzahl von Bits des Symbols entsprechen.
Uniforme binäre Variante (uABS) Bearbeiten
Die binäre Variante mit ungefähr gleichverteilten Symbolen mit und . Die Kodierfunktion und die Dekodierfunktion ergeben sich wie folgt:
Range-Variante (rANS) Bearbeiten
Die Range-Variante benutzt ebenfalls arithmetische Formeln, erlaubt aber im Gegensatz zu uABS ein größeres Alphabet. Es kann als Modifikation eines Stellenwertsystems gesehen werden, bei dem manche aufeinanderfolgenden Ziffern zu Bereichen vereinigt wurden.
Die Wahrscheinlichkeitsverteilung der Symbolmenge wird näherungsweise durch Brüche der Form mit und beschrieben. Das Symbol dem Bereich mit eines Stellenwertsystems zur Basis zugeordnet. Aus Position eines Symbols im Stellenwertsystem kann das Symbol durch bestimmt werden. Die Kodierfunktion und die Dekodierfunktion ergeben sich wie folgt:
Im Kodierer liegen üblicherweise , und tabellarisch vor, idealerweise auch und , um eine bessere Laufzeit zu erzielen.
Wenn als Potenz von 2 gewählt wird, können die Multiplikationen und Divisionen durch schnellere bitweise Verschiebungen und durch bitweises UND ersetzt werden. Dadurch ist bei der Dekodierung nur noch eine Multiplikation erforderlich.
Tabellarische Variante (tANS) Bearbeiten
Die tabellarische Variante verpackt den gesamten Ablauf für in eine Tabelle, die einen endlichen Automaten beschreibt. Dadurch ist es möglich, gänzlich auf Multiplikationen zu verzichten.
Anmerkungen Bearbeiten
Wie bei der Huffman-Kodierung ist die Veränderung der Wahrscheinlichkeitsverteilung von tANS relativ teuer, weshalb es hauptsächlich in statischen Anwendungsszenarien verwendet wird.
Im Gegensatz dazu stellt rANS eine schnellere Alternative zur Bereichskodierung dar. Es benötigt Multiplikationen, ist aber speichereffizienter und eignet sich für dynamisch adaptierte Wahrscheinlichkeitsverteilungen.
Das Kodieren und Dekodieren von ANS erfolgt in entgegengesetzte Richtung. Die Dekodierung verläuft in den kodierten Daten von hinten nach vorn. Damit bei der Dekodierung auf einen Stack verzichtet werden kann, wird in der Praxis oft rückwärts kodiert.
Weblinks Bearbeiten
- Microsoft bekommt Patent auf freies Kodierverfahren, golem.de, 18. Februar 2022
Einzelnachweise Bearbeiten
- Timothy B. Lee: Inventor says Google is patenting work he put in the public domain. In: Ars Technica. 10. Juni 2018, abgerufen am 24. Juni 2020 (englisch).
- Zstandard Compression Format. In: GitHub. Abgerufen am 23. Juni 2020 (englisch).
- Sergio De Simone: Apple Open-Sources its New Compression Algorithm LZFSE. In: InfoQ. 2. Juli 2016, abgerufen am 24. Juni 2020 (englisch).
- PIK. In: GitHub. Abgerufen am 24. Juni 2020 (englisch).
- Alexander Rhatushnyak, Jan Wassenberg, Jon Sneyers, Jyrki Alakuijala, Lode Vandevenne: Committee Draft of JPEG XL Image Coding System. 13. August 2019, arxiv:1908.03565.
- ↑ Jarek Duda: Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. 6. Januar 2014, arxiv:1311.2540.