Przejdź do głównej treści

Widok zawartości stron Widok zawartości stron

Wiadomości

Nawigacja okruszkowa Nawigacja okruszkowa

Widok zawartości stron Widok zawartości stron

Używasz Facebooka lub Apple’a? Twoje dane są zapisane kodowaniem z UJ

Używasz Facebooka lub Apple’a? Twoje dane są zapisane kodowaniem z UJ

W dzisiejszych czasach dane, których używamy są zwykle wcześniej poddane kompresji, co pozwala obniżyć koszt ich przechowywania i przesyłania. Przykładowo, stratna kompresja wideo, używana podczas oglądania filmów, pozwala zmniejszyć oryginalną wielkość pliku nawet tysiąc razy.

Kompresja danych jest skomplikowanym procesem złożonym zwykle z dwóch faz. Pierwsza polega na zastosowaniu do danych pewnych upraszczających transformacji, przykładowo, wykorzystujących powtarzanie się pewnych sekwencji znaków w pliku. W fazie drugiej uzyskany ciąg symboli jest poddawany tzw. kodowaniu entropijnemu, korzystającemu z faktu, że często występujące ciągi symboli niosą ze sobą mniej informacji niż te rzadkie. I tak symbol o prawdopodobieństwie wystąpienia 1/2 niesie ze sobą jeden bit informacji, zaś symbol o prawdopodobieństwie 1/8 - już trzy. Standardowo używa się tu kodowania Huffmana, zapisującego bezpośrednio symbole jako ciągi bitów, np. „a” jako „101”. Choć tanie obliczeniowo, nie jest jednak optymalne dla symboli o prawdopodobieństwie niebędącym potęgą 1/2. Przykładowo, mimo że symbol o prawdopodobieństwie 0,99 niesie tylko około 0,014 bita informacji, to kodowanie Huffmana musi tu zużyć przynajmniej 1 bit. Ten problem suboptymalności naprawia inne kodowanie - arytmetyczne, radzące sobie z ułamkowymi bitami dzięki akumulacji informacji w pewnego rodzaju buforze. Jest ono jednak o rząd wielkości kosztowniejsze od poprzedniego.

To że kompromis pomiędzy kosztem obliczeniowym i stopniem kompresji nie jest już konieczny, zawdzięczamy dr. Jarosławowi Dudzie z Instytutu Informatyki i Matematyki Komputerowej UJ, który w latach 2006-2014 wprowadził nową rodzinę kodowań entropijnych opartą na asymetrycznych systemach liczbowych (ang. Asymmetric Numeral Systems – ANS). Uogólniają one zwykłe systemy pozycyjne, takie jak dwójkowy czy dziesiętny. W rezultacie otrzymujemy kodowanie o stopniu kompresji podobnym jak w kodowaniu arytmetycznym, przy koszcie obliczeniowym zbliżonym do kodowania Huffmana.

Kompresory wykorzystujące ANS zaczęły powstawać w 2014 roku, zaś w połowie kolejnego roku Apple wprowadził oparty na tym schemacie kompresor LZFSE, który stał się domyślną opcją kompresji dla iPhone’a i Maca. W sierpniu 2016 roku Facebook zademonstrował swój otwarty kompresor Zstandard, także używający ANS, który ma szansę zastąpić powszechnie używany kompresor gzip ze względu na lepszą szybkość i stopień kompresji. ANS użyto też w wersji rozwojowej nowego, opracowywanego przez tzw. Alliance for Open Media (m.in. Adobe, Amazon, AMD, ARM, Cisco, Google, Intel, Microsoft, Mozilla, Netflix, Nvidia), kompresora wideo, który w przyszłości będzie mógł być stosowany na przykład w serwisie YouTube. Tego kodowania używa również najbardziej powszechna w tym momencie kompresja DNA: CRAM 3.0, wchodząca w skład popularnego pakietu do obróbki danych genetycznych SAMtools.

 

Szczegóły:

www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource
code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/
en.wikipedia.org/wiki/Asymmetric_Numeral_Systems

Polecamy również
Naukowcy UJ otrzymają ponad 73 mln zł na realizację badań podstawowych

Naukowcy UJ otrzymają ponad 73 mln zł na realizację badań podstawowych

Studenci WMiI UJ triumfatorami konkursu im. Józefa Marcinkiewicza

Studenci WMiI UJ triumfatorami konkursu im. Józefa Marcinkiewicza

Badacze UJ wśród pierwszych laureatów konkursu MINIATURA 8

Badacze UJ wśród pierwszych laureatów konkursu MINIATURA 8

Wybitni młodzi naukowcy z UJ laureatami konkursu START FNP

Wybitni młodzi naukowcy z UJ laureatami konkursu START FNP

Widok zawartości stron Widok zawartości stron