Asymmetric Numeral Systems

Ten artykuł należy dopracować:

od 2025-11 → poprawić styl – powinien być encyklopedyczny,
od 2025-11 → poprawić tłumaczenie fragmentów tekstu/pojęć (uwaga! nie należy używać automatycznych translatorów bez sprawdzenia uzyskanego dzięki nim tłumaczenia),
od 2024-04 → dodać przypisy do treści niemających odnośników do źródeł.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 ${\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żna użyć wariantu uABS, który dokonuje podziału zbioru liczb naturalnych prawie jednorodnie z powyższymi gęstościami. Do pozycji ${\displaystyle x}$ powinno być mniej więcej ${\displaystyle p\cdot x}$ wystąpień odpowiedników liczb nieparzystych (dla ${\displaystyle s=1}$). Można 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 otrzymuje się 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 ${\displaystyle p=1/2}$ dostaje się 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)}$ dostaje się, 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.

Żeby zakodować sekwencję '0100' zaczynając od ${\displaystyle x=1}$, najpierw ${\displaystyle s=0}$ powinien 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żna 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, kod przeszedłby przez odpowiednio ${\displaystyle x=1,2,5,10,20.}$ Dochodzi wtedy do zakodowania tego ciągu 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.

Kod może się również rozpocząć 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).

Żeby tak było, należy oznaczyć ${\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]}$ należy oznaczyć 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 koduje ciąg symboli do dużej liczby naturalnej ${\displaystyle x.}$ Żeby uniknąć arytmetyki na dużych liczbach, wykorzystuje się wersję strumieniową: wymusza się ${\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)

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}$ można dostać dla tANS z przyporządkowaniem „aaaabcdd”.

Przypisy

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