Entropia i Redundancja

Wprowadzenie: Podstawa Kompresji Bezstratnej

Po rozróżnieniu kompresji bezstratnej i stratnej skupiamy się na zasadzie działania kompresji bezstratnej. Algorytm bezstratny odtwarza dane wejściowe dokładnie, więc nie usuwa informacji. Zmienia sposób reprezentacji danych, wykorzystując występującą w nich nadmiarowość. Odtworzenie wymaga przechowania informacji o regułach kodowania lub o modelu użytym przez kompresor.

Nadmiarowość (redundancja) oznacza przewidywalne lub powtarzające się elementy reprezentacji danych. Ich opis można skrócić bez zmiany danych po dekompresji. Zawartość informacyjna określa część zależną od niepewności źródła. Teoria informacji, której podstawy opracował Claude Shannon, pozwala opisać obie wielkości. Entropia mierzy średnią zawartość informacji, natomiast redundancja opisuje różnicę między użytym kodem a granicą wyznaczoną przez entropię. Zależność ta wyjaśnia, kiedy i w jakim zakresie możliwa jest kompresja bezstratna. Reprezentacja bez nadmiarowości nie daje przestrzeni na dalsze skrócenie przy tym samym modelu źródła.

Entropię: Miara Niepewności i Informacji

Entropia to średnia zawartość informacji na symbol źródła. Dla rozkładu symboli określa niepewność związaną z ich występowaniem. Autoinformacja pojedynczego symbolu wynosi $I(x_i) = -\log_2 P(x_i)$, więc entropia jest jej wartością oczekiwaną. Jednostką wyniku przy logarytmie o podstawie 2 jest bit na symbol. Dla sekwencji z zależnościami między symbolami entropia na symbol może być mniejsza i wymaga uwzględnienia kontekstu poprzednich symboli. Wzór dla źródła $X$, które generuje symbole $x_i$ z prawdopodobieństwami $P(x_i)$, ma postać:

Właściwości Entropii

Z równania wynikają następujące własności informacji i niepewności:

• Entropia Maksymalna: Dla źródła o stałym alfabecie złożonym z $n$ symboli entropia osiąga maksimum, gdy symbole mają jednakowe prawdopodobieństwa. Wtedy $P(x_i) = 1/n$, a maksimum wynosi $H_{\text{max}}(X) = \log_2(n)$. W modelu bez pamięci taki rozkład nie daje wzorców statystycznych do wykorzystania, więc utrudnia kompresję. Zależności między kolejnymi symbolami mogą jednak obniżyć entropię źródła jako sekwencji.
• Entropia Minimalna (Zerowa Entropia):Entropia wynosi zero wtedy i tylko wtedy, gdy jeden symbol ma prawdopodobieństwo 1, a wszystkie pozostałe mają prawdopodobieństwo 0. Źródło jest wtedy deterministyczne, więc jego następny symbol można przewidzieć bez błędu. Przykładowo źródło generujące wyłącznie literę "A" ma entropię równą zero.
• Nieujemność: Wartość entropii jest zawsze równa zero lub dodatnia, ponieważ prawdopodobieństwa należą do przedziału od zera do jedności.

Przykład: Alfabet Czterech Symboli

Rozważmy źródło generujące wiadomości z alfabetu czterech symboli: A, B, C i D.

Załóżmy, że symbole są niezależne i każdy ma takie samo prawdopodobieństwo wystąpienia:

Maksymalna entropia dla tego źródła o czterech symbolach wynosi:

Kod stałej długości może przypisać symbolom wartości A=00, B=01, C=10, D=11. Średnia długość wynosi dokładnie 2 bity na symbol. Jest równa entropii tego źródła, więc kod osiąga teoretyczną granicę dla tego modelu. Każdy symbol wymaga dwóch bitów, ponieważ cztery równoprawdopodobne możliwości tworzą $\log_2(4) = 2$ bity informacji. Nie ma nadmiarowości wynikającej z użycia tego kodu.

