- Czym jest kompresja danych i dlaczego jest taka ważna we współczesnym świecie?
dr Jarosław Duda z Uniwersytetu Jagiellońskiego: - Kompresja to po prostu efektywny zapis danych – przedstawienie takiej informacji w miarę krótkim ciągiem bitów: zer i jedynek. Taka optymalizacja zapisu jest względnie niedroga, dając oszczędności dla wielkości plików, kosztu i czasu ich przesłania np. przez Internet.
W związku z tym prawie wszystkie używane, przesyłane przez nas dane są dzisiaj poddane kompresji, przykładowo dla wideo zmniejszając takie pliki nawet do 1000 razy, co jest kluczowe np. dla wideokonferencji. Łatwo dostępne dziś oglądanie wideo w rozdzielczości 8K bez kompresji wymagałoby kilkuset typowych łączy internetowych.
- Język polski nie jest szczególnie znany na świecie, ale polski „język komputerowy” wprost przeciwnie. Czym jest ANS?
- Ludzkie języki, np. polski, angielski, pozwalają nam przekazywać treści w ciągach słów, które zapisujemy jako ciągi liter. Kod genetyczny sterujący naszymi organizmami też zwykle przedstawiamy w postaci ciągu liter.
Zamiast liter komputery przekazują treści w postaci ciągów bitów: zer i jedynek, np. 1001101010110. ANS jest przykładem tzw. kodowania entropijnego, które jest analogiczne do tłumaczenia ciągów podstawowych liter (bitów) na ciągi słów (symboli, zdarzeń) – już mających konkretne znaczenia.
Trudnością jest to, że częste słowa, symbole, zdarzenia dla oszczędności powinny mieć krótszy zapis niż te rzadkie. Idealnie: dwukrotnie rzadsze powinny używać zapis o 1 bit dłuższy, prowadząc do optymalnej długości zapisu danej tzw. entropią Shannona.
Historycznie podstawowa metoda to kodowanie Huffmana z 1952 roku – bezpośrednio tłumacząca ciągi bitów na symbole np. 0 oznacza A, 10 to B, a 11 to C. Jest to tanie obliczeniowo ale zwykle nieoptymalne - ponieważ symbol może nieść ułamkową ilość np. 1/10 bita informacji, podczas gdy Huffman potrzebowałby dla niego użyć przynajmniej 1 bit. Naprawiało to zapoczątkowane ok. 1976 roku tzw. kodowanie arytmetyczne, ale znacznie większym kosztem obliczeniowym (wolniejsze, potrzebujące więcej energii, sprzętu).
Dopiero polski ANS pozwolił połączyć ich zalety – pracując z ułamkowymi bitami, jak kodowanie arytmetyczne, ma koszt obliczeniowy podobny jak kodowanie arytmetyczne. Dzięki temu od 2015 roku nowe kompresory już zwykle są budowane na ANS i raczej tak już pozostanie.
- Jaka jest historia powstania ANS? Kiedy rozpoczęły się prace?
- ANS to jest właściwie rodzina metod. Pierwszy wariant (uABS) wprowadziłem w 2006 roku w swojej pracy magisterskiej z fizyki (trzeciej po informatyce i matematyce) – potrzebowałem dobrą metodę, nie znałem wtedy kodowania arytmetycznego, więc zrobiłem po swojemu. ANS to Asymmetric Numeral Systems – czyli asymetryczne systemy liczbowe. Wyszedłem ze zwykłych powszechnie używanych systemów liczbowych, jak dwójkowy w komputerach czy dziesiątkowy w życiu codziennym – one są optymalne, gdy wszystkie cyfry są tak samo częste. ANS intuicyjne „uasymetrycznia” je do dowolnych wybranych częstości cyfr. Szybkość zawdzięcza tej prostocie, jest to dość naturalny sposób, gdy się go już pozna: zapisz informację w jedną liczbę, zamiast w przedział w kodowaniu arytmetycznym.
Praktyczniejszy wariant tANS (stablicowany) wprowadziłem w 2007, były wtedy jakiejś pierwsze dyskusje, ale dopiero pod koniec 2013 roku jego zalety zostały docenione przez praktyka, Yanna Colleta, który ok. 2 lata później wprowadził kompresor Zstandard – obecnie wypierający klasyczny „zip” dzięki byciu 3-5 razy szybszym, też pozwalając na znacznie lepszą kompresję. Jest on oficjalnie używany przez dziesiątki firm - zaczynając od Facebook, Amazon, IBM, jest także używany w jądrze systemu Linux. Zainspirował też Apple do kompresora LZFSE, który jest obecnie podstawowym dla ich sprzętu (iPhone, Mac, iWatch). Wariantu tANS używa również popularny w grach komputerowych kompresor Oodle Kraken, m.in. przetwarzający dane w sercu konsoli Sony Playstation 5.
Później w 2013 wprowadziłem wariant rANS (przedziałowy), którym m.in. prawdopodobnie będzie zapisany materiał genetyczny osoby poddającej się sekwencjonowaniu DNA (kompresor CRAM), jest on także użyty w Google Draco - kompresorze 3D używanym m.in. przez Pixar. Używa go też bliski standaryzacji ISO kompresor JPEG XL, rozwijany głównie przez Google, który prawdopodobnie w końcu wyprze używany przez nas wszystkich do zapisu zdjęć i obrazków JPEG z 1992 – oszczędzając miejsce ok. 3 razy, przyspieszając ładowanie stron i dodając brakujące funkcje jak HDR.
- Kto obecnie korzysta z ANS?
- Już praktycznie każdy użytkownik elektroniki ma dane zapisane tą polską metodą poprawiającą działanie naszych urządzeń. Stała się ona podstawowym sposobem zapisywania informacji i przesyłania jej po całym świecie, a jej popularność tylko rośnie.
Używamy obecnie ANS przykładowo:
● w naszych smartfonach, używających systemów opartych na Linux, którego jądro zapisuje teraz wspomnianym kompresorem Facebook Zstandard opartym na tANS,
● użytkownicy Apple iPhone, Mac, iWatch mają dane zapisane LZFSE też na tANS,
● grając w gry komputerowo często nieświadomie używamy Oodle Kraken lub Zstandard na tANS,
● poddając się sekwencjonowaniu DNA tłumaczymy ten nasz kod biologiczny na rANS w kompresorze CRAM,
● oglądając nowy film np. Pixar, prawdopodobnie powstał z użyciem Google Draco na rANS,
● niedługo otwierając strony czy robiąc zdjęcia będziemy używać rANS w JPEG XL.
- Jakie są największe różnice pomiędzy ANS a starszymi rodzajami kodowania? Jakie parametry są najważniejsze, jeżeli mówimy o nowoczesnym kodowaniu?
- Poprzednie metody wymagały kompromisu: kodowanie Huffmana jest tanie obliczeniowo, ale nieoptymalne z perspektywy kompresji. Kodowanie arytmetyczne może być optymalne, ale jest znacznie droższe obliczeniowo. Obecnie zastępuje je polski ANS dzięki łączeniu tych kluczowych zalet: pozwalając na to, co kodowanie arytmetyczne, ale nawet do 30 razy szybciej.
- Czy ANS jest powiązane w jakiś sposób z bezpieczeństwem danych użytkowników komputerów i telefonów?
- Sama kompresja nie ma bezpośredniego wpływu na bezpieczeństwo, aczkolwiek tANS daje możliwość przy okazji szyfrować tak przetwarzane dane – właśnie mamy grant, w którym to badamy, licząc, że w przyszłości będzie używane dla taniej kompresji plus szyfrowania szczególnie danych ze zdalnych sensorów IoT.
- Jak będzie wyglądać przyszłość narzędzi do kodowania?
- Wytwarzamy niewyobrażalne ilości danych, z roku na rok coraz więcej – np. wideo 4K czy nawet 8K, powoli spełnia się wizja IoT z komunikacją wszelkich urządzeń dookoła nas dzięki m.in. 5G, wyłaniają się kolejne zastosowania, jak rzeczywistość wirtualna/rozszerzona, autonomiczne pojazdy etc. Kompresja danych jest kluczowa, żeby sobie radzić z przesyłaniem i zapisywaniem tego oceanu informacji.
Polski sposób zapisu ANS pozwolił poprawić jej kluczowe parametry – oszczędzając czas, łącza komunikacyjne, energię np. baterię smartfonu, nośniki pamięci, koszt sprzętu – dzięki temu stając się tym podstawowym języki elektroniki, smartfonów, komputerów, a z czasem jego znaczenie będzie tylko rosło.
Materiał partnera: ImpactCEE