Kompresja danych wyjaśniona

Każda strona internetowa, którą wczytujesz, każdy plik ZIP i każdy obraz PNG zostały skompresowane: zmniejszone bez utraty choćby jednego bitu i rozpakowane z powrotem po dotarciu na miejsce. Metody, które za tym stoją, są zaskakująco proste. Szukają tego, co się powtarza, i zamiast mówić to jeszcze raz, mówią „to samo co wcześniej”. Jak daleko sięga ten pomysł i gdzie się kończy, to jedna z najzgrabniejszych historii informatyki.

Wiersz tekstu, w którym powtórzone fragmenty zastąpiono strzałkami wskazującymi wstecz na ich pierwsze wystąpienie, obok słupków pokazujących rozmiar oryginalny i skompresowany
Wiersz tekstu, w którym powtórzone fragmenty zastąpiono strzałkami wskazującymi wstecz na ich pierwsze wystąpienie, obok słupków pokazujących rozmiar oryginalny i skompresowany

Kompresja bezstratna i stratna

Kompresja występuje w dwóch odmianach. Kompresja bezstratna oddaje dokładnie oryginał, co jest niezbędne dla tekstu, programów, arkuszy kalkulacyjnych i wszystkiego, w czym jeden błędny bit ma znaczenie. Kompresja stratna, stosowana do zdjęć, muzyki i wideo, odrzuca szczegóły, których ludzie prawie nie dostrzegają, i osiąga znacznie mniejsze rozmiary, ale oryginał przepada bezpowrotnie. Ta strona i demonstrator dotyczą kompresji bezstratnej, która działa przez wyszukiwanie i usuwanie nadmiarowości: tych części danych, które dało się przewidzieć.

Kodowanie długości serii

Najprostsza metoda zastępuje serię identycznych symboli licznikiem i symbolem: dwanaście białych pikseli zamienia się w 12W. Korzystały z niej faksy, wczesne formaty bitmap i format graficzny PCX, bo zeskanowane strony i proste rysunki są pełne długich serii. Na zwykłym tekście jest bezużyteczna, a nawet szkodliwa: serie są rzadkie, a zapisanie licznika przy każdej pojedynczej literze podwaja rozmiar. Kodowanie długości serii wciąż jednak żyje wewnątrz innych metod, gdzie koduje serie zer pozostałe po wstępnym przekształceniu.

LZ77: wskazywanie wstecz

W 1977 roku Abraham Lempel i Jacob Ziv, dwaj badacze z Technionu w Izraelu, opublikowali metodę, która odmieniła tę dziedzinę. Koder przechowuje okno z tekstem, który właśnie przetworzył. Jeśli kolejne znaki wystąpiły już w oknie, zapisuje parę: jak daleko wstecz zaczyna się wcześniejsza kopia i jak jest długa. W przeciwnym razie zapisuje sam znak. Dekoder nie potrzebuje żadnego słownika, tylko tekstu, który już odtworzył. Odwołanie może nawet zachodzić na tekst, który samo wytwarza, więc seria 100 identycznych liter to jedna litera i jedno odwołanie.

Abraham Lempel, który w 1977 w Technionie wraz z Jacobem Zivem opublikował metodę okna i odwołań, dziś zwaną LZ77.
Abraham Lempel, który w 1977 w Technionie wraz z Jacobem Zivem opublikował metodę okna i odwołań, dziś zwaną LZ77.

LZW: uczenie się słownika

Druga metoda Lempela i Ziva, LZ78, zamiast szukać wstecz w oknie buduje słownik. Udoskonalenie Terry’ego Welcha z 1984 roku, LZW, zaczyna od wszystkich 256 wartości bajtu i na każdym kroku wysyła numer najdłuższego znanego już ciągu, a jako nowy wpis dodaje ten ciąg wraz z następnym znakiem. Dekoder odtwarza ten sam słownik z samych numerów. LZW było szybkie i proste, więc trafiło do polecenia compress systemu Unix, formatu graficznego GIF i plików TIFF, dopóki patenty na nie nie wywołały w latach 90. długiego sporu.

Deflate, ZIP i dalej

