Skocz do zawartości
elenorf

Kodowanie Huffmana wypierane przez ANS pochodzące z Polski (m.in. Apple, Facebook, Google)

Rekomendowane odpowiedzi

Chyba wszyscy informatycy słyszeli o kodowaniu Huffmana - jest ono szybkie ale niedokładne (przybliża prawdopodobieństwa potęgami 1/2), lepszy stopień kompresji daje kodowanie arytmetyczne, tyle że jest znacznie bardziej kosztowne obliczeniowo (potrzebuje mnożenia).

Okazuje się że od 2014 nowe kompresory są oparte już na innym kodowaniu (ANS), które pochodzi z Uniwersytetu Jagiellońskiego - jest ono dokładne i tanie obliczeniowo (nie potrzebuje mnożenia):

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

materiały: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations

 

Przykładowo obecnie domyślny kompresor Apple (LZFSE), czy open-source kompresor z Facebook (Zstandard), 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

ZSTD.png

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

A ten obrazek to skąd? bo ciężko to zrozumieć bez opisu.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Obrazek to z open source kompresora Facebook zstd - po lewej masz szybkość kompresji (kropki to wybrany parametr od 1 do 22): od np. 4x szybciej niż standardowy zlib (zip-y), aż do znacznie lepszej maksymalnej kompresji ... potem dekodowanie jest ze 3x szybsze niż dla zip.

Jest 7-zip z zstd: https://github.com/mcmilk/7-Zip-zstd/releases

 

Na poziomie kodowania "entropijnego" (serce kompresorów), w 2013 state-of-art dla dekodowania Huffmana (m.in. zip, rar, jpg, png, mp3, pdf) to było ~200MB/s rdzeń i7, dla arytmetycznego (lepsza kompresja, m.in. współczesne kompresory wideo, LZNA (7-zip, xz)) rzędu 50MB/s.

Obecnie implementacje Huffmana przyśpieszyły do ~1000MB/s na tym samym procesorze ... a ANS (kompresja jak w arytmetycznym) do ~1500MB/s.

Czyli ~30x przyśpieszenie na poziomie software w ciągu 3 lat dla podstawowej czynności: https://sites.google.com/site/powturbo/entropy-coder

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

widać nie zaglądałeś do linków ;)

Przejrzałem każdy, ale nie wchodziłem w podstrony, a na wierzchu nie zauważyłem. Temat może i ciekawy, ale nie mam tyle czasu, żeby tropić skąd autor zajumał.

 

Obrazek to z open source kompresora Facebook zstd - po lewej masz szybkość kompresji (kropki to wybrany parametr od 1 do 22): od np. 4x szybciej niż standardowy zlib (zip-y), aż do znacznie lepszej maksymalnej kompresji ... potem dekodowanie jest ze 3x szybsze niż dla zip.

Tyle to umiem odczytać z etykiet. Ale skąd się np. biorą różne kropki w ramach tego samego kompresora, czym się od siebie różnią?

 

Na poziomie kodowania "entropijnego" (serce kompresorów), w 2013 state-of-art dla dekodowania Huffmana (m.in. zip, rar, jpg, png, mp3, pdf)

Żadnym ekspertem od kompresji nie jestem, ale uczyli mnie, że współcześnie kody Huffmana to już raczej nie rdzeń a bardzie dodatkowa kompresja pomocnicza. Tak, że na pewno postęp, ale raczej nie przełom.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Tyle to umiem odczytać z etykiet. Ale skąd się np. biorą różne kropki w ramach tego samego kompresora, czym się od siebie różnią?

Jak napisałem, 22 kropki odpowiadają ustawieniu które wybierasz: od -1 do -22. Tradeoff między kosztem i stopniem kompresji.

W gzip miałeś 9 możliwości: od -1 do -9, więc jest 9 kropek.

Z oryginalnego artykułu o zstd: https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/

"At Facebook, we find the default level 3 suitable for many use cases, but from time to time, we will adjust this slightly depending upon what our bottleneck is (often we are trying to saturate a network connection or disk spindle); other times, we care more about the stored size and will use a higher level."

 

