Kodowanie po krakosku

Wynalazek polskiego matematyka wielokrotnie przyspieszył przetwarzanie danych. Korzystają z niego już wszyscy internetowi giganci.

01.03.2021

Czyta się kilka minut

Bulwary wiślane w Krakowie, maj 2020 r. / BEATA ZAWRZEL / REPORTER
Bulwary wiślane w Krakowie, maj 2020 r. / BEATA ZAWRZEL / REPORTER

Osią serialu „Dolina Krzemowa” (HBO, 2014-19) było wynalezienie przez głównego bohatera, genialnego informatyka Richarda Hendricksa, rewolucyjnej metody kompresji danych. To fikcyjna historia, ale w prawdziwym świecie podobny wynalazek powstał. Określa się go mianem ANS – czyli kodowania opartego na asymetrycznych systemach liczbowych (ang. Asymmetric Numeral Systems). Autorem tego systemu reprezentacji danych jest polski informatyk i matematyk Jarosław Duda z Uniwersytetu Jagiellońskiego. Dziś z jego rozwiązań w swoich produktach korzystają giganci Doliny Krzemowej, tacy jak Apple, Facebook i Google. Dzięki temu wszyscy możemy zapisywać więcej plików, taniej i szybciej je wczytywać i przesyłać.

Działanie tego systemu opiera się na dość zawiłym pomyśle matematycznym, ale ogólne założenia są stosunkowo proste.

Język maszyn

Wyobraźmy sobie język, w którym powiedzieć można tylko „tak” i „nie”. Czy jakakolwiek rozmowa byłaby w nim w ogóle możliwa? Mogłoby się wydawać, że nie, ale to właśnie tego rodzaju systemem binarnym porozumiewają się komputery. W wystarczająco długim ciągu złożonym wyłącznie z wartości 0 i 1 zapisać można bowiem wszystko: od liczb i słów, przez dźwięki, aż po obrazy i filmy. Kluczem jest odpowiednie kodowanie, czyli przypisanie sekwencjom zer i jedynek konkretnego znaczenia.

Każde słowo czy liczba, aby być zrozumiałe dla komputera, musi zostać przełożone na system binarny. Weźmy np. liczbę 42. Po jej prostym przetłumaczeniu z systemu dziesiątkowego na binarny otrzymamy ciąg 101010. Aby zapisać tę liczbę, potrzebujemy sześciu bitów – czyli sześciu pozycji, na których stoją zera lub jedynki. Bardziej skomplikowane jest kodowanie słów. Każdej literze musimy bowiem arbitralnie przypisać konkretną wartość. Aby zużyć możliwie jak najmniejszą liczbę bitów – co sprzyja szybkości przetwarzania i przesyłu danych – należy wziąć przy tym pod uwagę częstość występowania poszczególnych liter.

Dla przykładu, litera A jest używana znacznie częściej niż litera F. W tym tekście znajduje się kilkaset liter A i jedynie kilkadziesiąt liter F (średnio w polskich tekstach A występuje aż 30 razy częściej od F). Częstsze litery powinny być zakodowane krótszym ciągiem bitów, a rzadsze, jako mniej przewidywalne, dłuższym. Np. jeśli dana litera występuje średnio co cztery pozycje, powinna dostać dwa bity, jeśli co szesnaście – cztery bity. Założenie to zgodne jest z tzw. entropią statystyczną, określaną również jako entropia Shannona, od nazwiska uczonego, który położył podwaliny pod matematyczną teorię informacji.

Entropię często przedstawia się jako miarę nieporządku, choć lepiej mówić, że to miara tego, jak bardzo nie znamy dokładnego stanu układu, albo miara naszej niewiedzy na temat tego, który z możliwych stanów zrealizuje się w rzeczywistości. Entropia pozwala dokładnie zmierzyć np. to, jak bardzo możemy skompresować daną wiadomość, by nadal przekazywała określone informacje i była zrozumiała. Wszystko to zaś wiąże się z prawdopodobieństwem. W naszym przykładzie A występuje znacznie częściej niż F – a więc ta druga litera jest mniej prawdopodobna. Jej wartość informacyjna jest większa niż w przypadku litery A, ale jednocześnie koszt jej zapisu jest wyższy.


Czytaj także: Ewelina Burda: Kodujące dziewczyny


