Asymetryczne systemy liczbowe - Asymmetric numeral systems

Asymetryczne systemy liczbowe ( ANS ) to rodzina metod kodowania entropijnego wprowadzona przez Jarosława (Jarka) Dudę z Uniwersytetu Jagiellońskiego , stosowana w kompresji danych od 2014 roku ze względu na lepszą wydajność w porównaniu do dotychczas stosowanych metod, będącą do 30 razy szybszą. ANS łączy współczynnik kompresji kodowania arytmetycznego (który wykorzystuje prawie dokładny rozkład prawdopodobieństwa) z kosztem przetwarzania podobnym do kodowania Huffmana . W wariancie z tabelą ANS (tANS) osiąga się to poprzez skonstruowanie maszyny skończonej do działania na dużym alfabecie bez użycia mnożenia.

ANS jest używany m.in. w kompresorze Facebook Zstandard (wykorzystywany także np. w jądrze Linux , systemie operacyjnym Android , został opublikowany jako RFC 8478 dla MIME i HTTP ), w kompresorze Apple LZFSE, kompresorze Google Draco 3D (wykorzystywanym np. w Pixar Universal Scene Description format) i kompresor obrazu PIK, w kompresorze CRAM DNA z narzędzi SAMtools i innych formatach plików genetycznych, kompresor Dropbox DivANS oraz w standardzie kompresji obrazu JPEG XL nowej generacji.

Podstawową ideą jest zakodowanie informacji w jedną liczbę naturalną . W standardowym systemie liczba binarna, możemy dodać trochę informacji, które przez dodanie na końcu , co daje nam . Dla kodera entropijnego jest to optymalne, jeśli . ANS uogólnia ten proces dla dowolnych zestawów symboli z towarzyszącym rozkładem prawdopodobieństwa . W ANS, jeżeli jest wynikiem dołączenia informacji od do , to . Równoważnie, , gdzie jest liczbą bitów informacji przechowywanych w liczbie i jest liczbą bitów zawartych w symbolu . ${\displaystyle x}$${\ Displaystyle s \ w \ {0,1 \}}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x}$${\displaystyle x'=2x+s}$${\ Displaystyle \ Pr (0) = \ Pr (1) = 1/2}$${\ Displaystyle s \ w S}$${\ Displaystyle (p_ {s}) _ {s \ w S}}$${\displaystyle x'}$${\displaystyle s}$${\displaystyle x}$${\ Displaystyle x '\ około x \ cdot p_ {s} ^ {-1}}$${\ Displaystyle \ log _ {2} (x ') \ około \ log _ {2} (x) + \ log _ {2} (1/p_ {s})}$${\displaystyle \log_{2}(x)}$${\displaystyle x}$${\ Displaystyle \ log _ {2} (1/p_ {s})}$${\displaystyle s}$

