Asymmetric Numeral Systems

Ten artykuł należy dopracować:

od 2024-04 → poprawić styl – powinien być encyklopedyczny,
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)^[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.