Asymmetric Numeral Systems

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Asymmetric Numeral Systems (asymetryczne systemy liczbowe, ANS)[1] to 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] (także używany m.in. w jądrze Linux[5], został opublikowany jako RFC 8478 dla MIME[6] i HTTP[7]), w kompresorze LZFSE z Apple[8], kompresorze 3D Draco[9] i obrazu PIK z Google[10], kompresorze DNA CRAM[11] z SAMtools, kompresorze DivANS z Dropbox[12], i jest rozważany dla otwartego formatu wideo AV1[13] z Alliance for Open Media.

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 wykorzystywane ż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 uABS (uniform binary)[edytuj | edytuj kod]

Dla dwuelementowego alfabetu oraz rozkładu prawdopodobieństwa możemy użyć wariantu uABS, który dokonuje podziału zbioru liczb naturalnych prawie jednorodnie z powyższymi gęstościami. Do pozycji chcemy mniej więcej wystąpień odpowiedników liczb nieparzystych (dla ). Możemy wybrać tę liczbę jako dostając Ostatecznie dostajemy poniższe funkcje dla kroku kodowania/dekodowania[14].

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 dostajemy 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ść dostajemy biorąc wiersz odpowiadający danemu symbolowi z którego wybieramy zadane Wtedy wartość w górnym wierszy daje Na przykład przechodząc od środkowego do górnego wiersza.

Wyobraźmy sobie kodowanie sekwencji '0100' zaczynając od Najpierw prowadzi do potem do potem do a na końcu do Używając funkcji dekodującej na tym ostatnim możemy 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 przeszlibyśmy przez odpowiednio Czyli zakodowalibyśmy ten ciąg 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[edytuj | edytuj kod]

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.

Zaczynamy 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).

Oznaczmy dystrybuantę:

Dla 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 Żeby uniknąć arytmetyki na dużych liczbach wykorzystujemy wersję strumieniową: wymuszamy 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)[edytuj | edytuj kod]

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 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 a->0, b->100, c->101, d->11 dostalibyśmy dla tANS z przyporządkowaniem „aaaabcdd”.

Przypisy[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]