W przypadku zasady kodowania zbiór liczb naturalnych jest dzielony na rozłączne podzbiory odpowiadające różnym symbolom – podobnie jak liczby parzyste i nieparzyste, ale z gęstościami odpowiadającymi rozkładowi prawdopodobieństwa zakodowanych symboli. Następnie, aby dodać informację z symbolu do informacji już zapisanej w bieżącym numerze , przechodzimy do numeru będącego pozycją -tego wyglądu z -tego podzbioru. ${\displaystyle s}$${\displaystyle x}$${\displaystyle x'=C(x,s)\ok x/p}$${\displaystyle x}$${\displaystyle s}$

Istnieją alternatywne sposoby zastosowania go w praktyce – bezpośrednie formuły matematyczne dla kroków kodowania i dekodowania (warianty uABS i rANS) lub całe zachowanie można umieścić w tabeli (wariant tANS). Ponowna normalizacja służy do zapobiegania przechodzeniu w nieskończoność – przeniesieniu zgromadzonych bitów do lub ze strumienia bitów. ${\displaystyle x}$

Kodowanie entropijne

Załóżmy, że zakodowana zostanie sekwencja 1000 zer i jedynek, których bezpośrednie zapisanie zajmie 1000 bitów. Jeśli jednak jakoś wiadomo, że zawiera tylko 1 zero i 999 jedynek, wystarczyłoby zakodować położenie zera, co wymaga tutaj tylko bitów zamiast oryginalnych 1000 bitów. ${\ Displaystyle \ lceil \ log _ {2} (1000) \ rceil = 10}$

Generalnie takie ciągi długości zawierające zera i jedynek, z pewnym prawdopodobieństwem , nazywamy kombinacjami . Używając przybliżenia Stirlinga otrzymujemy ich asymptotyczną liczbę będącą ${\ Displaystyle n}$${\displaystyle pn}$${\ Displaystyle (1-p) n}$${\displaystyle p\w (0,1)}$

${\ Displaystyle {n \ wybierz pn} \ około 2 ^ {nh (p)} {\ tekst {dla dużych}} n {\ tekst {i}} h (p) = - p \ log _ {2} (p )-(1-p)\log _{2}(1-p),}$

zwany entropią Shannona .

Stąd, aby wybrać jedną taką sekwencję potrzebujemy około bitów. To wciąż bity , ale może być też znacznie mniejsze. Na przykład potrzebujemy tylko bitów dla . ${\displaystyle NH(p)}$${\ Displaystyle n}$${\ Displaystyle p = 1/2}$${\ Displaystyle \ około n/2}$${\ Displaystyle p = 0,11}$

Kodera entropijnego umożliwia kodowanie sekwencji symboli z wykorzystaniem w przybliżeniu bitów Shannon entropii na symbol. Na przykład ANS może być bezpośrednio użyty do wyliczenia kombinacji: przypisz inną liczbę naturalną do każdej sekwencji symboli o stałych proporcjach w prawie optymalny sposób.

W przeciwieństwie do kombinacji kodowania, ten rozkład prawdopodobieństwa zwykle różni się w kompresorach danych. W tym celu entropię Shannona można postrzegać jako średnią ważoną: symbol prawdopodobieństwa zawiera bity informacji. ANS koduje informacje w jedną liczbę naturalną , interpretowaną jako zawierająca bity informacji. Dodanie informacji z symbolu prawdopodobieństwa zwiększa tę zawartość informacyjną do . Dlatego nowy numer zawierający obie informacje powinien mieć postać . ${\displaystyle p}$${\displaystyle \log_{2}(1/p)}$${\displaystyle x}$${\displaystyle \log_{2}(x)}$${\displaystyle p}$${\ Displaystyle \ log _ {2} (x) + \ log _ {2} (1/p) = \ log _ {2} (x/p)}$${\displaystyle x'\ok x/p}$

Podstawowe pojęcia ANS

Porównanie koncepcji kodowania arytmetycznego (po lewej) i ANS (po prawej). Oba mogą być postrzegane jako uogólnienia standardowych systemów liczbowych, optymalnych dla jednolitego rozkładu prawdopodobieństwa cyfr, na zoptymalizowane dla pewnego wybranego rozkładu prawdopodobieństwa. Kodowanie arytmetyczne lub zakresowe odpowiada dodawaniu nowych informacji na najbardziej znaczącej pozycji, podczas gdy ANS uogólnia dodawanie informacji na najmniej znaczącej pozycji. Jego zasadą kodowania jest " x przechodzi do x-tego wyglądu podzbioru liczb naturalnych odpowiadającego aktualnie zakodowanemu symbolowi". W przedstawionym przykładzie sekwencja (01111) jest zakodowana na liczbę naturalną 18, mniejszą niż 47 uzyskaną przy użyciu standardowego systemu binarnego, dzięki lepszej zgodności z częstościami zakodowanego ciągu. Zaletą ANS jest przechowywanie informacji w jednej liczbie naturalnej, w przeciwieństwie do dwóch określających zakres.

Wyobraź sobie, że w liczbie naturalnej jest przechowywana jakaś informacja , na przykład jako sekwencja bitowa jej rozwinięcia binarnego. Aby dodać informacje ze zmiennej binarnej , możemy użyć funkcji kodowania , która przesuwa wszystkie bity o jedną pozycję w górę, a nowy bit umieszcza w najmniej znaczącej pozycji. Teraz funkcja dekodowania pozwala odzyskać poprzedni i ten dodany bit: . Możemy zacząć od stanu początkowego, a następnie użyć funkcji na kolejnych bitach skończonej sekwencji bitów, aby uzyskać końcową liczbę przechowującą całą sekwencję. Następnie użyj funkcji wiele razy, aż do uzyskania sekwencji bitów w odwrotnej kolejności. ${\displaystyle x}$${\displaystyle s}$${\displaystyle x'=C(x,s)=2x+s}$${\displaystyle D(x')=(\lpodłoga x'/2\rpodłoga,\mathrm {mod} (x',2))}$${\displaystyle x}$${\ Displaystyle D (C (x, s)) = (x, s), \ C (D (x')) = x'}$${\displaystyle x=1}$${\displaystyle C}$${\displaystyle x}$${\ Displaystyle D}$${\displaystyle x=1}$

Powyższa procedura jest optymalna dla równomiernego (symetrycznego) rozkładu prawdopodobieństwa symboli . ANS uogólniają go tak, aby był optymalny dla dowolnego wybranego (asymetrycznego) rozkładu prawdopodobieństwa symboli: . Podczas gdy w powyższym przykładzie wybierano pomiędzy parzystymi i nieparzystymi , w ANS ten parzysty/nieparzysty podział liczb naturalnych został zastąpiony podziałem na podzbiory o gęstości odpowiadającej założonemu rozkładowi prawdopodobieństwa : do pozycji występuje w przybliżeniu symbol . ${\ Displaystyle \ Pr (0) = \ Pr (1) = 1/2}$${\ Displaystyle \ Pr (s) = p_ {s}}$${\displaystyle s}$${\displaystyle C(x,s)}$${\ Displaystyle \ {p_ {s} \} _ {s}}$${\displaystyle x}$${\displaystyle xp_{s}}$${\displaystyle s}$

Funkcja kodująca zwraca -ty wygląd z takiego podzbioru odpowiadający symbolowi . Założenie gęstości jest równoznaczne z warunkiem . Zakładając, że liczba naturalna zawiera informację bitową, . Stąd symbol prawdopodobieństwa jest zakodowany jako zawierający bity informacji, tak jak jest to wymagane od koderów entropijnych . ${\displaystyle C(x,s)}$${\displaystyle x}$${\displaystyle s}$${\ Displaystyle x' = C (x, s) \ około x / p_ {s}}$${\displaystyle x}$${\displaystyle \log_{2}(x)}$${\ Displaystyle \ log _ {2} (C (x, s)) \ około \ log _ {2} (x) + \ log _ {2} (1/p_ {s})}$${\displaystyle p_{s}}$${\ Displaystyle \ około \ log _ {2} (1/p_ {s})}$

Jednolity wariant binarny (uABS)

Zacznijmy od alfabetu binarnego i rozkładu prawdopodobieństwa , . Do pozycji potrzebujemy w przybliżeniu analogów liczb nieparzystych (dla ). Tę liczbę wystąpień możemy wybrać jako , coraz . Ten wariant nazywa się uABS i prowadzi do następujących funkcji dekodowania i kodowania: ${\ Displaystyle \ Pr(1) = p}$${\ Displaystyle \ Pr (0) = 1-p}$${\displaystyle x}$${\displaystyle p\cdot x}$${\displaystyle s=1}$${\ Displaystyle \ lceil x \ cdot p \ rceil}$${\ Displaystyle s = \ lceil (x + 1) \ cdot p \ rceil - \ lceil x \ cdot p \ rceil}$

Rozszyfrowanie:

s = ceil((x+1)*p) - ceil(x*p)  // 0 if fract(x*p) < 1-p, else 1
if s = 0 then new_x = x - ceil(x*p)   // D(x) = (new_x, 0), this is the same as new_x = floor(x*(1-p))
if s = 1 then new_x = ceil(x*p)  // D(x) = (new_x, 1)

Kodowanie:

if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x
if s = 1 then new_x = floor(x/p)  // C(x,1) = new_x

Ponieważ jest to standardowy system binarny (z odwróconymi 0 i 1), dla innego staje się optymalny dla danego rozkładu prawdopodobieństwa. Na przykład, dla tych formuł prowadzą do tabeli dla małych wartości : ${\ Displaystyle p = 1/2}$${\displaystyle p}$${\ Displaystyle p = 0,3}$${\displaystyle x}$

${\displaystyle C(x,s)}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle s=0}$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
${\displaystyle s=1}$	0			1			2				3			4			5				6

Symbol odpowiada podzbiorowi liczb naturalnych o gęstości , które w tym przypadku są pozycjami . Ponieważ pozycje te wzrastają o 3 lub 4. Ponieważ tutaj wzór symboli powtarza się co 10 pozycji. ${\displaystyle s=1}$${\ Displaystyle p = 0,3}$${\ Displaystyle \ {0,3,6,10,13,16,20,23,26 \ldots \}}$${\ Displaystyle 1/4 <0,3 <1/3}$${\ Displaystyle p = 3/10}$

Kodowanie można znaleźć wybierając wiersz odpowiadający danemu symbolowi i wybierając dany w tym wierszu. Następnie w górnym wierszu znajduje się . Na przykład od środka do górnego rzędu. ${\displaystyle C(x,s)}$${\displaystyle s}$${\displaystyle x}$${\displaystyle C(x,s)}$${\ Displaystyle C (7,0) = 11}$

Wyobraź sobie, że chcielibyśmy zakodować sekwencję '0100' zaczynając od . Najpierw zabiera nas do , potem do , potem do , potem do . Korzystając z funkcji dekodowania w tym finale , możemy pobrać sekwencję symboli. Wykorzystując w tym celu tabelę, w pierwszym wierszu określa się kolumnę, następnie niepusty wiersz i zapisaną wartość określają odpowiednie i . ${\displaystyle x=1}$${\displaystyle s=0}$${\displaystyle x=2}$${\displaystyle s=1}$${\displaystyle x=6}$${\displaystyle s=0}$${\displaystyle x=9}$${\displaystyle s=0}$${\displaystyle x=14}$${\displaystyle D(x')}$${\displaystyle x}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x}$

Warianty zasięgu (rANS) i streaming

Wariant zakresowy również wykorzystuje wzory arytmetyczne, ale umożliwia operowanie na dużym alfabecie. Intuicyjnie dzieli zbiór liczb naturalnych na przedziały wielkościowe , a każdy z nich w identyczny sposób dzieli na podzakresy o proporcjach określonych przez założony rozkład prawdopodobieństwa. ${\ Displaystyle 2 ^ {n}}$

Zaczynamy od kwantyzacji rozkładu prawdopodobieństwa do mianownika, gdzie wybiera się n (zwykle 8-12 bitów): dla niektórych liczb naturalnych (wielkości podzakresów). ${\ Displaystyle 2 ^ {n}}$${\ Displaystyle p_ {s} \ ok. f [s] / 2 ^ {n}}$${\displaystyle f[s]}$

Oznaczmy , dystrybuantę skumulowaną: ${\ Displaystyle {\ tekst {maska}} = 2 ^ {n} -1}$

${\ Displaystyle \ operatorname {CDF} [s] = \ suma _ {i<s}f[i]=f[0]+\cdots+f[s-1].}$

Dla oznaczenia funkcji (zwykle w formie tabeli) ${\ Displaystyle y \ w [0,2 ^ {n}-1]}$

symbol(y) = s  such that  CDF[s] <= y < CDF[s+1]

Teraz funkcja kodowania to:

C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]

Rozszyfrowanie: s = symbol(x & mask)

D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s)

W ten sposób możemy zakodować sekwencję symboli w dużą liczbę naturalną x . Aby uniknąć stosowania arytmetyki dużych liczb, w praktyce stosuje się warianty strumieni: które wymuszają przez renormalizację: wysyłanie najmniej znaczących bitów x do lub ze strumienia bitów (zwykle L i b są potęgami 2). ${\displaystyle x\w [l,b\cdot l-1]}$

W wariancie rANS x jest na przykład 32-bitowy. W przypadku 16-bitowej renormalizacji dekoder w razie potrzeby uzupełnia najmniej znaczące bity ze strumienia bitów: ${\ Displaystyle x \ w [2 ^ {16}, 2 ^ {32} -1]}$

if(x < (1 << 16)) x = (x << 16) + read16bits()

Wariant stołowy (tANS)

Prosty przykład 4-stanowego automatu ANS dla Pr( a ) = 3/4, Pr( b ) = 1/4 rozkład prawdopodobieństwa. Symbol b zawiera −lg(1/4) = 2 bity informacji, a więc zawsze daje dwa bity. Natomiast symbol a zawiera −lg(3/4) ~ 0,415 bitów informacji, stąd czasami daje jeden bit (ze stanu 6 i 7), czasami 0 bitów (ze stanu 4 i 5), tylko zwiększając stan, co pełni rolę bufora zawierającego ułamkową liczbę bitów: lg( x ). Liczba stanów w praktyce wynosi np. 2048, dla alfabetu o rozmiarze 256 (do bezpośredniego kodowania bajtów).

Wariant tANS umieszcza całe zachowanie (w tym renormalizację) for w tabeli, która daje maszynę skończoną, unikając potrzeby mnożenia. ${\displaystyle x\w [L,2L-1]}$

Na koniec etap pętli dekodowania można zapisać jako:

t = decodingTable(x);  
x = t.newX + readBits(t.nbBits); //state transition
writeSymbol(t.symbol); //decoded symbol

Krok pętli kodowania:

s = ReadSymbol();
nbBits = (x + ns[s]) >> r;  // # of bits for renormalization
writeBits(x, nbBits);  // send the least significant bits to bitstream
x = encodingTable[start[s] + (x >> nbBits)];

Konkretne kodowanie tANS określa się przez przypisanie symbolu do każdej pozycji, ich liczba wystąpień powinna być proporcjonalna do założonych prawdopodobieństw. Na przykład można wybrać przypisanie "abdacdac" dla rozkładu prawdopodobieństwa Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8. Jeśli symbole są przypisane w zakresach długości będących potęgami 2, otrzymalibyśmy kodowanie Huffmana . Na przykład kod prefiksu a->0, b->100, c->101, d->11 byłby otrzymany dla tANS z przypisaniem symbolu „aaaabcdd”. ${\displaystyle [L,2L-1]}$

Przykład generowania tablic tANS dla alfabetu o rozmiarze m = 3 i L = 16 stanów, a następnie zastosowanie ich do dekodowania strumienia. Najpierw przybliżamy prawdopodobieństwa za pomocą ułamka, którego mianownikiem jest liczba stanów. Następnie rozkładamy te symbole w prawie jednolity sposób, opcjonalnie szczegóły mogą zależeć od klucza kryptograficznego do jednoczesnego szyfrowania. Następnie wyliczamy wyglądy zaczynając od wartości będącej ich ilością dla danego symbolu. Następnie uzupełniamy najmłodsze bity ze strumienia, aby powrócić do założonego zakresu dla x (renormalizacja).

Uwagi

Jeśli chodzi o kodowanie Huffmana, modyfikacja rozkładu prawdopodobieństwa tANS jest stosunkowo kosztowna, stąd jest stosowana głównie w sytuacjach statycznych, zwykle z pewnym schematem Lempel-Ziv (np. ZSTD, LZFSE). W tym przypadku plik dzielony jest na bloki - dla każdego z nich niezależnie zliczane są częstotliwości symboli, a następnie po aproksymacji (kwantyzacji) zapisywanej w nagłówku bloku i wykorzystywanej jako statyczny rozkład prawdopodobieństwa dla tANS.

W przeciwieństwie do tego rANS jest zwykle używany jako szybszy zamiennik kodowania zakresu (np. CRAM , LZNA, Draco, AV1 ). Wymaga mnożenia, ale jest bardziej wydajny pod względem pamięci i jest odpowiedni do dynamicznego dostosowywania rozkładów prawdopodobieństwa.

Kodowanie i dekodowanie ANS odbywa się w przeciwnych kierunkach, dzięki czemu jest to stos symboli. Ta niedogodność jest zwykle rozwiązywana przez kodowanie w kierunku wstecznym, po czym można wykonać dekodowanie do przodu. W przypadku zależności kontekstowej, takiej jak model Markowa , koder musi używać kontekstu z perspektywy późniejszego dekodowania. W przypadku adaptacyjności koder powinien najpierw przejść do przodu, aby znaleźć prawdopodobieństwa, które będą używane (przewidywane) przez dekoder i przechowywać je w buforze, a następnie kodować w kierunku wstecznym przy użyciu zbuforowanych prawdopodobieństw.

Ostateczny stan kodowania jest wymagany do rozpoczęcia dekodowania, dlatego musi być przechowywany w skompresowanym pliku. Koszt ten można zrekompensować poprzez przechowywanie niektórych informacji w początkowym stanie kodera. Na przykład, zamiast zaczynać od stanu „10000”, zacznij od stanu „1****”, gdzie „*” to dodatkowe zapisane bity, które można odzyskać na końcu dekodowania. Alternatywnie, stan ten może być użyty jako suma kontrolna, rozpoczynając kodowanie od ustalonego stanu i sprawdzając, czy końcowy stan dekodowania jest oczekiwany.

Kontrowersje patentowe

Autor nowatorskiego algorytmu ANS i jego wariantów, tANS i rANS, chciał, aby jego prace były swobodnie dostępne w domenie publicznej z powodów altruistycznych. Nie dążył do czerpania z nich korzyści i podjął kroki, aby zapewnić, że nie staną się „legalnym polem minowym” lub ograniczonym lub czerpanym przez innych. W 2015 r. Google opublikował amerykański, a następnie światowy patent na „Mixed Boolean-token and factor coding”. W tym czasie profesor Duda został poproszony przez Google o pomoc w kompresji wideo, więc był dokładnie świadomy tej domeny, mając do pomocy oryginalnego autora.

Duda nie był zadowolony z (przypadkowego) odkrycia intencji patentowych Google, ponieważ jasno określił, że chce, aby była to domena publiczna i wspierał Google właśnie na tej podstawie. Duda złożył następnie wniosek osoby trzeciej do urzędu patentowego USA o odrzucenie. USPTO odrzuciło jego wniosek w 2018 roku, a Google następnie porzucił patent.

W czerwcu 2019 r. Microsoft złożył wniosek patentowy o nazwie „Funkcje kodowania i dekodowania systemu liczb asymetrycznych zakresu”. USPTO wydała ostateczne odrzucenie wniosku w dniu 27 października 2020 r. Jednak 2 marca 2021 r. Microsoft złożył uzasadnienie USPTO stwierdzające „Wnioskodawca z szacunkiem nie zgadza się z odrzuceniem”, starając się unieważnić ostateczne odrzucenie w ramach „Po Program Rozważania Końcowego 2.0". Wniosek jest obecnie w toku, ponieważ USPTO nie potwierdziło, czy pozwoli na kontynuowanie odwołania od odrzucenia.

Zobacz też

• Kodowanie entropii
• Kodowanie Huffmana
• Kodowanie arytmetyczne
• Kodowanie zakresu
• Zstandardowy kompresor Facebooka
• Kompresor LZFSE Apple

Bibliografia

Zewnętrzne linki

• Architektury sprzętowe o wysokiej przepustowości do kodowania entropijnego asymetrycznych systemów liczbowych SM Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
• https://github.com/Cyan4973/FiniteStateEntropy Implementacja tANS według entropii skończonego stanu (FSE) autorstwa Yanna Colleta
• https://github.com/rygorous/ryg_rans Wdrożenie rANS przez Fabiana Giesena
• https://github.com/jkbonfield/rans_static Szybka implementacja rANS i kodowania arytmetycznego przez Jamesa K. Bonfielda
• https://github.com/facebook/zstd/ Facebook kompresor Zstandard autorstwa Yanna Colleta (autora LZ4 )
• https://github.com/lzfse/lzfse Kompresor LZFSE (LZ+FSE) firmy Apple Inc.
• Kompresor CRAM 3.0 DNA (zamówienie 1 rANS) (część SAMtools ) przez Europejski Instytut Bioinformatyki
• https://chromium-review.googlesource.com/#/c/318743 Implementacja dla Google VP10
• https://chromium-review.googlesource.com/#/c/338781/ implementacja dla Google WebP
• https://github.com/google/draco/tree/master/core Biblioteka kompresji 3D Google Draco
• https://aomedia.googlesource.com/aom/+/master/aom_dsp wdrożenie Alliance for Open Media
• http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Wolfram Demonstrations Project
• http://gamma.cs.unc.edu/GST/ GST: Superkompresowane tekstury dekodowane przez GPU
• Zrozumienie książki o kompresji autorstwa A. Haecky, C. McAnlis