Asymmetric Numeral Systems

Asymmetric Numeral Systems (asymetryczne systemy liczbowe, ANS) – rodzina kodowań entropijnych wprowadzonych przez dr. Jarosława Dudę na przestrzeni lat 2006–2014, używanych w kompresji danych od 2014 roku z powodu poprawionej wydajności w porównaniu z używanymi dotychczas metodami: ANS pozwala połączyć stopień kompresji kodowania arytmetycznego (używa praktycznie dokładnych prawdopodobieństw), z kosztem przetwarzania podobnym jak w kodowaniu Huffmana (przybliżającym prawdopodobieństwa potęgami 1/2). W wariancie tANS jest to osiągnięte przez skonstruowanie automatu skończonego w celu przetwarzania dużego alfabetu bez użycia mnożenia.

ANS jest m.in. użyte w kompresorze Zstandard z Facebook (także używany m.in. w jądrze systemu Linux, przeglądarce Google Chrome, Android, został opublikowany jako RFC 8478 ↓ dla MIME i HTTP), w kompresorze LZFSE z Apple, kompresorze 3D Draco i obrazu PIK z Google, kompresorze DNA CRAM z SAMtools, bibliotece do szybkiej kompresji Nvidia nvCOMP, kompresorze DivANS z Dropbox, Microsoft BCPack kompresji tekstur (komponent DirectX), oraz w standardzie kompresji obrazu JPEG XL.

Podstawową koncepcją ANS jest zapisanie informacji w pojedynczej liczbie naturalnej $x.$ W standardowym systemie liczbowym możemy dodać bit informacji $s\in \{0,1\}$ do informacji już zawartej w liczbie $x$ poprzez wstawienie go na ostatniej pozycji, prowadząc do liczby $x'=2x+s.$ Dla kodowania entropijnego jest to optymalne o ile $\Pr(0)=\Pr(1)=1/2.$ ANS uogólnia ten proces do dowolnego zestawu symboli $s\in S$ z założonym rozkładem prawdopodobieństwa $(p_{s})_{s\in S}.$ Nowa liczba $x'$ jest rezultatem dodania informacji z $s$ do liczby $x$ używając przybliżonej zależności: $x'\approx x/p_{s}.$ Równoważnie: $\log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s}),$ gdzie $\log _{2}(x)$ jest ilością bitów informacji zapisanych w liczbie $x$ oraz $\log _{2}(1/p_{s})$ jest ilością bitów zawartą w symbolu $s.$

Reguła kodowania jest ustalana poprzez podział zbioru liczb naturalnych na rozłączne podzbiory odpowiadające poszczególnym symbolom – jak na liczby parzyste i nieparzyste, ale tym razem z gęstościami odpowiadającymi założonemu rozkładowi prawdopodobieństwa symboli. Żeby dodać informację z symbolu $s$ do informacji już zapisanej w aktualnej liczbie $x,$ przechodzimy do liczby $x'=C(x,s)\approx x/p$ będącej $x$-tym wystąpieniem z $s$-tego podzbioru.

Kilka różnych sposobów jest wykorzystywanych, żeby użyć ANS w praktyce – bezpośrednie formuły matematyczne dla kroku kodowania i dekodowania (warianty uABS i rANS), lub można w całości stablicować zachowanie (wariant tANS). Żeby zapobiec ucieczce $x$ do nieskończoności, używana jest renormalizacja – przesłanie najmłodszych bitów do lub ze strumienia.

Wariant uANS (uniform binary)

Dla dwuelementowego alfabetu oraz rozkładu prawdopodobieństwa $\Pr(1)=p,\Pr(0)=1-p$ możemy użyć wariantu uABS, który dokonuje podziału zbioru liczb naturalnych prawie jednorodnie z powyższymi gęstościami. Do pozycji $x$ chcemy mniej więcej $p\cdot x$ wystąpień odpowiedników liczb nieparzystych (dla $s=1$). Możemy wybrać tę liczbę jako $\lceil x\cdot p\rceil ,$ dostając $s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil .$ Ostatecznie dostajemy poniższe funkcje dla kroku kodowania/dekodowania.

Krok dekodowania uABS:

s = ceil((x+1)*p) - ceil(x*p) // 0 if fract(x*p) < 1-p, else 1
if s = 0 then x = x - ceil(x*p)
if s = 1 then x = ceil(x*p)

