Dr Jarosław Duda z Uniwersytetu Jagiellońskiego opracował innowacyjną metodę komputerowego kodowania ANS. Technika ta pozwala przyspieszyć przepływ informacji drogą elektroniczną aż do 30 razy!

Każdego dnia ludzkość produkuje ogromne ilości danych przekraczające ponad 2,5 kwintyliona bajtów. Szacuje się, że w ciągu jednej sekundy każdy z nas wytwarza 1,7 MB danych. Przepływ tak dużych ilości danych bez odpowiedniej kompresji, czyli swoistego ich zmniejszenia, by łatwiej byłoby przemieszczać się po światłowodach, trwa dłużej i zwiększa koszty. Dr Jarosław Duda z Uniwersytetu Jagiellońskiego opracował innowacyjną metodę kompresji danych, którą już nawet chciał podkraść amerykański gigant, Google.

Jak kompresuje się dane?

Kompresja danych to skomplikowany proces składający się zazwyczaj z dwóch faz. Pierwsza polega na zastosowaniu do danych pewnych upraszczających transformacji, np. wykorzystujących powtarzanie się pewnych sekwencji znaków w pliku. W drugiej fazie dochodzi do tzw. kodowania entropijnego, zgodnie z którym powszechne symbole niosą mniej informacji niż te rzadkie. Dla przykładu – symbol o prawdopodobieństwie wystąpienia 1/2 niesie ze sobą jeden bit informacji, a symbol o prawdopodobieństwie 1/8 już trzy.

Standardowo używaną metodą kodowania jest kodowanie Huffmana, w którym symbole bezpośrednio są zapisywane jako ciągi bitów np. „a” jako „101”. Jest to tania i prosta metoda, ale mało optymalna dla symboli o prawdopodobieństwie niebędącym potęgą 1/2. Znacznie dokładniejsze jest tzw. kodowanie arytmetyczne, które jest jednak o rząd wielkości kosztowniejsze od kodowania Huffmana.

Nowy język komputerów i smartfonów

Z pomocą przyszło nowatorskie rozwiązanie opracowane przez dr Jarosława Dudę z Instytutu Informatyki i Matematyki Komputerowej UJ. W latach 2006-2014 polski naukowiec stworzył nową rodzinę kodowań entropijnych, opartych na asymetrycznych systemach liczbowych (ANS), która często jest także nazywana po prostu „kodowaniem z UJ”. Pozwala ono osiągnąć stopień kompresji z kodowania arytmetycznego przy koszcie obliczeniowym zbliżonym do kodowania Huffmana.

Kodowanie ANS pozwala na kompresję danych na komputerach, smartfonach i innych urządzeniach elektronicznych. Już teraz stanowi jeden z fundamentów dzisiejszego świata i jest używane w produktach Apple, Facebooka, Linuksa czy Google oraz uczone na uniwersytetach na całym świecie”, np. z Berkeley https://youtu.be/pPyOlGvWoXA?t=8103

Dr Duda od 2014 r. pomagał Google w adaptacji ANS do kompresji plików wideo. Nowa metoda tak bardzo zainteresowała giganta z Mountain View, że ten próbował ją opatentować w 2015 r. Na szczęście, w 2018 r. wniosek patentowy Google został odrzucony, więc ANS może być używane bez zagrożeń prawnych.

Przyszłe zastosowania

Kodowanie ANS ułatwia życie nam wszystkim. Zostało one zaadaptowane w nadchodzącym wielkimi krokami nowym formacie plików graficznych – JPEG XL. Wszystkie zdjęcia zapisane w formacie JPEG XL będą trzy razy mniejsze, bez jakiejkolwiek utraty jakości obrazu. To z kolei oznacza przyspieszenie ich przesyłania, dużo lepszą jakość grafik na portalach społecznościowych i szybsze otwieranie stron internetowych. Format ten zmniejszy także zużycie energii i wydłuży żywotność baterii naszych smartfonów.

Obecnie nieświadomie używamy ANS m.in. w:

– kompresorze Facebook Zstandard który powszechnie zastąpił podstawowy „zip” m.in. w systemie
Linux,
– Apple LZFSE którym zapisuje iPhone, Mac, iWatch,
– sekwencje genetyczne są zwykle zapisane kompresorem CRAM z SAMtools,
– Google Draco dla grafiki 3D, używany m.in. przez Pixar,
– kompresor Kraken popularny w grach komputerowych, sprzętowy w Sony Playstation 5,
– JPEG XL niedługo zastąpi JPEG z 1992, m.in. zmniejszając ok. 3 razy wielkość zdjęć w naszych
telefonach.

Dzięki metodzie z UJ 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.

Leave a Reply

FUNDACJA IMPACT
UL. STAWKI 3A LOK. 47
00-193 WARSZAWA
POLSKA
KRS: 0000611651