Chyba wszyscy informatycy słyszeli o kodowaniu Huffmana używanym m.in. w zip, rar, png, jpg, mp3, pdf - jest ono szybkie ale niedokładne: przybliża prawdopodobieństwa potęgami 1/2. Przykładowo kod A->00, B->01, C->1 jest optymalny gdy prawdopodobieństwa symboli wynoszą odpowiednio 1/4, 1/4 i 1/2. Natomiast symbol (zdarzenie) o prawdopodobieństwie 0.99 niesie tylko ~0.014 bita informacji (log(1/p)) , podczas gdy kodowanie Huffmana potrzebowałoby użyć dla niego aż 1 bit.
Tę nieoptymalność naprawia kodowanie arytmetyczne, pozwalając na lepszy stopień kompresji (operuje na dowolnych prawdopodobieństwach), jednak będąc znacznie bardziej kosztowne obliczeniowo (m.in. potrzebuje mnożenia). Jest używane m.in. we współczesnej kompresji wideo czy LZMA (7-Zip, xz).
Okazuje się że powyższy kompromis między kosztem (szybkością) a stopniem kompresji został niedawno zakończony: od 2014 roku nowe kompresory są oparte już na innym kodowaniu (ANS), pochodzącym z Uniwersytetu Jagiellońskiego - jest ono równocześnie dokładne (używa dowolnych prawdopodobieństw) i tanie obliczeniowo (nie potrzebuje mnożenia).
Koncepcyjnie od kodowania arytmetycznego różni się tym że zamiast reprezentować informację jako przedział (dwie liczby), ANS operuje bezpośrednio na pojedynczej liczbie naturalnej: która jest zwiększana ~1/p razy podczas kodowania symbolu o prawdopodobieństwie p.
W 2013 roku state-of-art dla dekodowania arytmetycznego to było ~50MB/s/rdzeń i7 (dla Huffmana ~200MB/s), obecnie analogiczne zadanie osiąga ~1500MB/s na tym samym procesorze (rzędu 30x przyspieszenie, Huffman przyspieszył do ~1000MB/s): https://sites.google.com/site/powturbo/entropy-coder
Wikipedia: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
wiadomość z UJ: http://www.uj.edu.pl/wiadomosci/-/journal_content/56_INSTANCE_d82lKZvhit4m/10172/134381865
zebrane linki: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations
Przykładowo ANS-em zapisuje informację obecnie domyślny kompresor Apple (LZFSE), oraz open-source kompresor z Facebook (zstd), który ma aspiracje do wyparcia standardowego gzip/zlib (zip-y) jako że jest kilkukrotnie szybszy i pozwala na znacznie lepszą kompresję:
https://github.com/facebook/zstd
7-Zip z zstd: https://github.com/mcmilk/7-Zip-zstd/releases
Kodowanie ANS też jest używane m.in. w kompresji DNA, w kompresji tekstur na GPU, oraz w będącym w rozwoju otwartym kompresorze wideo z Alliance for Open Media (m.in. Google, Microsoft, Intel, ARM, NVidia, AMD, Cisco, Netflix, Amazon).
update: the Guardian już używa ZStandard zamiast zlib - https://www.theguardian.com/info/developer-bl...-compression-iinovations-brotli-and-zstandard
Tę nieoptymalność naprawia kodowanie arytmetyczne, pozwalając na lepszy stopień kompresji (operuje na dowolnych prawdopodobieństwach), jednak będąc znacznie bardziej kosztowne obliczeniowo (m.in. potrzebuje mnożenia). Jest używane m.in. we współczesnej kompresji wideo czy LZMA (7-Zip, xz).
Okazuje się że powyższy kompromis między kosztem (szybkością) a stopniem kompresji został niedawno zakończony: od 2014 roku nowe kompresory są oparte już na innym kodowaniu (ANS), pochodzącym z Uniwersytetu Jagiellońskiego - jest ono równocześnie dokładne (używa dowolnych prawdopodobieństw) i tanie obliczeniowo (nie potrzebuje mnożenia).
Koncepcyjnie od kodowania arytmetycznego różni się tym że zamiast reprezentować informację jako przedział (dwie liczby), ANS operuje bezpośrednio na pojedynczej liczbie naturalnej: która jest zwiększana ~1/p razy podczas kodowania symbolu o prawdopodobieństwie p.
W 2013 roku state-of-art dla dekodowania arytmetycznego to było ~50MB/s/rdzeń i7 (dla Huffmana ~200MB/s), obecnie analogiczne zadanie osiąga ~1500MB/s na tym samym procesorze (rzędu 30x przyspieszenie, Huffman przyspieszył do ~1000MB/s): https://sites.google.com/site/powturbo/entropy-coder
Wikipedia: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
wiadomość z UJ: http://www.uj.edu.pl/wiadomosci/-/journal_content/56_INSTANCE_d82lKZvhit4m/10172/134381865
zebrane linki: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations
Przykładowo ANS-em zapisuje informację obecnie domyślny kompresor Apple (LZFSE), oraz open-source kompresor z Facebook (zstd), który ma aspiracje do wyparcia standardowego gzip/zlib (zip-y) jako że jest kilkukrotnie szybszy i pozwala na znacznie lepszą kompresję:
https://github.com/facebook/zstd
7-Zip z zstd: https://github.com/mcmilk/7-Zip-zstd/releases
Kodowanie ANS też jest używane m.in. w kompresji DNA, w kompresji tekstur na GPU, oraz w będącym w rozwoju otwartym kompresorze wideo z Alliance for Open Media (m.in. Google, Microsoft, Intel, ARM, NVidia, AMD, Cisco, Netflix, Amazon).
update: the Guardian już używa ZStandard zamiast zlib - https://www.theguardian.com/info/developer-bl...-compression-iinovations-brotli-and-zstandard
Fajne? Ranking DIY
