Informatyk z UJ wynalazł popularną metodę zapisywania danych

Podczas gdy ludzie porozumiewają się językami, np. polskim czy angielskim, które pozwalają przedstawić jakąś treść w postaci ciągu liter, urządzenia elektroniczne w tym celu używają kodowań - przedstawiając treści w postaci ciągów bitów: 0 i 1. Od kilku lat podstawowym używanym kodowaniem jest ANS pochodzący z Uniwersytetu Jagiellońskiego. W ten sposób zapisują dane - nawet o tym nie wiedząc - użytkownicy m.in. Apple, Facebooka, Google’a, Linuxa, gier komputerowych, sekwencji genetycznych, grafik 3D, a niedługo też m.in. zdjęć w telefonach, bo szykuje się JPEG XL - oparty także na tej polskiej metodzie. Jak działa kompresja ANS?

Bronisław Tumiłowicz, "Przegląd": Platforma Nauki umieściła pańską metodę kompresji na pierwszym miejscu rankingu największych osiągnięć ostatnich czasów. To zaskakujące, że właściwie nic o tym nie było słychać.

Dr Jarosław Duda: - Nie wiedziałem o tym, ale właśnie znalazłem tę informację - bardzo dziękuję.

Czy kompresja danych, którą pan wzbogacił i usprawnił, jest rzeczywiście tak bardzo ważna dla technologii informatycznych?

- Gdyby nie kompresja przesyłanych danych, sieć i komputery szybko by się zapchały. Kompresja to po prostu efektywny zapis danych - przedstawienie informacji możliwie 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 i przesyłane przez nas dane są dzisiaj poddane kompresji. Przykładowo dla wideo zmniejsza się takie pliki nawet 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.

Ale pan nie wymyślił kompresji jako takiej?

- Oczywiście, że nie. ANS to nowy sposób zapisu na ciągi bitów, tłumaczenie na ciągi symboli mających konkretne znaczenia. W kompresji trudnością jest to, że często pojawiające się symbole niosą mniej informacji niż te rzadkie. Historycznie podstawowa metoda to kodowanie Huffmana z 1952 r., bezpośrednio tłumacząca ciągi bitów na symbole np. 0 → A, 10 → B, 11 → C. Jest to tanie obliczeniowo, ale zazwyczaj nieoptymalne, ponieważ symbol może nieść ułamkową ilość, np. jedną dziesiątą bita informacji, podczas gdy Huffman potrzebowałby dla niego użyć przynajmniej 1 bit. Tę "rozrzutność" naprawiało zapoczątkowane ok. 1976 r. tzw. kodowanie arytmetyczne, ale znacznie większym kosztem obliczeniowym - było wolniejsze, potrzebowało więcej energii i sprzętu. Dopiero polski ANS pozwolił połączyć zalety tamtych metod - pracując z ułamkowymi bitami, jak kodowanie arytmetyczne, ma koszt obliczeniowy podobny do kodowania Huffmana; pozwala na to samo, co kodowanie arytmetyczne, ale nawet do 30 razy szybciej. Dzięki temu od 2015 r. nowe kompresory są już zwykle budowane na ANS i raczej tak już pozostanie.

Jak pan wpadł na pomysł ANS?

- To było w 2006 r., gdy wprowadziłem pierwszy wariant kodowania (uABS) w swojej pracy magisterskiej z fizyki (trzeciej po informatyce i matematyce). Potrzebowałem dobrej metody, a nie znałem jeszcze wtedy kodowania arytmetycznego, więc zrobiłem to 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. Ogólniejszy ANS intuicyjne "uasymetrycznia" je do dowolnych wybranych częstości cyfr. Szybkość zawdzięcza tej prostocie, jest to dość naturalny sposób, gdy już go się pozna: zapisz informację w jedną liczbę, zamiast w przedział w kodowaniu arytmetycznym. ANS jest dziś już właściwie rodziną metod. Praktyczniejszy wariant tANS (stablicowany) wprowadziłem w 2007 r., były wtedy jakiejś pierwsze dyskusje, ale dopiero pod koniec 2013 r. jego zalety zostały docenione przez praktyka: Yanna Colleta, który mniej więcej dwa lata później wprowadził kompresor Zstandard - obecnie wypierający klasyczny "zip", ponieważ jest od trzech do pięciu razy szybszy i pozwala na znacznie lepszą kompresję.