Metoda deflate Phila Katza, wprowadzona wraz z PKZIP 2 w 1993 roku, łączy LZ77 z kodowaniem Huffmana: po znalezieniu powtórzeń nadaje najczęstszym literałom, długościom i odległościom najkrótsze kody bitowe. Deflate jest używany w ZIP, gzip, obrazach PNG i kompresji stron internetowych i to właśnie tę metodę demonstrator mierzy za pomocą wbudowanego kompresora przeglądarki. Nowsze metody, takie jak Zstandard, Brotli i xz, używają większych okien, sprytniejszego dopasowywania i dokładniejszego kodowania entropijnego i zmniejszają typowe pliki o dalsze 10–30%.

Dlaczego nie wszystko da się zmniejszyć

Żadna metoda nie zmniejszy każdego pliku. Istnieje 2ⁿ plików n-bitowych, ale tylko 2ⁿ − 1 plików krótszych, więc gdyby metoda zmniejszała je wszystkie, dwa z nich dałyby ten sam wynik i nie dałoby się odtworzyć obu: to zasada szufladkowa Dirichleta. Każdy kompresor powiększa więc niektóre dane wejściowe, zwykle dane wyglądające na losowe, takie jak pliki zaszyfrowane, pliki już skompresowane i szum. To zarazem test losowości: dane, których nie zmniejszy żaden kompresor, wyglądają na losowe.

Granica entropii

Claude Shannon wykazał w 1948 roku, że entropia źródła jest najmniejszą możliwą średnią liczbą bitów na symbol dla dowolnego kodu bezstratnego. Liczony litera po literze tekst angielski ma entropię około 4 bitów na literę, czyli połowę z 8 bitów, w których jest zapisywany. Metody korzystające z kontekstu, takie jak LZ77, schodzą na tekście z powtórzeniami poniżej tej wartości dla pojedynczych liter, bo odwołanie zastępuje od razu cały fragment. Najlepsze współczesne kompresory, które przewidują każdą literę na podstawie wszystkiego, co było przed nią, sprowadzają angielski do mniej niż 2 bitów na literę.

Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.
Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.

Wypróbuj to

Otwórz demonstrator kompresji, aby uruchomić LZ77, LZW i kodowanie długości serii na akapicie, piosence z refrenem, rzędzie pikseli, tabeli danych, losowych literach lub DNA albo na własnym tekście. Kliknij dowolne odwołanie LZ77, aby zobaczyć, co kopiuje, obserwuj, jak rośnie słownik LZW, i porównaj wszystkie metody z ZIP i granicą entropii.

Często zadawane pytania

Co oznacza stopień kompresji 3 : 1?

Że oryginał jest trzy razy większy od wersji skompresowanej, więc skompresowany plik zajmuje jedną trzecią miejsca i oszczędza dwie trzecie. Tekst osiąga z ZIP zwykle od 2 : 1 do 4 : 1; dane z dużą liczbą powtórzeń, takie jak pliki dziennika (logi), często znacznie więcej.

Dlaczego ponowna kompresja pliku ZIP nic nie daje?

Pierwszy przebieg usunął już powtórzenia, a jego wynik wygląda niemal losowo. Drugi przebieg nie znajduje niczego, do czego mógłby się odwołać, i dodaje tylko własny narzut, więc plik zachowuje ten sam rozmiar albo nieco rośnie.

Dlaczego większe okno LZ77 jest lepsze?

Większe okno pozwala koderowi znaleźć powtórzenia leżące dalej wstecz, na przykład refren, który wraca po kilku zwrotkach. Ceną jest to, że zapisanie każdej odległości wymaga więcej bitów, a wyszukiwanie trwa dłużej, dlatego deflate zatrzymuje się na 32 KB, a nowsze metody dopuszczają megabajty.

Czy kompresja to to samo co szyfrowanie?

Nie. Kompresja zmniejsza dane i każdy może ją odwrócić; szyfrowanie sprawia, że dane są nieczytelne bez klucza. Często łączy się je ze sobą i wtedy dane trzeba najpierw skompresować: zaszyfrowane dane wyglądają losowo i nie da się ich już skompresować.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz demonstrator kompresji