Wprowadzenie: Waluta Kompresji

Po ustaleniu dwóch wielkich domen kompresji danych, bezstratnej i stratnej, zagłębiamy się w silnik napędzający kompresję bezstratną. Wiemy, że algorytmy bezstratne działają poprzez idealne odtworzenie oryginalnych danych. Oznacza to, że nie odrzucają żadnej informacji, a jedynie znajdują bardziej wydajny sposób na jej reprezentację. Ta wydajność pochodzi z jednego kluczowego zasobu: nadmiarowości.

Nadmiarowość (redundancja) to "tłuszcz" w danych, przewidywalne i powtarzające się części, które można "wycisnąć" bez utraty istotnej substancji. Prawdziwa, esencjonalna substancja danych to ich zawartość informacyjna. Dziedzina matematyki zwana Teorią Informacji, której pionierem był Claude Shannon, dostarcza nam narzędzi do precyzyjnego pomiaru obu tych wielkości. W tej sekcji zgłębimy pojęcia Entropii, która mierzy prawdziwą informację, oraz Redundancji, która mierzy kompresowalne marnotrawstwo. Zrozumienie relacji między nimi jest kluczem do zrozumienia, dlaczego, jak i o ile dowolny fragment danych może być skompresowany bezstratnie. Bez redundancji kompresja bezstratna jest niemożliwa.

Dogłębne Spojrzenie na Entropię: Miarę Prawdziwej Informacji

Jak wspomniano wcześniej, entropia to średnia zawartość informacji na symbol ze źródła danych. Ilościowo określa ona poziom niepewności lub losowości nieodłącznie związany z danymi. Przyjrzyjmy się ponownie wzorowi i zbadajmy jego właściwości, aby uzyskać głębsze zrozumienie. Entropia $H(X)$ źródła $X$, które generuje symbole $x_i$ z prawdopodobieństwami $P(x_i)$, jest dana wzorem:

Kluczowe Właściwości Entropii

Ten wzór ma kilka ważnych właściwości, które idealnie pasują do naszej intuicji na temat informacji i niepewności:

• Entropia Maksymalna: Dla źródła, które może generować stałą liczbę $n$ różnych symboli, entropia osiąga swoje maksimum, gdy wszystkie symbole są jednakowo prawdopodobne. W tym stanie maksymalnej nieprzewidywalności każdy symbol ma prawdopodobieństwo $P(x_i) = 1/n$. Maksymalna entropia wynosi wtedy $H_{\text{max}}(X) = \log_2(n)$. Źródło o maksymalnej entropii jest jak idealnie losowa sekwencja; nie zawiera żadnych wzorców statystycznych i dlatego jest najtrudniejsze do skompresowania.
• Entropia Minimalna (Zerowa Entropia): Entropia wynosi zero wtedy i tylko wtedy, gdy nie ma żadnej niepewności. Dzieje się tak, gdy jeden symbol na pewno wystąpi (prawdopodobieństwo 1), a wszystkie inne są niemożliwe (prawdopodobieństwo 0). Wiadomość z takiego źródła jest całkowicie przewidywalna. Ponieważ nie ma zaskoczenia, nie ma też informacji. Na przykład źródło, które zawsze generuje tylko literę "A", ma entropię równą zero.
• Nieujemność: Wartość entropii jest zawsze zerowa lub dodatnia. Nie jest możliwe posiadanie ujemnej ilości informacji.

Analiza Przypadku: Alfabet Czterech Symboli

Rozważmy proste źródło danych, które generuje wiadomości używając tylko czterech możliwych symboli: A, B, C i D.

Załóżmy, że źródło jest całkowicie losowe, co oznacza, że każdy symbol ma taką samą szansę na pojawienie się:

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

Prosty kod o stałej długości do reprezentacji tych symboli to A=00, B=01, C=10, D=11. Średnia długość tego kodu wynosi dokładnie 2 bity na symbol. Ponieważ ta średnia długość jest równa entropii, to kodowanie jest idealnie optymalne. Nie ma żadnej redundancji do usunięcia; źródło jest już tak zwarte, jak to tylko możliwe.

