Jak działa bezstratna kompresja danych | Magazyn Quanta

Każdego dnia w Internecie przepływa ponad 9 miliardów gigabajtów informacji, dlatego badacze nieustannie poszukują nowych sposobów kompresji danych do mniejszych pakietów. Najnowocześniejsze techniki koncentrują się na podejściach stratnych, które osiągają kompresję poprzez celową „utratę” informacji z transmisji. Na przykład Google niedawno ujawnił stratną strategię, w której komputer wysyłający usuwa szczegóły z obrazu, a komputer odbierający wykorzystuje sztuczną inteligencję do odgadnięcia brakujących części. Nawet Netflix stosuje stratne podejście, obniżając jakość wideo, gdy firma wykryje, że użytkownik ogląda na urządzeniu o niskiej rozdzielczości.

Natomiast bardzo niewiele badań jest obecnie prowadzonych nad strategiami bezstratnymi, w których transmisje są zmniejszane, ale nie poświęca się żadnej substancji. Powód? Podejścia bezstratne są już niezwykle wydajne. Obsługują wszystko, od standardu obrazu JPEG po wszechobecne oprogramowanie narzędziowe PKZip. A wszystko to za sprawą studenta, który po prostu szukał wyjścia z trudnego egzaminu końcowego.

Siedemdziesiąt lat temu Robert Fano, profesor Massachusetts Institute of Technology, dał studentom na swoich zajęciach z teorii informacji wybór: przystąpić do tradycyjnego egzaminu końcowego lub udoskonalić wiodący algorytm kompresji danych. Fano mógł, ale nie musiał, informować swoich uczniów, że jest autorem istniejącego algorytmu lub że od lat poluje na ulepszenia. Wiemy tylko, że Fano zaoferował swoim uczniom następujące wyzwanie.

Rozważ wiadomość złożoną z liter, cyfr i znaków interpunkcyjnych. Prostym sposobem zakodowania takiej wiadomości byłoby przypisanie każdemu znakowi unikalnej liczby binarnej. Na przykład komputer może reprezentować literę A jako 01000001, a wykrzyknik jako 00100001. Powoduje to, że kody są łatwe do przeanalizowania — co osiem cyfr lub bitów odpowiada jednemu unikalnemu znakowi — ale strasznie nieefektywne, ponieważ ta sama liczba cyfr binarnych jest używany zarówno dla wpisów powszechnych, jak i nietypowych. Lepszym podejściem byłoby coś w rodzaju alfabetu Morse'a, gdzie częsta litera E jest reprezentowana przez tylko pojedynczą kropkę, podczas gdy mniej powszechne Q wymaga dłuższej i bardziej pracochłonnej kreski-kreski-kropki-kreski.

Jednak alfabet Morse'a jest również nieefektywny. Jasne, niektóre kody są krótkie, a inne długie. Ale ponieważ długość kodu jest różna, komunikaty zapisane alfabetem Morse'a nie mogą być zrozumiane, chyba że zawierają krótkie okresy ciszy między każdą transmisją znaków. Rzeczywiście, bez tych kosztownych przerw odbiorcy nie byliby w stanie odróżnić wiadomości Morse'a kreska kropka-kreska-kropka kropka-kropka kreska kropka („banalne”) od kreska kropka-kreska-kropka kropka-kropka-kreska kropka („prawda” ).

Fano rozwiązał tę część problemu. Zdał sobie sprawę, że może używać kodów o różnej długości bez konieczności stosowania kosztownych spacji, o ile nigdy nie używa tego samego wzoru cyfr zarówno jako pełnego kodu, jak i początku innego kodu. Na przykład, jeśli litera S była tak powszechna w konkretnej wiadomości, że Fano przypisał jej wyjątkowo krótki kod 01, to żadna inna litera w tej wiadomości nie byłaby zakodowana z niczym, co zaczynało się od 01; kody takie jak 010, 011 lub 0101 byłyby zabronione. W rezultacie zakodowaną wiadomość można było czytać od lewej do prawej, bez żadnych dwuznaczności. Na przykład, gdy literze S przypisano 01, literze A przypisano 000, literze M przypisano 001, a literze L przypisano 1, nagle wiadomość 0100100011 może zostać natychmiast przetłumaczona na słowo „mały”, mimo że L jest reprezentowane przez jeden cyfra, S o dwie cyfry, a pozostałe litery po trzy.

