Granice kompresji

Wprowadzenie do granic kompresji

Kompresja bezstratna wykorzystuje zależności i powtórzenia obecne w danych, natomiast kompresja stratna dodatkowo zmniejsza dokładność reprezentacji zgodnie z przyjętym modelem jakości. Autoinformacja i entropia pozwalają opisać ilość informacji oraz statystyczną nieprzewidywalność źródła. Nadmiarowość można wtedy rozpatrywać jako część opisu wynikającą z powtarzalności danych. Koder bezstratny musi zachować możliwość jednoznacznego odtworzenia każdego symbolu, a długość kodu może zależeć od jego prawdopodobieństwa. Współczynnik kompresji z konkretnego pliku nie jest więc samą granicą teoretyczną, ponieważ obejmuje także nagłówki, model i sposób reprezentacji.

Pojawia się więc pytanie o granicę dalszego zmniejszania opisu. Odpowiedź wynika z teorii informacji i z pracy Claude'a Shannona. Twierdzenie Shannona o kodowaniu źródłowym określa asymptotyczną średnią długość kodu dla źródła o danym rozkładzie prawdopodobieństwa. Granica ujawnia się przy porównaniu krótkich bloków, budowy modelu oraz złożoności pojedynczego ciągu.

Twierdzenie Shannona o kodowaniu źródłowym

Twierdzenie o kodowaniu źródłowym, nazywane także pierwszym twierdzeniem Shannona, opisuje zależność między entropią źródła a średnią długością kodu bezstratnego. W standardowym ujęciu dotyczy dyskretnego źródła bezpamięciowego i długich bloków symboli. Jedna część wyznacza dolne ograniczenie, druga opisuje możliwość zbliżenia się do tego ograniczenia. Sformułowanie dotyczy średniej po komunikatach zgodnych z rozkładem źródła. Dla pojedynczego pliku wynik może odbiegać od średniej, zwłaszcza gdy plik jest krótki albo model źródła jest niedopasowany.

Dolne ograniczenie średniej długości kodu

Pierwsza część twierdzenia wyznacza dolne ograniczenie średniej długości kodu.

W praktyce średnia liczba bitów na symbol nie może zejść poniżej entropii źródła przy zachowaniu bezstratności i założeń modelu. Entropia opisuje średnią ilość informacji wynikającą z rozkładu symboli. Wartość poniżej tego poziomu oznaczałaby pominięcie części rozróżnialnych komunikatów albo dodatkowe założenie o źródle.

Osiągalność granicy asymptotycznej

Druga część twierdzenia mówi, że dolne ograniczenie można osiągać asymptotycznie dla odpowiednio długich bloków.

Wyrażenie "dowolnie bliska" odnosi się do granicy asymptotycznej. Dla krótkich wiadomości narzut nagłówków, modelu i sposobu kodowania może podnieść średnią długość. Dla długich bloków odpowiednio zaprojektowany kod może zbliżać średnią do entropii z dowolnie małym odstępem. Kodowanie arytmetyczne pokazuje tę zasadę, ponieważ rozkłada informację na cały komunikat i może osiągać wynik bliski granicy Shannona.

Skąd wynika rola entropii

Kompresor musi przyporządkować każdej wiadomości wejściowej jednoznaczny opis, który pozwoli dekompresorowi odtworzyć oryginał. Gdyby dwa różne komunikaty otrzymały ten sam opis, dekompresor nie rozróżniłby ich podczas odtwarzania. Jednoznaczność ogranicza liczbę krótkich opisów dostępnych dla całego zbioru wiadomości.

Rozważmy źródło wytwarzające wiadomości długości $L$ symboli. Liczba wszystkich wiadomości rośnie wykładniczo, lecz ich prawdopodobieństwa mogą się różnić. Dla źródła spełniającego założenia twierdzenia większość prawdopodobieństwa skupia się, przy dużym $L$, w zbiorze sekwencji zwanym zbiorem typowym.