Teraz załóżmy, że źródło jest tendencyjne. Niektóre symbole są bardziej prawdopodobne niż inne, co wprowadza wzorzec i pewną przewidywalność.

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

Zauważ, że entropia (1.75 bita/symbol) jest teraz mniejsza niż maksymalna możliwa entropia (2 bity/symbol). Ten spadek entropii jest bezpośrednią miarą przewidywalności, którą wprowadziliśmy. Jeśli nadal używamy naszego prostego kodu 2-bitowego (A=00, B=01, itd.), to średnio używamy więcej bitów niż jest to teoretycznie konieczne. Różnica między 2 bitami, których używamy, a 1.75 bitami prawdziwej zawartości informacyjnej to właśnie redundancja.

Redundancja (Nadmiarowość): Miara Marnotrawstwa

Redundancja jest "drugą stroną medalu" w stosunku do entropii. Podczas gdy entropia mierzy niezbędną, nieprzewidywalną informację, redundancja mierzy przewidywalną, powtarzalną i ostatecznie kompresowalną część danych. Jest to różnica między tym, jak dane są obecnie reprezentowane, a najmniejszą możliwą reprezentacją zdefiniowaną przez ich entropię.

Ilościowe Określanie Redundancji

Możemy określić redundancję zarówno w ujęciu bezwzględnym, jak i względnym. Rozważmy źródło danych $X$ o entropii $H(X)$, używające schematu kodowania, w którym średnia liczba bitów na symbol wynosi $L_{\text{avg}}$. Dla prostego kodu o stałej długości z $n$ symbolami, ta średnia długość wynosi $L_{\text{avg}} = \log_2(n)$, co jest równe maksymalnej możliwej entropii $H_{\text{max}}(X)$.

• Redundancja Bezwzględna ($R$): Jest to średnia liczba zmarnowanych bitów na symbol.
  $R = L_{\text{avg}} - H(X)$
• Redundancja Względna ($r$): Wyraża zmarnowaną część jako procent całkowitego rozmiaru danych, dostarczając bardziej intuicyjnej miary ś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}}}$

Ostatecznym celem każdego algorytmu kompresji bezstratnej jest stworzenie nowej reprezentacji danych, w której $L_{ ext{avg}}$ jest jak najbliższe $H(X)$, co jest równoznaczne ze sprowadzeniem redundancji $R$ jak najbliżej zera.

Przykład Ponownie: Redundancja w Naszym Alfabecie Czterech Symboli

Zastosujmy te wzory do Scenariusza 2 naszego alfabetu o czterech symbolach, gdzie użyliśmy 2-bitowego kodu o stałej długości $(L_{ ext{avg}} = 2)$ i obliczyliśmy entropię na $H(X) = 1.75$ bita/symbol.

• Redundancja Bezwzględna:$R = 2 - 1.75 = 0.25 \text{ bita/symbol}$. Średnio marnujemy ćwierć bita na każdy kodowany symbol.
• Redundancja Względna:$r = 1 - \frac{1.75}{2} = 1 - 0.875 = 0.125$, czyli 12.5%. Mówi nam to, że 12.5% naszych zakodowanych danych to czysta redundancja, którą teoretycznie można by usunąć. Wartość ta reprezentuje również maksymalną potencjalną redukcję rozmiaru, jaką moglibyśmy osiągnąć za pomocą idealnego algorytmu kompresji bezstratnej dla tego źródła danych.

Źródła i Rodzaje Redundancji w Prawdziwych Danych

Proste modele statystyczne, których użyliśmy, są przydatne do zrozumienia teorii. Jednak w prawdziwych danych redundancja jest o wiele bardziej złożona i pojawia się w wielu formach.

Redundancja w Tekście

