Asymmetric Numeral Systems (asymetryczne systemy liczbowe, ANS)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. – rodzina kodowań entropijnych wprowadzonych przez dr. Jarosława DudęWiadomości Uniwersytetu Jagiellońskiego: Używasz Facebooka lub Apple’a? Twoje dane są zapisane kodowaniem z UJ. na przestrzeni lat 2006–2014, używanych w kompresji danych od 2014 rokuList of compressors using ANS, implementations and other materials. 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 FacebookSmaller and faster data compression with Zstandard, Facebook, August 2016.5 ways Facebook improved compression at scale with Zstandard, Facebook, December 2018. (także używany m.in. w jądrze systemu LinuxZstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook, Phoronix, September 2017., przeglądarce Google ChromeNew in Chrome 123 (Content-Encoding), Google, March 2024., AndroidZstd w Android P., został opublikowany jako dla MIMEZstandard Compression and The application/zstd Media Type (email standard). i HTTPHypertext Transfer Protocol (HTTP) Parameters, IANA.), w kompresorze LZFSE z AppleApple Open-Sources its New Compression Algorithm LZFSE, InfoQ, July 2016., kompresorze 3D DracoGoogle Draco 3D compression library. i obrazu PIK z GoogleGoogle PIK: new lossy image format for the internet., kompresorze DNA CRAMCRAM format specification (version 3.0). z SAMtools, bibliotece do szybkiej kompresji Nvidia nvCOMPHigh Speed Data Compression Using NVIDIA GPUs., kompresorze DivANS z DropboxBuilding better compression together with DivANS., Microsoft BCPack kompresji tekstur (komponent DirectX)Microsoft DirectStorage overview., oraz w standardzie kompresji obrazu JPEG XLCommittee Draft of JPEG XL Image Coding System..

Podstawową koncepcją ANS jest zapisanie informacji w pojedynczej liczbie naturalnej W standardowym systemie liczbowym możemy dodać bit informacji do informacji już zawartej w liczbie poprzez wstawienie go na ostatniej pozycji, prowadząc do liczby Dla kodowania entropijnego jest to optymalne o ile ANS uogólnia ten proces do dowolnego zestawu symboli z założonym rozkładem prawdopodobieństwa Nowa liczba jest rezultatem dodania informacji z do liczby używając przybliżonej zależności: Równoważnie: gdzie jest ilością bitów informacji zapisanych w liczbie oraz jest ilością bitów zawartą w symbolu

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 do informacji już zapisanej w aktualnej liczbie przechodzimy do liczby będącej -tym wystąpieniem z -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 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 można użyć wariantu uABS, który dokonuje podziału zbioru liczb naturalnych prawie jednorodnie z powyższymi gęstościami. Do pozycji powinno być mniej więcej wystąpień odpowiedników liczb nieparzystych (dla ). Można wybrać tę liczbę jako dostając Ostatecznie otrzymuje się poniższe funkcje dla kroku kodowania/dekodowaniaData Compression Explained, Matt Mahoney..

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 dostaje się standardowy system dwójkowy (z zamienionymi 0 i 1). Dla innych staje się on zoptymalizowany dla danego rozkładu prawdopodobieństwa. Na przykład dla powyższe formuły prowadzą do tabelki dla małych wartości

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6

Symbol odpowiada podzbiorowi liczb naturalnych o gęstości które w powyższej tabelce są pozycjami Jako że te pozycje zwiększają się o 3 lub 4. Ponieważ tutaj wzorzec symboli powtarza się co 10 pozycji.

Wartość dostaje się, biorąc wiersz odpowiadający danemu symbolowi z którego wybieramy zadane Wtedy wartość w górnym wierszu daje Na przykład przechodząc od środkowego do górnego wiersza.

Żeby zakodować sekwencję '0100' zaczynając od , najpierw powinien prowadzić do potem do potem do a na końcu do Używając funkcji dekodującej na tym ostatnim można odtworzyć zakodowaną sekwencję symboli w odwrotnej kolejności. Żeby użyć powyższej tabelki w tym celu, w pierwszym wierszu determinuje kolumnę, dla której niepusta wartość poniżej określa i

W zwykłym systemie dwójkowym, używając reguły dla powyższego ciągu symboli, kod przeszedłby przez odpowiednio Dochodzi wtedy do zakodowania tego ciągu w liczbie która jest bardziej kosztowna do zapisania niż (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 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 gdzie jest wybrane (zwykle 8-12 bitów): dla pewnych liczb naturalnych (wielkości podprzedziałów).

Żeby tak było, należy oznaczyć dystrybuantę:

Dla 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 Żeby uniknąć arytmetyki na dużych liczbach, wykorzystuje się wersję strumieniową: wymusza się poprzez renormalizację – wysyłanie do (lub z) strumienia najmniej znaczących bitów (zazwyczaj i są potęgami 2).

W wariancie rANS liczba (stan) jest na przykład 32-bitowa. Dla 16-bitowej renormalizacji 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) thumb|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. 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 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 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 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

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

Kategoria:Algorytmy kompresji bezstratnej Kategoria:Polskie wynalazki Kategoria:Teoria automatów