Aby faktycznie określić kody, Fano zbudował drzewa binarne, umieszczając każdą niezbędną literę na końcu gałęzi wizualnej. Kod każdej litery został następnie zdefiniowany przez ścieżkę od góry do dołu. Jeśli ścieżka rozgałęziała się w lewo, Fano dodawał 0; prawe gałęzie otrzymały 1. Struktura drzewa ułatwiła Fano unikanie tych niepożądanych nakładek: gdy Fano umieścił literę w drzewie, ta gałąź się kończyła, co oznaczało, że żaden przyszły kod nie mógł zaczynać się w ten sam sposób.

Aby zdecydować, które litery trafią dokąd, Fano mógł wyczerpująco przetestować każdy możliwy wzór pod kątem maksymalnej wydajności, ale byłoby to niepraktyczne. Zamiast tego opracował przybliżenie: dla każdej wiadomości uporządkował odpowiednie litery według częstotliwości, a następnie przypisał litery do gałęzi, tak aby litery po lewej stronie w dowolnej parze gałęzi zostały użyte w wiadomości mniej więcej tyle samo razy, co litery po prawej stronie. W ten sposób często używane znaki trafiałyby na krótsze, mniej gęste gałęzie. Niewielka liczba liter o wysokiej częstotliwości zawsze równoważy większą liczbę liter o niższej częstotliwości.

Rezultatem była niezwykle skuteczna kompresja. Ale to było tylko przybliżenie; musiała istnieć lepsza strategia kompresji. Więc Fano rzucił wyzwanie swoim uczniom, aby go znaleźli.

Fano zbudował swoje drzewa od góry do dołu, zachowując jak największą symetrię między parami gałęzi. Jego uczeń, David Huffman, odwrócił ten proces do góry nogami, budując te same typy drzew, ale od dołu do góry. Wgląd Huffmana polegał na tym, że niezależnie od tego, co się stanie, w wydajnym kodzie dwa najrzadziej występujące znaki powinny mieć dwa najdłuższe kody. Tak więc Huffman zidentyfikował dwie najrzadziej spotykane postacie, zgrupował je w rozgałęzioną parę, a następnie powtórzył proces, tym razem szukając dwóch najmniej powszechnych wpisów spośród pozostałych postaci i pary, którą właśnie zbudował.

Rozważ wiadomość, w której podejście Fano słabnie. W „schoolroom” O pojawia się cztery razy, a S/C/H/L/R/M raz. Podejście równoważenia Fano zaczyna się od przypisania O i jednej innej litery do lewej gałęzi, przy czym pięć całkowitych zastosowań tych liter równoważy pięć występów pozostałych liter. Wynikowa wiadomość wymaga 27 bitów.

Z kolei Huffman zaczyna od dwóch rzadkich liter — powiedzmy R i M — i grupuje je razem, traktując parę jak pojedynczą literę.

Jego zaktualizowany wykres częstotliwości oferuje mu następnie cztery możliwości: O, które pojawia się cztery razy, nowy połączony węzeł RM, który jest funkcjonalnie używany dwukrotnie, oraz pojedyncze litery S, C, H i L. Huffman ponownie wybiera dwie najrzadziej spotykane opcje, pasujące (powiedzmy) H z L.

Wykres ponownie się aktualizuje: O nadal ma wagę 4, RM i HL mają teraz wagę 2, a litery S i C stoją osobno. Huffman kontynuuje stamtąd, na każdym etapie grupując dwie najrzadziej występujące opcje, a następnie aktualizując zarówno drzewo, jak i wykres częstotliwości.

Ostatecznie „sala szkolna” staje się 11101111110000110110000101, goląc nieco podejście odgórne Fano.

Jeden bit może nie wydawać się dużo, ale nawet niewielkie oszczędności rosną ogromnie, gdy są skalowane o miliardy gigabajtów.

Rzeczywiście, podejście Huffmana okazało się tak potężne, że obecnie prawie każda strategia bezstratnej kompresji wykorzystuje wgląd Huffmana w całości lub w części. Potrzebujesz PKZip do skompresowania dokumentu Word? Pierwszy krok obejmuje kolejną sprytną strategię identyfikowania powtórzeń, a tym samym kompresji rozmiaru wiadomości, ale drugim krokiem jest pobranie powstałej skompresowanej wiadomości i przeprowadzenie jej przez proces Huffmana. Przechowywać obraz jako JPEG? Twój komputer najpierw tłumaczy obraz na reprezentację tekstową, a następnie ponownie używa kodowania Huffmana do kompresji tego tekstu.

Nieźle jak na projekt pierwotnie motywowany pragnieniem absolwenta, aby pominąć egzamin końcowy.