Krok kodowania uABS:

if s = 0 then x = ceil((x+1)/(1-p)) - 1
if s = 1 then x = floor(x/p)

Dla $p=1/2$ dostajemy standardowy system dwójkowy (z zamienionymi 0 i 1). Dla innych $p$ staje się on zoptymalizowany dla danego rozkładu prawdopodobieństwa. Na przykład dla $p=0.3$ powyższe formuły prowadzą do tabelki dla małych wartości $x{:}$

$C(x,s)$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$s=0$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
$s=1$	0			1			2				3			4			5				6

Symbol $s=1$ odpowiada podzbiorowi liczb naturalnych o gęstości $p=0.3,$ które w powyższej tabelce są pozycjami $\{0,3,6,10,13,16,20,23,26,\dots \}.$ Jako że $1/4<0.3<1/3,$ te pozycje zwiększają się o 3 lub 4. Ponieważ tutaj $p=3/10,$ wzorzec symboli powtarza się co 10 pozycji.

Wartość $C(x,s)$ dostajemy biorąc wiersz odpowiadający danemu symbolowi $s,$ z którego wybieramy zadane $x.$ Wtedy wartość w górnym wierszu daje $C(x,s).$ Na przykład $C(7,0)=11,$ przechodząc od środkowego do górnego wiersza.

Wyobraźmy sobie kodowanie sekwencji '0100' zaczynając od $x=1.$ Najpierw $s=0$ prowadzi do $x=2,$ potem $s=1$ do $x=6,$ potem $s=0$ do $x=9,$ a na końcu $s=0$ do $x=14.$ Używając funkcji dekodującej $D(x')$ na tym ostatnim $x,$ możemy odtworzyć zakodowaną sekwencję symboli w odwrotnej kolejności. Żeby użyć powyższej tabelki w tym celu, $x'$ w pierwszym wierszu determinuje kolumnę, dla której niepusta wartość poniżej określa $s$ i $x.$

W zwykłym systemie dwójkowym: używając reguły $x'=2x+s,$ dla powyższego ciągu symboli przeszlibyśmy przez odpowiednio $x=1,2,5,10,20.$ Czyli zakodowalibyśmy ten ciąg w liczbie $x=20,$ która jest bardziej kosztowna do zapisania niż $x=14$ (otrzymane dla uABS) ze względu na gorsze zoptymalizowanie dla rozkładu prawdopodobieństwa kodowanego ciągu.

Wariant przedziałowy (rANS: range ANS) i strumieniowanie

Wariant rANS także używa formuł arytmetycznych, ale pozwala na bezpośrednie operowanie na dowolnie dużym alfabecie. Dzieli on zbiór liczb naturalnych na przedziały o długościach $2^{n},$ dalej każdy z nich w identyczny sposób dzieli na podprzedziały o założonych proporcjach.

Zaczynamy od kwantyzacji rozkładu prawdopodobieństwa do ułamków o mianowniku $2^{n},$ gdzie $n$ jest wybrane (zwykle 8-12 bitów): $p_{s}\approx f[s]/2^{n}$ dla pewnych liczb naturalnych $f[s]>0$ (wielkości podprzedziałów).

Oznaczmy ${\text{mask}}=2^{n}-1,$ dystrybuantę: $\operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\ldots +f[s-1].$

Dla $y\in [0,2^{n}-1]$ oznaczmy funkcję (zazwyczaj stablicowaną):

symbol(y) = s takie że CDF[s] <= y < CDF[s+1].

Teraz funkcja kodująca rANS to:

C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]

Dekodująca:

s = symbol(x & mask)

D(x) = (f[s] * (x >> n) + (x & mask ) – CDF[s], s)

W ten sposób kodujemy ciąg symboli do dużej liczby naturalnej $x.$ Żeby uniknąć arytmetyki na dużych liczbach wykorzystujemy wersję strumieniową: wymuszamy $x\in [L,b\cdot L-1]$ poprzez renormalizację – wysyłanie do (lub z) strumienia najmniej znaczących bitów $x$ (zazwyczaj $L$ i $b$ są potęgami 2).

