Asymmetric Numeral Systems

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Szablon:Dopracować

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 Szablon:Odn 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 x. W standardowym systemie liczbowym możemy dodać bit informacji s∈{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∈S z założonym rozkładem prawdopodobieństwa (ps)s∈S. Nowa liczba x′ jest rezultatem dodania informacji z s do liczby x używając przybliżonej zależności: x′≈x/ps. Równoważnie: log2(x′)≈log2(x)+log2(1/ps), gdzie log2(x) jest ilością bitów informacji zapisanych w liczbie x oraz log2(1/ps) 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)≈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⋅x wystąpień odpowiedników liczb nieparzystych (dla s=1). Możemy wybrać tę liczbę jako ⌈x⋅p⌉, dostając s=⌈(x+1)⋅p⌉−⌈x⋅p⌉. 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 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,…}. 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 2n, 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 2n, gdzie n jest wybrane (zwykle 8-12 bitów): ps≈f[s]/2n dla pewnych liczb naturalnych f[s]>0 (wielkości podprzedziałów).

Oznaczmy mask=2n−1, dystrybuantę: CDF⁡[s]=∑i<sf[i]=f[0]+…+f[s−1].

Dla y∈[0,2n−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∈[L,b⋅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∈[216,232−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∈[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→0, b→100, c→101, d→11 dostalibyśmy dla tANS z przyporządkowaniem „aaaabcdd”.

Przypisy

Szablon:Przypisy

Linki zewnętrzne

  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.
Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Asymmetric_Numeral_Systems&oldid=7575”