Podręcznik

1. Matematyczna modelowanie informacji

1.4. Entropia modelu źródła z pamięcią

Zależności pomiędzy danymi w strumieniu zwykle lepiej opisuje model z pamięcią, a wartość entropii tego źródła (tzw. entropii warunkowej) jest bliższa rzeczywistej ilości informacji zawartej w kompresowanym zbiorze danych. Zależność pomiędzy entropią łączną $H(C,S)$ źródła o zdefiniowanym kontekście $C$ , warunkową $H(S|C)$ oraz tzw. entropią brzegową (entropią źródła obliczoną dla rozkładu brzegowego) $H(C)$ jest następująca:

$H(C,S)=H(S|C)+H(C)$

(1.6)

Przykładem miary ilości informacji źródeł z pamięcią będzie entropia wyznaczona dla źródeł Markowa, znajdujących bardzo częste zastosowanie w praktyce kompresji.

Entropia modelu źródła Markowa
Aby za pomocą modelu źródła Markowa rzędu $m$ obliczyć ilość informacji (średnio na symbol źródła) zawartą w kodowanym zbiorze danych, wykorzystuje się zbiór prawdopodobieństw warunkowych i określa tzw. entropię warunkową źródła znajdującego się w pewnym stanie $(a_{j_{1}},a_{j_{2}},\ldots,a_{j_{m}})$ jako:

$H(S|a_{j_{1}},a_{j_{2}},\ldots,a_{j_{m}})=-\sum_{i=1}^{n}P(a_{i}|a_{j_{1}},\ldots,a_{j_{m}})\log_{2}P(a_{i}|a_{j_{1}},\ldots,a_{j_{m}})$

(1.7)

Następnie oblicza się średnią entropię warunkową źródła S jako sumę ważoną entropii warunkowych po kolejnych stanach źródła wynikających ze wszystkich możliwych konfiguracji (stanów) kontekstu $C^{(m)}$ : $\quad A_{C^{(m)}}^{S}=\{\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{j},\ldots,\mathbf{b}_{k}\}$ , gdzie $\mathbf{b}_{j}=(a_{j_{1}},\ldots,a_{j_{m}})$ oraz $\forall_{l\in \{1,\ldots,m\}}a_{j_{l}}\in A_{S}$ , przy czym wagami są prawdopodobieństwa przebywania źródła w danym stanie:

$H(S|C^{(m)})=\sum_{A_{C^{(m)}}^{S}}P(a_{j_{1}},\ldots,a_{j_{m}})H(S|a_{j_{1}},\ldots,a_{j_{m}})$

(1.8)

czyli

$H(S|C^{(m)})=-\sum_{j_{1}=1}^{n}\cdots \sum_{j_{m}=1}^{n}\sum_{i=1}^{n}P(a_{j_{1}},\ldots,a_{j_{m}},a_{i})\log_{2}P(a_{i}|a_{j_{1}},\ldots,a_{j_{m}})$

Tak określona średnia entropia warunkowa modelu źródła Markowa rzędu $m$ jest mniejsza lub równa entropii bezwarunkowej. Jest ona pomniejszona o średnią ilość informacji zawartą w kontekście wystąpienia każdego symbolu strumienia danych. Jednocześnie entropia warunkowa danych przybliżanych źródłem Markowa rzędu $m$ jest niemniejsza niż entropia łączna źródła emitującego tę sekwencję danych (według równania (1.4)). Zależność pomiędzy postaciami entropii związanymi z przedstawionymi modelami źródeł informacji, opisującymi z większym lub mniejszym przybliżeniem informację zawartą w konkretnym zbiorze danych, jest następująca:

$H(S)\leq H(S|C^{(m)})\leq H(S_{\textrm{DMS}})$

(1.9)

Zastosowanie modeli CSM wyższych rzędów zazwyczaj lepiej określa rzeczywistą informację zawartą w zbiorze danych, co pozwala zwiększyć potencjalną efektywność algorytmów kompresji wykorzystujących te modele. W zależności od charakteru kompresowanych danych właściwy dobór kontekstu może wtedy zmniejszyć graniczną długość reprezentacji kodowej. Stosowanie rozbudowanych modeli CSM w konkretnych implementacjach napotyka jednak na szereg trudności, wynikających przede wszystkim z faktu, iż ze wzrostem rzędu kontekstu liczba współczynników opisujących model rośnie wykładniczo. Wiarygodne statystycznie określenie modeli zaczyna być wtedy problemem. Trudniej jest także zrealizować algorytmy adaptacyjne, co w efekcie może zmniejszyć skuteczność kompresji w stosunku do rozwiązań wykorzystujących prostsze modele.