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 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ż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[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 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 wierszu 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
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)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Simple_example_of_ANS_automaton.png/480px-Simple_example_of_ANS_automaton.png)
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 dostalibyśmy dla tANS z przyporządkowaniem „aaaabcdd”.
Przypisy
- ↑ 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.
- ↑ Wiadomości Uniwersytetu Jagiellońskiego: Używasz Facebooka lub Apple’a? Twoje dane są zapisane kodowaniem z UJ.
- ↑ List of compressors using ANS, implementations and other materials.
- ↑ Smaller and faster data compression with Zstandard, Facebook, August 2016.
- ↑ 5 ways Facebook improved compression at scale with Zstandard, Facebook, December 2018.
- ↑ Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook, Phoronix, September 2017.
- ↑ New in Chrome 123 (Content-Encoding), Google, March 2024.
- ↑ Zstd w Android P.
- ↑ Zstandard Compression and The application/zstd Media Type (email standard).
- ↑ Hypertext Transfer Protocol (HTTP) Parameters, IANA.
- ↑ Apple Open-Sources its New Compression Algorithm LZFSE, InfoQ, July 2016.
- ↑ Google Draco 3D compression library.
- ↑ Google PIK: new lossy image format for the internet.
- ↑ CRAM format specification (version 3.0).
- ↑ High Speed Data Compression Using NVIDIA GPUs.
- ↑ Building better compression together with DivANS.
- ↑ Microsoft DirectStorage overview.
- ↑ Committee Draft of JPEG XL Image Coding System.
- ↑ Data Compression Explained, Matt Mahoney.
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