Zależność tę można próbować przetłumaczyć na życie codzienne, w którym również zdarzenia czy zjawiska rzadkie niosą więcej informacji niż typowe (jednocześnie ich opis wymaga więcej miejsca). Pomyślmy choćby o idei znaków szczególnych, wpisywanych niegdyś do dowodów osobistych: aby spełniały swoją funkcję, czyli dobrze informowały o czyjejś tożsamości, muszą być czymś rzadkim. Płeć ludzką można w większości przypadków bez trudu wyrazić przy pomocy jednego bitu – zresztą tak się robi w dokumentach tożsamości. Ale nie jest to wyjątkowo cenna informacja, jeśli chcemy zidentyfikować konkretną osobę. Gdy zaś szczegółowo opiszemy czyjś tatuaż albo położenie i kształt charakterystycznego pieprzyka, to z jednej strony powstanie dłuższy tekst (pomyślmy, na ile różnych sposobów można dokonać opisu pieprzyka!), ale też znacznie większa będzie jego zawartość informacyjna.

Wnioski z rozmyślań Shannona zastosowano w opracowanym w 1952 r. kodowaniu Huffmana, w którym np. literę A zapisujemy jako ciąg bitów 010, a F jako 1001110. Metoda Huffmana jest prosta, ale optymalna tylko wtedy, jeśli litery niosą jeden, dwa, trzy lub więcej pełnych bitów informacji. W praktyce jednak częsta litera może nieść zaledwie pół lub nawet mniej bita informacji – więc przydzielenie jej pełnych bitów byłoby marnotrawstwem. Przykładowo litera o prawdopodobieństwie występowania w tekście 0,99 niosłaby tylko ok. 0,014 bita informacji, podczas gdy kodowanie Huffmana potrzebowałoby dla niej całego bitu. Operowanie na takich ułamkowych bitach wymaga grupowania liter – akumulowania ich informacji przed zapisaniem, np. z dwóch zawierających po pół bita do zapisania w jednym: jako 0 lub 1. Jeśli A jest w jakimś tekście bardzo częste, chciałoby się zapisać parę AA jako jeden bit, np. 0, zamiast zużywać po całym bicie dla każdej takiej litery.

Ułamek bita

Na taką możliwość zwrócił uwagę już sam Shannon. Drogę do praktycznych metod operujących ułamkowymi bitami otwarły dopiero prace Roberta Fano i Petera Eliasa w latach 50. i 60. Na podstawie ich badań w latach 70. udało się opracować tzw. kodowanie arytmetyczne i rozpocząć erę jego rozwoju. Choć bardziej ekonomiczne, jest ono rzadko używane, ponieważ generuje większe problemy obliczeniowe (co obciąża komputery), a liczne ograniczenia patentowe opóźniły jego powszechne użycie o kilka dziesięcioleci. Idealnym rozwiązaniem byłoby więc połączenie zalet obu metod: możliwości operowania na ułamkowych ­bitach kodowania arytmetycznego z niskim kosztem obliczeniowym kodowania Huffmana. Właśnie ta sztuka udała się w 2006 r. Jarosławowi Dudzie.

Krakowski naukowiec wpadł na pomysł, gdy przygotowywał pracę magisterską z fizyki. Pracował wówczas nad możliwością zwiększenia pojemności dysku twardego poprzez zagęszczenie siatki kropek magnetycznych. W dyskach magnetycznych informacja zapisywana jest poprzez manipulację mikroskopijnymi magnesami. Różna orientacja magnesów odpowiada wartościom bitów 0 i 1. Zbytnie zagęszczenie kropek magnetycznych powoduje, że ich pola magnetyczne zaczynają na siebie oddziaływać, co może doprowadzić do spontanicznej zmiany orientacji, a więc i zapisanego bitu. W efekcie nadmierne zagęszczenie siatki uniemożliwia użycie dwóch sąsiadujących pozycji, przez co zmniejszamy liczbę zapisanych bitów z 1 na pozycję do średnio ok. 0,59 bita na pozycję, jednak liczba pozycji rośnie dwukrotnie, więc dostajemy ostatecznie dysk o ok. 1,18 razy większej pojemności. Takie operowanie na ułamkach bitów wymagało specjalnego typu kodowania. Nie znając jeszcze wówczas kodowania arytmetycznego, Duda wymyślił swoją metodę. Dziś nasze dane są głównie zapisane wariantami, które wprowadził później – tzw. stablicowany tANS z 2007 i przedziałowy rANS z 2013 r. To wtedy jego rozwiązanie zdobyło popularność, bo okazało się kilkukrotnie szybsze od metod alternatywnych.

