Algorytmy Kompresji

Algorytmy kompresji to moje ulubione rodzaje algorytmów, które testuję eksperymentalnie. Już kiedyś co nieco o tym opowiadałem, ale temat jest bardzo ciekawy mimo wszystko, a dodatkowo łączy się z tematyką ogólnej informatyki.

Skąd się wzięła kompresja?

Nośniki analogowe (część) miały to do siebie, że zawsze przechowywały taką samą ilość danych (w sensie taką samą dla urządzenia). Nieważne czy obraz był bardzo szczegółowy czy bardzo prosty, film zajmował ileś klatek.

Dlatego na przykład na płytach CD podawało się czas w minutach (muzyki) i czemu średnio na płycie mieściło się ~17 piosenek (bo więcej się nie dało - nieważne czy utwór był słabej czy dobrej jakości).

Jednak z cyfrowymi rozwiązaniami było inaczej, gdyż mogły one przetwarzać materiały przed "wytworzeniem go". Sprawia to, że można próbować zapisać te same lub podobne ilości danych na mniejszej objętości. Co oznacza, że można było umieścić więcej utworów na płycie lub wytwarzać mniejsze nośniki (np. płyty 350MB).

Ważne programy i algorytmy, które zmieniły oblicza świata (z dziedziny kompresji).

Oczywiście lista jest subiektywna

Stacker / DoubleSpace

Była to pierwsza rewolucyjna technologia. Na początku ery komputerów dyski nie były pojemne (o ile ktoś miał), dyskietki zresztą też ;) Co zrobić? Firmy Stac Electronics stworzyła (prawdopodobnie) pierwszy program, który kompresował dane na dysku systemowym "w taki sposób, że komputer jeszcze działał". Zwiększało to często wydajność komputera (bo wczytanie danych skompresowanych potrafiło trwać szybciej niż wersja bez kompresji), a także zaoszczędzić trochę miejsca.

Niestety Microsoft dokonał kradzieży intelektualnej (zdobywając algorytmy itd) i na jej podstawie dokonali własną wersję Stackera niszcząc firmę. Kiedyś to były czasy ...

MP3

W 1991 roku na świat przychodzi nowy standard kodowania dźwięku. Wcześniejsze algorytmy bezstratne umożliwiały zapisywanie muzyki w bardzo dobrej jakości, ale kosztem miejsca. Zespół z organizacji Fraunhofer poszedł do tego inaczej tworząc algorytm kompresji stratnej (czyli z utratą danych), który zapisze muzykę w jakości "odpowiadającej" ludziom.

Wynalazek się przyjął, często zresztą ludzie nazywali urządzenia do odtwarzania muzyki - "empetrójkami". Tak więc był to rewolucyjny projekt i nawet lepszy algorytmy jak OGG Vorbis nie są w stanie tego sukcesu przerwać.

PNG

Portable Network Graphics to dość ciekawy rodzaj algorytmu, który powstał z potrzebny. Wyobraźcie sobie czasy, w których nie możecie w projekcie wykorzystać GIFów. Dzisiaj jest to sytuacja nie do wyobrażenia, ale kiedyś z powodu patentów nie można było używać tego algorytmu (np. Paint uniemożliwiał zapisywanie do niego). Makabra? Być może.

Na szczęście pojawiła się grupa śmiałków, która stworzyła algorytm nieopatentowany.

LZMA2

Nie zawsze wydajność się liczy w dziedzinie informatyki. LZMA2 to "algorytm potwór", który wymaga olbrzymich mocy obliczeniowych by stworzyć archiwum możliwie najlżejsze. Domyślny algorytm stosowany przez 7-zip (i chyba ostatecznie przez RAR) przydaje się do przechowywania danych, których rzadko używamy (np. Backupy).

ZStandard

Bardzo ciekawy algorytm wytworzony przez Polaka, którego celem było stworzenie algorytmu kompresji bardzo szybkiego, ale zarazem (dzięki jego pomysłowi) z całkiem niezłą wagą pliku wynikowego.

Algorytm ten jest o tyle ciekawy, że ... Google próbowało go ukraść i opatentować. "Don't be evil" nie działa już od jakiegoś czasu, więc Google posuwa się do różnych kradzieży (nie tylko tego algorytmu, żeby nie było. Często zapraszają na rozmowy kwalifikacyjne ludzi z ich wynalazkami, które próbują ukraść - też znana afera).

H.265

H.265 to nowa wersja algorytmu (niestety opatentowanego i to mocno - może AV1 dorówna mu rozmiarowym plikiem), który dzięki zastosowaniu nowoczesnych algorytmów pozwala z np. 5.5GB filmu FLV zrobić 700MB film (w full HD). Stosowane są różne sztuczki jak wykrywanie ruchu (co pewnie widzieliście kiedyś, że film jak się zatnie i zepsuje to do następnej sceny często jest brzydki).

Opracowywanie tego typu algorytmów skutkuje tym, że np. Youtube jest bardziej rentowny ;)

The End

Algorytmy są stosowane i będą prawdopodobnie do końca życia informatyki. Większość stron się kompresuje, by szybciej się wczytywały i oszczędzały możliwie serwer! Im coś mniej waży tym często lepiej, szczególnie dla ludzi ze słabym łączem.