22 Dygresja: kompresja

22.1 Wprowadzenie

Załóżmy, że dysponujemy następującym słownikiem \[\begin{equation*} \mathcal{A} = \{a,b,c,d,e,f,g,h\}. \end{equation*}\] Wówczas każdą wiadomość złożoną z jednego słowa możemy zakodować za pomocą trzech bitów.

x	a	b	c	d	e	f	g	h
c(x)	000	001	010	011	100	101	110	111

Podobnie, każdą wiadomość składającą się z \(N \in \mathbb{N}\) słów możemy zakodować za pomocą \(3N\) bitów. Załóżmy, że każde słowo pojawia się z pewnym prawdopodobieństwem

x	a	b	c	d	e	f	g	h
P(x)	1/4	1/4	1/4	3/64	1/64	1/64	1/64	1/64

Wówczas \[\begin{equation*} \mathbb{P}[a,b,c,d]=15/16. \end{equation*}\] Jeśli jesteśmy gotowi zaryzykować, to możemy zakodować słowa za pomocą dwóch bitów

x	a	b	c	d	e	f	g	h
c(x)	00	01	10	11	-	-	-	-

Wówczas z prawdopodobieństwem \(15/16\) jesteśmy w stanie poprawnie zakodować wiadomość. Prawdopodobieństwo, że wiadomość składająca się z jednego słowa nie zostanie odczytana wynosi \(1/16\).

22.2 Długie wiadomości

Chcemy teraz kodować długie wiadomości. Niech \(M \in \mathbb{N}\). Zakładać będziemy, że nasz słownik jest postaci \(\mathcal{A} = \{1,2, \ldots , M\} = [M]\). Dla \(j \in \mathbb{N}\) niech \(X_j\) będzie \(j\)-tym słowem losowej wiadomości. Zakładać będziemy, że zmienne \(\{X_j\}_{j \in \mathbb{N}}\) są niezależne z rozkładem \[\begin{equation*} \mathbb{P}[X_j=k] = p_k \end{equation*}\] dla pewnych liczb \(p_k \in [0,1]\) takich, że \(\sum_{k=1}^Mp_k =1\). Niech \(N \in \mathbb{N}\). \(N\)-wymiarowy wektor losowy \(\vec{X} = (X_1, X_2, \ldots, X_N)\) jest internującą nas wiadomością, którą chcemy zakodować (zapisać) za pomocą możliwie małej liczby bitów.

Jeżeli \(\vec{a} = (a_1, \ldots, a_N)\) jest typową wiadomością, to spodziewamy się, że \[\begin{equation*} \mathrm{P}(\vec{a}) = \mathbb{P}\left[\vec{X}=\vec{a}\right] = p_{a_1}p_{a_2}\cdots p_{a_N} \sim p_1^{p_1N} \cdot p_2^{p_2N} \cdots p_M^{p_MN} \end{equation*}\] Zatem \[\begin{equation*} \log_2\left(1/\mathrm{P}(\vec{a}) \right) \sim N \sum_{k=1}^M p_k\log_2(1/p_k). \end{equation*}\] Liczbę \[\begin{equation*} H= \sum_{k=1}^M p_k\log(1/p_k) \end{equation*}\] nazywamy entropią rozkładu \((p_1, \ldots, p_M)\). Dla \(\epsilon>0\) rozważmy zbiór \[\begin{equation*} T_{N,\epsilon} = \left\{ \vec{a} \in \mathcal{A}^N \: :\: \left| \frac 1N \log_2 (1/\mathrm{P}(\vec{a})) -H \right| <\epsilon \right\} \end{equation*}\] tych słów długości \(N\), których prawdopodobieństwo jest między \(2^{-N(H+\epsilon)}\) a \(2^{-N(H-\epsilon)}\). Okazuje się, że typowe wiadomości są w \(T_{N,\epsilon}\). Rzeczywiście \(\vec{X} \in T_{N,\epsilon}\) wtedy i tylko wtedy, gdy \[\begin{equation*} \left| \frac 1N \log_2 (1/\mathrm{P}(\vec{X})) -H \right| <\epsilon. \end{equation*}\] Zauważmy, że \[\begin{equation*} \frac 1N \log_2 (1/\mathrm{P}(\vec{X})) = \frac 1N \log_2 \left( \frac 1{p_{X_1}p_{X_2}\cdots p_{X_N} } \right) = \frac 1N\sum_{k=1}^N \log_2(1/p_{X_j}). \end{equation*}\] Korzystając z Mocnego prawa wielkich liczb \[\begin{equation*} \frac 1N\sum_{k=1}^N \log_2(1/p_{X_j}) \to \mathbb{E}\left[ \log_2(1/p_{X_1}) \right] \end{equation*}\] prawie na pewno. Mamy \[\begin{equation*} \mathbb{E}\left[ \log_2(1/p_{X_1}) \right] = \sum_{k=1}^M \mathbb{P}[X_1=k] \log_2(1/p_{k}) = \sum_{k=1}^M p_k\log_2(1/p_k) = H. \end{equation*}\] Podsumowując, z prawdopodobieństwem jeden \[\begin{equation*} \frac 1N \log_2 (1/\mathrm{P}(\vec{X})) \to H. \end{equation*}\] Zauważmy, że \[\begin{equation*} 1 \geq \mathbb{P}\left[ \vec{X} \in T_{N, \epsilon} \right] = \sum_{\vec{a} \in T_{N,\epsilon}} \mathrm{P}(\vec{a}) \geq 2^{-N(H+\epsilon)} \left|T_{N,\epsilon}\right|. \end{equation*}\] Stąd \[\begin{equation*} \left| T_{N,\epsilon} \right| \leq 2^{N(H+\epsilon)}. \end{equation*}\] Do zakodowania typowej wiadomości potrzebujemy więc \(N(H+\epsilon)\) bitów. Zauważmy, że z nierówności Jensena \[\begin{equation*} H = \sum_{k=1}^M p_k \log_2(1/p_k) \leq \log_2 \left(\sum_{k=1}^M 1 \right) = \log_2(M). \end{equation*}\] Przy czym równość zachodzi jedynie w przypadku \(p_k=1/M\). Jeżeli więc rozkład \((p_1, \ldots , p_M)\) nie jest jednostajny, to \(H<\log_2(M)\). Wówczas dla dostatecznie małego \(\epsilon>0\), \(H+\epsilon< \log_2(M)\). Wtedy \[2^{N(H+\epsilon)} \ll 2^{N\log_2(M)} = \left|\mathcal{A}^N \right|. \] Z prawdopodobieństwem bliskim jeden, każdą wiadomość długości \(N\) jesteśmy w stanie zapisać za pomocą \(N(H+\epsilon)\) bitów. Skoro \(H+\epsilon<\log_2(M)\) oznacza to, że jesteśmy w stanie skompresować dane.

Można pokazać, że \(H\) jest optymalne. Dokładniej nie jest możliwa kompresja do \(N(H-\epsilon)\) bitów. Wówczas prawdopodobieństwo poprawnego odczytania wiadomości jest oddalone od jeden.