Przyjmijmy teraz nierówny rozkład prawdopodobieństw. Część symboli występuje częściej, więc średnia niepewność źródła jest mniejsza.

Entropia dla tego nierównego źródła jest obliczana jako średnia ważona autoinformacji każdego symbolu:

Entropia (1.75 bita/symbol) jest mniejsza od maksymalnej wartości 2 bitów/symbol. Przy użyciu kodu 2-bitowego (A=00, B=01 itd.) średnia długość kodu nadal wynosi 2 bity. Kod o zmiennej długości może przydzielić krótsze słowa częstszym symbolom, zachowując jednoznaczne dekodowanie. Różnica między tą długością a entropią, czyli 0.25 bita/symbol, jest redundancją tego kodu.

Redundancja (Nadmiarowość): Różnica względem Entropii

Redundancja opisuje przewidywalną i powtarzalną część reprezentacji danych. Entropia określa średnią zawartość informacji źródła, a redundancja zależy dodatkowo od wybranego kodu. W ujęciu ilościowym jest to różnica między średnią długością reprezentacji a granicą wyznaczoną przez entropię. Dla tego samego źródła dwa kody mogą więc mieć różne wartości redundancji, nawet gdy odtwarzają identyczny komunikat.

Ilościowe Określenie Redundancji

Redundancję można określić bezwzględnie i względnie. Rozważmy źródło $X$ o entropii $H(X)$ oraz kod, którego średnia długość wynosi $L_{\text{avg}}$ bitów na symbol. Dla kodu stałej długości z $n$ symbolami ogólna wartość wynosi $L_{\text{avg}} = \lceil \log_2(n) \rceil$. Gdy $n$ jest potęgą dwójki, $L_{\text{avg}} = \log_2(n)$ i $H_{\text{max}}(X)$ mają tę samą wartość, więc otrzymujemy $L_{\text{avg}} = \log_2(n) = H_{\text{max}}(X)$. Dla innych wartości $n$ część słów kodowych pozostaje niewykorzystana, więc zaokrąglenie ma znaczenie.

• Redundancja Bezwzględna ($R$): Jest to średnia liczba bitów przypadających na symbol ponad entropię.
  $R = L_{\text{avg}} - H(X)$
• Redundancja Względna ($r$): Wyraża nadmiar jako procent całkowitego rozmiaru danych, co daje bezpośrednią miarę ściśliwości.
  $r = \frac{R}{L_{\text{avg}}} = \frac{L_{\text{avg}} - H(X)}{L_{\text{avg}}} = 1 - \frac{H(X)}{L_{\text{avg}}}$

Algorytm bezstratny dąży do reprezentacji, w której $L_{\text{avg}}$ jest możliwie bliskie $H(X)$, więc redundancja $R$ zbliża się do zera. Granica ta dotyczy kodowania długich sekwencji zgodnie z przyjętym modelem źródła. Implementacja ponosi także narzut nagłówków, słowników, tablic kodów lub znaczników potrzebnych do dekodowania.

Przykład: Redundancja w Alfabecie Czterech Symboli

Zastosujmy wzory do Scenariusza 2, w którym użyliśmy kodu stałej długości 2 bitów $(L_{\text{avg}} = 2)$, a entropia wyniosła $H(X) = 1.75$ bita/symbol.

• Redundancja Bezwzględna:$R = 2 - 1.75 = 0.25 \text{ bita/symbol}$. Średnia nadmiarowość wynosi ćwierć bita na symbol.
• Redundancja Względna:$r = 1 - \frac{1.75}{2} = 1 - 0.875 = 0.125$, czyli 12.5%. W tym modelu 12.5% bitów bieżącego kodu stanowi różnicę względem entropii. Rzeczywista redukcja pliku zależy od modelu, długości danych i narzutu formatu, a kodowanie długich sekwencji może teoretycznie zbliżyć średnią długość do entropii.

Źródła i Rodzaje Redundancji w Danych

Prosty model statystyczny pomaga opisać teorię. W rzeczywistych danych zależności występują na wielu poziomach, dlatego redundancja ma kilka różnych postaci. Kodek wybiera model zależnie od typu danych, ponieważ zależności w tekście, obrazie i nagraniu dźwiękowym mają inny charakter.