ANS zawdzięcza swój sukces prostocie – zapisuje informację w jednej liczbie naturalnej, podczas gdy kodowanie arytmetyczne zapisuje ją w dwóch reprezentujących przedział. Nie będziemy tu wchodzić w zawiłe matematyczne szczegóły, ale warto wspomnieć, że w tym systemie każdy znak możemy „zważyć”, określając dla niego prawdopodobieństwo pojawienia się – różne w zależności od naszych potrzeb. To zaś przekłada się na oszczędniejsze gospodarowanie bitami. A więc także na szybkość przetwarzania danych.

Przyszłość jest teraz

Była już mowa o tym, że patenty opóźniły zastosowania kodowania arytmetycznego o kilka dekad. Duda nie chciał, żeby podobny los spotkał jego metodę – uważał zresztą, że powinna być ona dostępna bezpłatnie dla wszystkich, dlatego zrezygnował ze starań o uzyskanie patentu. Jednak w 2015 r. odkrył, że Google złożyło do amerykańskiego urzędu patentowego wniosek na użycie ANS w kompresji plików wideo. Gdy od 2014 r. Duda pomagał w aplikacji tej metody kompresji filmów przez Google, temat patentu nigdy się nie pojawił. Protesty Dudy wsparte przez prawników Uniwersytetu Jagiellońskiego doprowadziły do odrzucenia wniosku przez urząd patentowy. W styczniu ubiegłego roku ­Google oficjalnie zrezygnowało z dalszej walki o patent na ANS.

Już dziś opracowane przez polskiego matematyka rozwiązanie stosowane jest przez Facebooka. Jego kompresor Zstandard (zstd) używający ANS zastępuje podstawowy format zip. Korzystamy z tej metody także w systemie Linux oraz produktach dziesiątek firm, jak Amazon czy IBM. Apple korzysta z opartego na tym kodowaniu algorytmu LZFSE, którego codziennie używają użytkownicy iPhone’ów, Maców i iWatchy. Pixar, znany producent filmów animowanych, korzysta z ANS w Google Draco, algorytmie do kompresji grafiki 3D. ANS jest też używany przez producentów gier komputerowych w kilku kompresorach, np. Oodle Kraken, będącym podstawą dla konsoli PlayStation 5 firmy Sony. A jeśli poddasz się sekwencjonowaniu DNA, prawdopodobnie twój genom zostanie zapisany metodą ANS w kompresorze CRAM. W tej chwili trwa też proces standaryzacji formatu JPEG XL, który już wkrótce zastąpi wysłużony – powstały prawie 30 lat temu – format JPG, używany do zapisu zdjęć. Zastosowanie algorytmu opartego na ANS w kombinacji z innymi usprawnieniami spowoduje, że pliki graficzne zajmować będą trzy razy mniej miejsca niż obecnie, odciążając tym samym pamięci urządzeń i przyspieszając ładowanie stron.

Nic więc dziwnego, że ta metoda kodowania jest dziś nauczana na uniwersytetach na całym świecie. ©

Autor dziękuje Jarosławowi Dudzie za wyjaśnienie działania ­systemu ANS.

Dziękujemy, że nas czytasz!

Wykupienie dostępu pozwoli Ci czytać artykuły wysokiej jakości i wspierać niezależne dziennikarstwo w wymagających dla wydawców czasach. Rośnij z nami! Pełna oferta →

Dostęp 10/10

  • 10 dni dostępu - poznaj nas
  • Natychmiastowy dostęp
  • Ogromne archiwum
  • Zapamiętaj i czytaj później
  • Autorskie newslettery premium
  • Także w formatach PDF, EPUB i MOBI
10,00 zł

Dostęp kwartalny

Kwartalny dostęp do TygodnikPowszechny.pl
  • Natychmiastowy dostęp
  • 92 dni dostępu = aż 13 numerów Tygodnika
  • Ogromne archiwum
  • Zapamiętaj i czytaj później
  • Autorskie newslettery premium
  • Także w formatach PDF, EPUB i MOBI
89,90 zł
© Wszelkie prawa w tym prawa autorów i wydawcy zastrzeżone. Jakiekolwiek dalsze rozpowszechnianie artykułów i innych części czasopisma bez zgody wydawcy zabronione [nota wydawnicza]. Jeśli na końcu artykułu znajduje się znak ℗, wówczas istnieje możliwość przedruku po zakupieniu licencji od Wydawcy [kontakt z Wydawcą]

Artykuł pochodzi z numeru Nr 10/2021