Asymmetric Numeral Systems

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

ANS findet unter anderem Verwendung in den Kompressionsalgorithmen Zstandard^[2] und LZFSE,^[3] bei der Kompression der Bildformate PIK^[4] und JPEG XL.^[5]

Entropiekodierung

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 ${\displaystyle \lceil \log _{2}(1000)\rceil =10}$ Bits benötigt werden.

Die Anzahl von Kombinationen aus ${\displaystyle n}$ Symbolen mit ${\displaystyle pn}$ Einsen und ${\displaystyle (1-p)n}$ Nullen entspricht bei einer Wahrscheinlichkeit von ${\displaystyle p\in (0,1)}$ für Einsen nach der Stirlingformel näherungsweise

${\displaystyle {n \choose pn}\approx 2^{nh(p)}{\text{ für große }}n{\text{ und }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p).}$

Daher sind zur Speicherung einer solchen Sequenz ungefähr ${\displaystyle nh(p)}$ Bits erforderlich, wobei ${\displaystyle h(p)}$ der Entropie eines Symbols entspricht. Im Falle von ${\displaystyle p=1/2}$ sind also weiterhin ${\displaystyle n}$ Bits erforderlich, bei asymmetrischer Wahrscheinlichkeit allerdings weit weniger. Beispielsweise werden bei ${\displaystyle p=0{,}11}$ nur noch etwa ${\displaystyle n/2}$ 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

Die grundlegende Idee ist, Informationen in eine einzelne natürliche Zahl ${\displaystyle x}$ zu kodieren. Im üblichen Binärsystem kann ein Bit ${\displaystyle s\in \{0,1\}}$ an Information mithilfe der Kodierfunktion ${\displaystyle C(s,x)=2x+s}$ zu ${\displaystyle x}$ hinzugefügt werden, sodass ${\displaystyle x'=C(s,x)=2x+s}$. Durch Anwendung der Kodierfunktion verschieben sich alle Bits um eine Stelle und ${\displaystyle s}$ wird an der niedrigstwertigen Stelle ergänzt. Die Dekodierfunktion ${\displaystyle D(x')=((x'{\bmod {2}}),\lfloor x'/2\rfloor )}$ ermöglicht die Extraktion der vorherigen Zahl ${\displaystyle x}$ sowie des hinzugefügten Symbols ${\displaystyle s}$. 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 ${\displaystyle p_{0}=p_{1}=1/2}$. Dieser Prozess wird von ANS für beliebige Mengen von Symbolen ${\displaystyle s\in S}$ mit einer zugehörigen, oft asymmetrischen Wahrscheinlichkeitsverteilung ${\displaystyle (p_{s})_{s\in S}}$ generalisiert.

Nach dem Hinzufügen der Information von ${\displaystyle s}$ zu ${\displaystyle x}$ ist ${\displaystyle x'=C(s,x)\approx x/p_{s}}$ bzw. ${\displaystyle \log _{2}(x')=\log _{2}(C(s,x))\approx \log _{2}(x)+\log _{2}(1/p_{s})}$, wobei ${\displaystyle \log _{2}(x)}$ der Anzahl von Bits an Information in der Zahl ${\displaystyle x}$ und ${\displaystyle \log _{2}(1/p_{s})}$ der ungefähren Anzahl von Bits des Symbols ${\displaystyle s}$ entsprechen.

Varianten

Uniforme binäre Variante (uABS)

Die binäre Variante mit ungefähr gleichverteilten Symbolen ${\displaystyle s\in \{0,1\}}$ mit ${\displaystyle p_{1}=p}$ und ${\displaystyle p_{0}=1-p}$. Die Kodierfunktion ${\displaystyle C(s,x)}$ und die Dekodierfunktion ${\displaystyle D(x)}$ ergeben sich wie folgt:^[6]

