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
