Asymmetric Numeral Systems

Asymmetric Numeral Systems (asymetryczne systemy liczbowe, ANS)^[1] – rodzina kodowań entropijnych wprowadzonych przez dr. Jarosława Dudę^[2] na przestrzeni lat 2006–2014, używanych w kompresji danych od 2014 roku^[3] 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^[4][5] (także używany m.in. w jądrze systemu Linux^[6], przeglądarce Google Chrome^[7], Android^[8], został opublikowany jako RFC 8478 ↓ dla MIME^[9] i HTTP^[10]), w kompresorze LZFSE z Apple^[11], kompresorze 3D Draco^[12] i obrazu PIK z Google^[13], kompresorze DNA CRAM^[14] z SAMtools, bibliotece do szybkiej kompresji Nvidia nvCOMP^[15], kompresorze DivANS z Dropbox^[16], Microsoft BCPack kompresji tekstur (komponent DirectX)^[17], oraz w standardzie kompresji obrazu JPEG XL^[18].

Podstawową koncepcją ANS jest zapisanie informacji w pojedynczej liczbie naturalnej ${\displaystyle x.}$ W standardowym systemie liczbowym możemy dodać bit informacji ${\displaystyle s\in \{0,1\}}$ do informacji już zawartej w liczbie ${\displaystyle x}$ poprzez wstawienie go na ostatniej pozycji, prowadząc do liczby ${\displaystyle x'=2x+s.}$ Dla kodowania entropijnego jest to optymalne o ile ${\displaystyle \Pr(0)=\Pr(1)=1/2.}$ ANS uogólnia ten proces do dowolnego zestawu symboli ${\displaystyle s\in S}$ z założonym rozkładem prawdopodobieństwa ${\displaystyle (p_{s})_{s\in S}.}$ Nowa liczba ${\displaystyle x'}$ jest rezultatem dodania informacji z ${\displaystyle s}$ do liczby ${\displaystyle x}$ używając przybliżonej zależności: ${\displaystyle x'\approx x/p_{s}.}$ Równoważnie: ${\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s}),}$ gdzie ${\displaystyle \log _{2}(x)}$ jest ilością bitów informacji zapisanych w liczbie ${\displaystyle x}$ oraz ${\displaystyle \log _{2}(1/p_{s})}$ jest ilością bitów zawartą w symbolu ${\displaystyle 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 ${\displaystyle s}$ do informacji już zapisanej w aktualnej liczbie ${\displaystyle x,}$ przechodzimy do liczby ${\displaystyle x'=C(x,s)\approx x/p}$ będącej ${\displaystyle x}$-tym wystąpieniem z ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle x}$ chcemy mniej więcej ${\displaystyle p\cdot x}$ wystąpień odpowiedników liczb nieparzystych (dla ${\displaystyle s=1}$). Możemy wybrać tę liczbę jako ${\displaystyle \lceil x\cdot p\rceil ,}$ dostając ${\displaystyle s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil .}$ Ostatecznie dostajemy poniższe funkcje dla kroku kodowania/dekodowania^[19].

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

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

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

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

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

W zwykłym systemie dwójkowym: używając reguły ${\displaystyle x'=2x+s,}$ dla powyższego ciągu symboli przeszlibyśmy przez odpowiednio ${\displaystyle x=1,2,5,10,20.}$ Czyli zakodowalibyśmy ten ciąg w liczbie ${\displaystyle x=20,}$ która jest bardziej kosztowna do zapisania niż ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 2^{n},}$ gdzie ${\displaystyle n}$ jest wybrane (zwykle 8-12 bitów): ${\displaystyle p_{s}\approx f[s]/2^{n}}$ dla pewnych liczb naturalnych ${\displaystyle f[s]>0}$ (wielkości podprzedziałów).

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

Dla ${\displaystyle 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 ${\displaystyle x.}$ Żeby uniknąć arytmetyki na dużych liczbach wykorzystujemy wersję strumieniową: wymuszamy ${\displaystyle x\in [L,b\cdot L-1]}$ poprzez renormalizację – wysyłanie do (lub z) strumienia najmniej znaczących bitów ${\displaystyle x}$ (zazwyczaj ${\displaystyle L}$ i ${\displaystyle b}$ są potęgami 2).

W wariancie rANS liczba (stan) ${\displaystyle x}$ jest na przykład 32-bitowa. Dla 16-bitowej renormalizacji, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle [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 ${\displaystyle a\rightarrow 0,}$ ${\displaystyle b\rightarrow 100,}$ ${\displaystyle c\rightarrow 101,}$ ${\displaystyle d\rightarrow 11}$ dostalibyśmy dla tANS z przyporządkowaniem „aaaabcdd”.

Przypisy

1. J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, The use of asymmetric numeral systems as an accurate replacement for Huffman coding, Picture Coding Symposium, 2015.
2. Wiadomości Uniwersytetu Jagiellońskiego: Używasz Facebooka lub Apple’a? Twoje dane są zapisane kodowaniem z UJ.
3. List of compressors using ANS, implementations and other materials.
4. Smaller and faster data compression with Zstandard, Facebook, August 2016.
5. 5 ways Facebook improved compression at scale with Zstandard, Facebook, December 2018.
6. Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook, Phoronix, September 2017.
7. New in Chrome 123 (Content-Encoding), Google, March 2024.
8. Zstd w Android P.
9. Zstandard Compression and The application/zstd Media Type (email standard).
10. Hypertext Transfer Protocol (HTTP) Parameters, IANA.
11. Apple Open-Sources its New Compression Algorithm LZFSE, InfoQ, July 2016.
12. Google Draco 3D compression library.
13. Google PIK: new lossy image format for the internet.
14. CRAM format specification (version 3.0).
15. High Speed Data Compression Using NVIDIA GPUs.
16. Building better compression together with DivANS.
17. Microsoft DirectStorage overview.
18. Committee Draft of JPEG XL Image Coding System.
19. Data Compression Explained, Matt Mahoney.

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