${\displaystyle {\begin{aligned}C(s,x)&={\begin{cases}\left\lceil {\frac {x+1}{1-p}}\right\rceil &{\textrm {falls}}\ s=0\\\left\lfloor {\frac {x}{p}}\right\rfloor &{\textrm {falls}}\ s=1\end{cases}}\\D(x)&=(s,x_{s})\\s&=\lceil (x+1)p\rceil -\lceil xp\rceil \\x_{1}&=\lceil xp\rceil \\x_{0}&=x-x_{1}=x-\lceil xp\rceil \end{aligned}}}$

Range-Variante (rANS)

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 ${\displaystyle (p_{s})_{s\in S}}$ der Symbolmenge ${\displaystyle S=\{0,1,\dots ,n-1\}}$ wird näherungsweise durch Brüche der Form ${\displaystyle p_{s}\approx l_{s}/m}$ mit ${\displaystyle l_{s}\in \mathbb {N} }$ und ${\textstyle m=\sum _{s}l_{s}}$ beschrieben. Das Symbol ${\displaystyle s}$ dem Bereich ${\displaystyle \{b_{s},\dots ,b_{s+1}-1\}}$ mit ${\textstyle b_{s}=\sum _{i=0}^{s-1}}$ eines Stellenwertsystems zur Basis ${\displaystyle m}$ zugeordnet. Aus Position ${\displaystyle y}$ eines Symbols im Stellenwertsystem kann das Symbol durch ${\textstyle s(y)=\min \,\{s:y<\sum _{i=0}^{s}l_{i}\}}$ bestimmt werden. Die Kodierfunktion ${\displaystyle C(s,x)}$ und die Dekodierfunktion ${\displaystyle D(x)}$ ergeben sich wie folgt:^[6]

${\displaystyle {\begin{aligned}C(s,x)&=m\left\lfloor {\frac {x}{l_{s}}}\right\rfloor +b_{s}+(x{\bmod {l}}_{s})\\D(x)&=\left(s,l_{s}\left\lfloor {\frac {x}{m}}\right\rfloor +(x{\bmod {m}})-b_{s}\right)\;{\textrm {mit}}\ s=s(x{\bmod {m}})\end{aligned}}}$

Im Kodierer liegen üblicherweise ${\displaystyle l_{s}}$, ${\displaystyle b_{s}}$ und ${\displaystyle s(y)}$ tabellarisch vor, idealerweise auch ${\displaystyle l(y)=l_{s(y)}}$ und ${\displaystyle b(y)=b_{s(y)}}$, um eine bessere Laufzeit zu erzielen.

Wenn ${\displaystyle m}$ als Potenz von 2 gewählt wird, können die Multiplikationen und Divisionen durch schnellere bitweise Verschiebungen und ${\displaystyle x{\bmod {m}}}$ durch bitweises UND ersetzt werden. Dadurch ist bei der Dekodierung nur noch eine Multiplikation erforderlich.

Tabellarische Variante (tANS)

Die tabellarische Variante verpackt den gesamten Ablauf für ${\displaystyle x\in [L,2L-1]}$ in eine Tabelle, die einen endlichen Automaten beschreibt. Dadurch ist es möglich, gänzlich auf Multiplikationen zu verzichten.

Anmerkungen

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

• Microsoft bekommt Patent auf freies Kodierverfahren, golem.de, 18. Februar 2022

Einzelnachweise

1. 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).
2. Zstandard Compression Format. In: GitHub. Abgerufen am 23. Juni 2020 (englisch).
3. Sergio De Simone: Apple Open-Sources its New Compression Algorithm LZFSE. In: InfoQ. 2. Juli 2016, abgerufen am 24. Juni 2020 (englisch).
4. PIK. In: GitHub. Abgerufen am 24. Juni 2020 (englisch).
5. Alexander Rhatushnyak, Jan Wassenberg, Jon Sneyers, Jyrki Alakuijala, Lode Vandevenne: Committee Draft of JPEG XL Image Coding System. 13. August 2019, arxiv:1908.03565.Fehler in Vorlage:Literatur – *** Parameterproblem: Dateiformat/Größe/Abruf nur bei externem Link
6. Jarek Duda: Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. 6. Januar 2014, arxiv:1311.2540.Fehler in Vorlage:Literatur – *** Parameterproblem: Dateiformat/Größe/Abruf nur bei externem Link