Liczba sekwencji w tym zbiorze typowym wynosi w przybliżeniu $2^{L cdot H(X)}$. Wszystkie inne "nietypowe" sekwencje mają łącznie małe prawdopodobieństwo. Aby stworzyć bezstratny schemat kompresji, musimy mieć co najmniej tyle unikalnych, skompresowanych słów kodowych, aby reprezentować każdą sekwencję z tego zbioru typowego. Minimalna liczba bitów wymagana do unikalnej identyfikacji $2^{L cdot H(X)}$ różnych elementów wynosi, z definicji, $\log_2(2^{L cdot H(X)})$, co upraszcza się do $L cdot H(X)$ bitów. Jest to argument asymptotyczny, oparty na własności typowej dla długich bloków. Kod musi dodatkowo obsłużyć przypadki spoza zbioru, zwykle przez osobne reguły albo większy opis.

Jeśli całkowita liczba bitów wymagana dla wiadomości o długości $L$ symboli wynosi $L \cdot H(X)$, to średnia liczba bitów wymagana na symbol wynosi $\frac{L \cdot H(X)}{L} = H(X)$. Ta zależność wynika z twierdzenia Shannona. Entropia określa liczbę "prawdopodobnych" wiadomości, które trzeba rozróżnić podczas kodowania, a to wyznacza minimalną średnią liczbę bitów na symbol.

Przykład źródła z czterema symbolami

Rozważmy źródło generujące symbole A, B, C i D.

Dla rozkładu jednostajnego $H(X) = 2$. Kod (A=00, B=01, C=10, D=11) ma średnią długość $L_{\text{avg}} = 2$ bity/symbol. Ponieważ $L_{\text{avg}} = H(X)$, kod osiąga granicę dla tego modelu źródła.

Przyjmijmy rozkład $P(A)=0.48, P(B)=0.26, P(C)=0.18, P(D)=0.08$. Daje on $H(X) \approx 1.75$ bita/symbol. W przykładzie przyjmujemy wartość $H(X) = 1.75$. Kod 2-bitowy ma średnią długość $L_{\text{avg}} = 2$, więc pozostaje powyżej entropii. W tym przykładzie obie części twierdzenia opisują osobne ograniczenia:

1. Średnia długość bezstratnego kodu dla tego źródła nie może wynosić 1.7 bita/symbol. Dolna granica wynika z entropii około 1.75.
2. Kod Huffmana o długościach 1, 2, 3 i 3 dla A, B, C i D daje średnią długość 1.78 bita/symbol, bliską wartości 1.75. Kodowanie arytmetyczne może zmniejszyć odstęp dla długiego bloku.

Ograniczenia praktycznych koderów

Twierdzenie Shannona opisuje wynik asymptotyczny dla określonego modelu źródła. Implementacja musi dodatkowo oszacować rozkład, zakodować model i obsłużyć skończone bloki. Z tego powodu wynik praktycznego kodera jest przybliżeniem granicy zależnym od danych i narzutu formatu.

Budowa modelu źródła

Obliczenie entropii wymaga rozkładu prawdopodobieństwa symboli. Model można wyznaczyć z danych, przyjąć z góry albo aktualizować podczas kodowania.

• Kompresja dwubiegowa: W pierwszym przebiegu plik służy do zbudowania modelu statystycznego, na przykład przez zliczenie częstotliwości znaków. W drugim przebiegu model steruje kodowaniem. Model trzeba zapisać lub przekazać razem z danymi, więc narzut może mieć duży udział w małym pliku.
• Modele zdefiniowane wcześniej: Dla danego typu danych można użyć ogólnego modelu, na przykład średnich częstotliwości liter w języku polskim. Nie ma wtedy osobnego modelu w strumieniu, lecz wynik zależy od zgodności pliku z przyjętym rozkładem.
• Modele adaptacyjne: Koder zaczyna od modelu początkowego i aktualizuje statystyki podczas przetwarzania danych. Dekoder wykonuje te same aktualizacje, aby zachować synchronizację. LZMA używany w 7z stosuje adaptacyjne modelowanie prawdopodobieństwa. ZIP może korzystać z dynamicznych kodów Huffmana w blokach Deflate, lecz szczegóły zależą od metody i implementacji.