• Nadmiarowość Statystyczna: Najbardziej oczywisty typ. Jak zauważono, litery i słowa nie pojawiają się z równą częstotliwością. W języku polskim częste sekwencje liter (digramy), takie jak "rz", "sz", "cz", oraz popularne słowa, takie jak "i", "w", "się", tworzą ogromną redundancję statystyczną. Algorytm kompresji może to wykorzystać, używając krótszych kodów dla tych popularnych elementów.
• Nadmiarowość Składniowa: Reguły gramatyki czynią język przewidywalnym. Rzeczownik prawdopodobnie będzie poprzedzony przymiotnikiem, a po nim nastąpi czasownik. Ta struktura gramatyczna ogranicza możliwe prawidłowe sekwencje, tworząc kolejną warstwę redundancji.
• Nadmiarowość Semantyczna: Znaczenie tekstu dodaje jeszcze jedną warstwę przewidywalności. Rozważmy zdanie: "Gdyby kózka nie skakała, to by...". Ostatnie słowo jest wysoce przewidywalne ("nóżki nie złamała") ze względu na kontekst semantyczny znanego przysłowia. To wysoce prawdopodobne słowo niesie bardzo mało nowych informacji (niską autoinformację) i przyczynia się do ogólnej redundancji wiadomości.

Redundancja w Obrazach i Wideo

• Redundancja Przestrzenna: W pojedynczym obrazie lub klatce wideo sąsiednie piksele są silnie skorelowane. Piksel pośrodku niebieskiego nieba jest niezwykle prawdopodobne, że będzie miał ten sam odcień niebieskiego, co piksele go otaczające. Ta przestrzenna przewidywalność jest ogromnym źródłem redundancji, którą eliminują algorytmy takie jak RLE czy kodowanie predykcyjne używane w formacie PNG.
• Redundancja Czasowa: Jest to unikalne dla wideo i audio. W strumieniu wideo kolejne klatki są często niemal identyczne. W scenie z osobą mówiącą na statycznym tle jedyne, co zmienia się między klatkami, to piksele wokół ust i oczu osoby. Redundancja czasowa jest największym pojedynczym źródłem "marnotrawstwa" w surowych danych wideo, a jej usunięcie za pomocą technik takich jak kompensacja ruchu jest głównym zadaniem kodeków wideo, takich jak H.264.
• 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

Aby skutecznie wykorzystać te złożone formy redundancji, algorytmy kompresji używają modeli danych. Model to zbiór reguł i danych statystycznych, który próbuje opisać strukturę informacji źródłowej. Lepszy model potrafi zidentyfikować głębsze wzorce, a tym samym umożliwić lepszą kompresję.

• Modele bez Pamięci: Proste obliczenie entropii, które wykonaliśmy, zakłada, że źródło jest "bez pamięci", co oznacza, że prawdopodobieństwo symbolu nie zależy od poprzednich symboli. Model ten wychwytuje tylko podstawową redundancję statystyczną.
• Modele Markowa: Są to bardziej zaawansowane "źródła z pamięcią". Wychwytują one redundancję składniową, biorąc pod uwagę kontekst. Na przykład model Markowa pierwszego rzędu oblicza prawdopodobieństwo następnego znaku na podstawie bezpośrednio go poprzedzającego. Prowadzi to do pojęcia entropii warunkowej, czyli entropii źródła, biorąc pod uwagę znajomość jego kontekstu. Entropia warunkowa jest zawsze mniejsza lub równa prostej entropii, a ta różnica określa dodatkową redundancję wychwyconą przez bardziej zaawansowany model.

Podsumowując, entropia dostarcza teoretycznej dolnej granicy dla kompresji bezstratnej, określając ilościowo prawdziwą, nieredukowalną informację w źródle danych. Redundancja to mierzalne "marnotrawstwo" w reprezentacji danych, które algorytmy kompresji starają się wyeliminować. Im bardziej złożona jest redundancja, tym bardziej zaawansowany model danych jest potrzebny do jej skutecznej identyfikacji i usunięcia.