Redundancja w Tekście

• Nadmiarowość Statystyczna:Litery i słowa nie występują z jednakową częstotliwością. W języku polskim częste sekwencje liter (digramy), takie jak "rz", "sz" i "cz", oraz słowa "i", "w" i "się" mogą otrzymywać krótsze kody w kompresorze.
• Nadmiarowość Składniowa: Reguły gramatyczne ograniczają liczbę poprawnych sekwencji. Zależność między sąsiednimi częściami mowy pozwala modelowi przewidywać kolejne znaki lub słowa i kodować je krócej.
• Nadmiarowość Semantyczna:Znaczenie tekstu zwiększa przewidywalność. W zdaniu "Gdyby kózka nie skakała, to by..." dalszy ciąg "nóżki nie złamała" wynika z kontekstu znanego przysłowia. Prawdopodobny ciąg ma niską autoinformację i zwiększa redundancję wiadomości.

Redundancja w Obrazach i Wideo

• Redundancja Przestrzenna: W obrazie lub pojedynczej klatce wideo sąsiednie piksele są często skorelowane. Piksel na tle nieba może mieć odcień zbliżony do pikseli wokół niego. Redundancję tę ograniczają między innymi RLE w odpowiednich formatach oraz filtrowanie predykcyjne stosowane przed DEFLATE w PNG.
• Redundancja Czasowa: W wideo i audio kolejne próbki lub klatki często są do siebie podobne. W scenie z osobą mówiącą na statycznym tle zmienia się głównie obszar ust i oczu. Redundancja czasowa jest jednym z głównych źródeł oszczędności w kodowaniu wideo, dlatego kodeki takie jak H.264 stosują kompensację ruchu.
• Redundancja Spektralna: W obrazach kolorowych składowe Czerwona, Zielona i Niebieska (RGB) są często silnie powiązane. Na przykład w obrazie w skali szarości $R=G=B$. Znajomość wartości jednego kanału koloru dostarcza wiele informacji o prawdopodobnych wartościach pozostałych.

Rola Modeli Danych

Algorytmy kompresji wykorzystują modele danych do opisu zależności w źródle. Model jest zbiorem reguł i statystyk, które wskazują prawdopodobne wartości kolejnych symboli. Trafniejszy model pozwala wykorzystać więcej zależności i uzyskać krótszą reprezentację, lecz jego opis również musi zostać przekazany dekoderowi.

• Modele bez Pamięci: Proste obliczenie entropii zakłada, że źródło jest "bez pamięci", czyli prawdopodobieństwo symbolu nie zależy od poprzednich symboli. Model bez pamięci opisuje podstawową redundancję statystyczną.
• Modele Markowa: Są to "źródła z pamięcią", które uwzględniają kontekst. Model Markowa pierwszego rzędu wyznacza prawdopodobieństwo następnego znaku na podstawie znaku bezpośrednio poprzedzającego. Prowadzi to do pojęcia entropii warunkowej, czyli entropii przy znanym kontekście. Dla zmiennej kontekstowej zachodzi $H(X|Y) \leq H(X)$, więc różnica może opisywać redundancję ujawnioną przez model. Algorytmy takie jak PPM używają kontekstów o różnej długości i mogą uzyskiwać wysoką skuteczność dla tekstu. Model może więc zastąpić jedną tablicę częstotliwości kilkoma rozkładami warunkowymi wybieranymi na podstawie zaobserwowanego kontekstu.

Entropia wyznacza teoretyczną dolną granicę średniej długości bezstratnego kodu dla określonego modelu źródła i długich sekwencji. Redundancja jest różnicą między tą granicą a używaną reprezentacją. Im bardziej złożone zależności, tym model musi dokładniej je opisywać, aby kompresor mógł je wykorzystać. Dla krótkich komunikatów nagłówki i opis modelu mogą zwiększyć rzeczywisty rozmiar strumienia.