Kto teraz używa metody ANS?

- Sam Zstandard (na tANS) jest oficjalnie używany przez dziesiątki firm, zaczynając od Facebooka, Amazona, IBM. Używa go także jądro systemu Linux, które zarządza m.in. naszymi smartfonami. Zainspirował również Apple do stworzenia 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. W 2013 r. wwprowadził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 wykorzystywany w Google Draco w kompresorze 3D używanym m.in. przez Pixar. Stosuje 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 r., mniej więcej trzykrotnie zmniejszając wielkwości plików, oszczędzając miejsce i przyspieszając ładowanie stron, dodając także brakujące funkcje, jak przeźroczystość czy HDR (High Dynamic Range) dający obraz o dużej różnicy pomiędzy ciemnymi a jasnymi tonami.

A gdzie tu jest Polska, gdzie Uniwersytet z Krakowa, gdzie Duda, dziś bardzo znane nazwisko? Przecież dzięki pańskiej metodzie wszyscy możemy teraz zapisywać więcej plików, taniej i szybciej je wczytywać i przesyłać, oszczędzając też na koszcie infrastruktury i energii elektrycznej.

- Polska owszem może się pochwalić tym, że praktycznie wszyscy mają dziś dane zapisane naszą metodą, ale zbudowanie tej świadomości jest dość trudne. Może gdyby np. w Cyberpunku, komputerowej fabularnej grze akcji stworzonej przez Polaków, jakoś nawiązali... Wszyscy piszą po prostu ANS, czasami wspominając autora czy historię z Google - np. w wykładzie w Berkeley. Jest kilka wariantów ANS i to ja je wszystkie wprowadziłem (uABS w 2006 r., tANS w 2007 r., rANS w 2013 r.). Cytują w artykułach, czasami wspominają mnie w dokumentacji oprogramowani. I to raczej wszystko.

To porażające - wszyscy specjaliści wiedzą, ludzie i firmy masowo korzystają, a pan nie należy do najbogatszych wynalazców na świecie. Czy opracowanie tej metody w ogóle się panu opłaciło?

- Zyskałem tylko bezcenną satysfakcję. Liczyłem na współpracę z Google, ale skończyło się inaczej. Teraz trochę dorabiam do pensji akademickiej jako konsultant, ale zajmuję się raczej inną tematyką.

Nie próbował pan opatentować swojej metody?

- Do opatentowania i spieniężenia metody potrzebny jest zespół, a zawsze byłem z tym sam. Nawet gdy cały świat tego używa, nikt w Polsce nie pomoże. W związku z tym od wymyślenia metody w 2006 r. do docenienia w 2014 r. minęło zbyt dużo czasu dla prób patentowania. W sumie dobrze się stało - opatentowany ANS pewnie przez 20 lat albo więcej byłby praktycznie nieużywany, jak AC, którego on wypiera, a ANS już jest dosłownie wszędzie.

Gratulujemy więc panu satysfakcji. A jak się rysuje przyszłość kompresji danych i ich kodowania? Postęp technologiczny jest coraz szybszy.

- 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, m.in. dzięki 5G, wyłaniają się kolejne zastosowania, jak rzeczywistość wirtualna/rozszerzona, autonomiczne pojazdy itd. Kompresja danych jest kluczowa, aby 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 stał się podstawowym językiem elektroniki, smartfonów, komputerów, a z czasem jego znaczenie będzie tylko rosło.

Rozmawiał Bronisław Tumiłowicz