W wariancie rANS liczba (stan) $x$ jest na przykład 32-bitowa. Dla 16-bitowej renormalizacji, $x\in [2^{16},2^{32}-1],$ dekoder uzupełnia najmniej znaczące bity ze strumienia kiedy zachodzi taka potrzeba:

if(x < (1 << 16)) x = (x << 16) + read16bits()

Wariant stablicowany (tANS: tabled ANS)

Prosty przykład 4 stanowego automatu tANS dla rozkładu prawdopodobieństwa Pr(a) = 3/4, Pr(b) = 1/4. Symbol b zawiera –lg(1/4) = 2 bity informacji, więc zawsze produkuje dwa bity. Natomiast symbol a zawiera –lg(3/4) ~ 0.415 bity informacji, więc czasem produkuje jeden bit (ze stanów 6 i 7), czasem zero (ze stanów 4 i 5), tylko zwiększając stan. Czyli stan działa jako bufor przechowujący ułamkową ilość bitów: lg(x). W praktyce ilość stanów to np. 2048 dla alfabetu o wielkości 256 (żeby bezpośrednio kodować bajty).

Wariant tANS umieszcza całe zachowanie (też renormalizację) dla $x\in [L,2L-1]$ w tablicy, dostając automat skończony, unikając w ten sposób mnożenia.

Ostatecznie krok dekodowania może być zapisany jako:

t = decodingTable(x);
x = t.newX + readBits(t.nbBits); //nowy stan
writeSymbol(t.symbol); //zdekodowany symbol

Krok kodowania:

s = ReadSymbol();
nbBits = (x + ns[s]) >> r; // bitów do renormalizacji
writeBits(x, nbBits); // wyślij najmłodsze bity do strumienia
x = encodingTable[start[s] + (x >> nbBits)];

Konkretne kodowanie tANS jest określone przez przyporządkowanie symbolu do każdej pozycji $[L,2L-1].$ Ilości wystąpień symboli powinny być proporcjonalne do założonych prawdopodobieństw. Na przykład dla rozkładu Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 można wybrać przyporządkowanie „abdacdac”. Jeśli symbole są przyporządkowane w przedziałach, których długości są potęgami 2, dostaniemy dokładnie kodowanie Huffmana. Na przykład $a\rightarrow 0,$ $b\rightarrow 100,$ $c\rightarrow 101,$ $d\rightarrow 11$ dostalibyśmy dla tANS z przyporządkowaniem „aaaabcdd”.

Linki zewnętrzne

• https://github.com/Cyan4973/FiniteStateEntropy Finite state entropy (FSE) implementacja tANS (Yann Collet)
• https://github.com/rygorous/ryg_rans Implementacja rANS (Fabian Giesen)
• https://github.com/jkbonfield/rans_static Szybka implementacja rANS i kodowania arytmetycznego (James K. Bonfield)
• https://github.com/facebook/zstd/ Kompresor Facebook Zstandard (Yann Collet, Przemysław Skibiński)
• https://github.com/lzfse/lzfse kompresor LZFSE (LZ+FSE) Apple Inc.
• kompresor DNA CRAM 3.0 DNA (rANS rzędu 1) (część SAMtools) z European Bioinformatics Institute
• https://chromium-review.googlesource.com/#/c/318743 implementacja rANS dla Google VP10
• https://chromium-review.googlesource.com/#/c/338781/ implementacja rANS dla Google WebP
• https://aomedia.googlesource.com/aom/+/master/aom_dsp implementacja rANS dla Alliance for Open Media
• http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Wolfram Demonstrations Project
• http://gamma.cs.unc.edu/GST/ GST: GPU-decodable Supercompressed Textures
• Understanding compression podręcznik, A. Haecky, C. McAnlis
• High throughput hardware architectures for asymmetric numeral systems entropy coding S. M. Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
• Y.Y. Collet Y.Y., M.M. Kucherawy M.M. (red.), Zstandard Compression and the application/zstd Media Type, RFC 8478, IETF, październik 2018, DOI: 10.17487/RFC8478, ISSN 2070-1721, OCLC 943595667  (ang.).
• Duda J., Asymetryczne systemy liczbowe – wygodna praca z ułamkowymi bitami, Delta 11/2021: http://www.deltami.edu.pl/2021a/11/2021-11-delta-art-05-duda.pdf