Długość bloku i całkowite długości kodów

Twierdzenie Shannona ma charakter asymptotyczny. W krótkich plikach nagłówek, drzewo Huffmana albo słownik może zniwelować zysk wynikający z kodowania danych. Kody prefiksowe przypisują symbolom całkowite długości, więc przy entropii równej na przykład 1.75 bita/symbol średnia długość kodu wymaga przybliżenia. Kodowanie arytmetyczne może zmniejszyć ten odstęp w długim komunikacie, ponieważ średni koszt jest rozłożony na wiele symboli.

Granica pojedynczego ciągu i nieskompresowalność

Teoria Shannona opisuje średnią ściśliwość źródła. Algorytmiczna teoria informacji i złożoność Kołmogorowa dotyczą opisu pojedynczego, konkretnego ciągu.

Przy ustalonym uniwersalnym języku programowania złożoność Kołmogorowa $K(s)$ oznacza długość najkrótszego programu generującego ciąg $s$. Wartość zależy od tego wyboru najwyżej o stałą niezależną od ciągu. Stanowi teoretyczny punkt odniesienia dla bezstratnego opisu, razem z kodem programu i dekodera. Złożoność Kołmogorowa nie jest obliczalna dla dowolnego ciągu, dlatego służy przede wszystkim jako pojęcie graniczne. Praktyczny kompresor może jedynie szukać krótkiego opisu w określonej rodzinie modeli.

Ciąg nazywa się algorytmicznie losowym, gdy jego złożoność jest bliska długości ciągu, z uwzględnieniem stałej zależnej od języka. Nie istnieje wtedy krótszy opis w rozważanym modelu. Dla danych o takim charakterze bezstratny koder często dodaje nagłówek lub inne metadane, więc wynik może być większy od wejścia. Z tego powodu ponowne pakowanie pliku skompresowanego stratnie, na przykład JPEG, albo danych losowych zwykle nie zmniejsza rozmiaru.

Podsumowanie granic kompresji

Twierdzenie Shannona wyznacza statystyczną granicę średniej długości kodu źródła dla długich bloków i określonego modelu prawdopodobieństwa. Kodowanie Huffmana oraz arytmetyczne są praktycznymi sposobami zbliżania się do tej granicy przy różnych ograniczeniach. Złożoność Kołmogorowa opisuje natomiast najkrótszy program dla pojedynczego ciągu w ustalonym modelu opisu. Oba ujęcia wyjaśniają, dlaczego wynik zależy od statystyki źródła, długości bloku i tego, czy rozpatrujemy średnią, czy konkretną wiadomość. Przy ocenie narzędzia trzeba więc rozdzielić własność danych od narzutu formatu. Plik może mieć entropię bliską granicy, a mimo tego otrzymać większy wynik po dodaniu metadanych. W przypadku kodów prefiksowych nierówność Krafta łączy długości słów kodowych z możliwością jednoznacznego dekodowania. Kod Huffmana dla pojedynczych symboli ma całkowite długości słów, natomiast kodowanie blokowe zmniejsza względny narzut zaokrągleń. Dla źródła z pamięcią entropia pojedynczego symbolu może pomijać zależności między symbolami, dlatego właściwą miarą bywa entropia warunkowa albo entropia bloku. Model użyty podczas pomiaru powinien odpowiadać danym, które koder otrzyma w rzeczywistym zadaniu. Przy krótkich plikach koszt nagłówka i tablicy kodów może dominować nad oszczędnością wynikającą z modelu. To ograniczenie dotyczy konkretnej implementacji formatu.

Porównanie wymaga tego samego alfabetu, modelu źródła i formatu wyjściowego. Koszt reprezentacji modelu oraz alfabetu pozostaje częścią praktycznego wyniku i powinien być uwzględniony w pomiarze.