Żadnym ekspertem od kompresji nie jestem, ale uczyli mnie, że współcześnie kody Huffmana to już raczej nie rdzeń a bardzie dodatkowa kompresja pomocnicza. Tak, że na pewno postęp, ale raczej nie przełom.

Kodowanie entropijne (Huffman, arytmetyczne, teraz ANS) to jest jakby serce kompresora.

Wcześniej masz różne transformacje, jak Lempel-Ziv w zip, rar, zstd: kopiujesz powtarzające się podciągi, np. https://pl.wikipedia.org/wiki/LZ78

Potem zliczasz wystąpienia symboli żeby oszacować prawdopodobieństwa (modelowanie statystyczne) i na końcu "pompujesz" tą całą informację przez koder entropijny - który optymalnie powinien użyć log(1/p) dla symbolu o prawdopodobieństwie p (zna zamodelowane prawdopodobieństwa).

Huffman używa pełnych bitów, przybliżając prawdopodobieństwa potęgami 1/2 - dając nieoptymalną kompresję.

Arytmetyczne i ANS używają praktycznie dokładnych prawdopodobieństw - potrafią operować na ułamkowych bitach dzięki specjalnemu buforowi (przedział w arytmetycznym, jedna liczba naturalna w ANS).

 

Przed 2014 to finalne "przepompowanie informacji" było Huffmanem (szybkie ale niedokładne) lub kodowaniem arytmetycznym (dokładne ale kosztowne).

Natomiast nowe kompresory robią to ANS który jest dokładny i szybki ... no i z Polski.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Co by nie mówić szybka kompresja zstd w 7zip jest na prawdę szybka. Cache przeglądarki z ramdysku (szybciej jest pakować niż zrobić zwykłą kopię wielu drobnych plików) zamiast 15-20s zrzuca się w 5s.

Szkoda że to jeszcze nie weszło w główną gałąź programu i ciężko szerzej zastosować.

 

Są jakieś linuksowe implementacje wspomagające rsync-a lub tar-a?

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Właśnie Google próbuje patentować podstawowe zastosowanie ANS - 400+ komentarzy:

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Polskie kodowanie od kilku miesięcy jest w jądrze Linuxa (od 4.14): https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.14-Zstd-Pull

Niedługo będzie w naszych mailach - trwa standaryzacja MIME ( https://en.wikipedia.org/wiki/MIME ): https://datatracker.ietf.org/doc/draft-kucherawy-dispatch-zstd/

 

Szkoda że nie ma jakiegoś wideo które łatwo by je tłumaczyło ...

 

ps. patent gugła wstępnie odrzucony, ale oczywiście walczą dalej: https://encode.ru/threads/2648-Published-rANS-patent-by-Storeleap?p=54339&viewfull=1#post54339

Edytowane przez elenorf

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Rzeczywiście, coś przycięło. Spora burza w necie, np.

https://yro.slashdot.org/story/18/06/11/2159218/inventor-says-google-is-patenting-his-public-domain-work

 

I pojawił się wykład Dudy, od połowy jest o ANS (slajdy: https://www.dropbox.com/s/axji416fo8cm4u6/sfi.pdf )

Edytowane przez elenorf

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Ostatnio Free Software Foundation wsparło walkę z patentem:

Po czym Electronic Frontier Foundation poinformowało że jest non-final rejection, prosząc Google o zaprzestanie dalszego starania o ten patent: https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public

W czerwcu sprawa doszła na górę redita (~25k): https://old.reddit.com/r/programming/duplicates/8q3kp8/inventor_says_google_is_patenting_work_he_put_in/

Teraz znowu (~30k): https://old.reddit.com/r/technology/duplicates/9c7kw6/google_is_trying_to_patent_use_of_a_data/

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jest wideo tutorial o ANS:

I wykład z Berkeley:

Edytowane przez elenorf

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

×
×
  • Dodaj nową pozycję...