Teoria informacji/TI Ćwiczenia 5

Ćwiczenia

Poniższe ćwiczenia służą oswojeniu się z własnościami entropii warunkowej i łącznej.

Ćwiczenie [Warunkowa entropia łączna]

Udowodnij że $H(A,B|C)\le H(A|C)+H(B|C)$,

i równość zachodzi wtedy i tylko wtedy gdy A i B są niezależne w odniesieniu do C, czyli

$p(a\wedge b|c)=p(a|c)\cdot p(b|c)$.

Rozwiązanie

{{{3}}}

Ćwiczenie [Warunkowa entropia dla bliskich rozkładów]

Niech $X^{\prime }$ i $X$ będą dwiema zmiennymi losowymi takimi że $Pr(X^{\prime }\ne X)\le \epsilon$ (dla pewnego małego $\epsilon$).

Pokaż że $H(X^{\prime }|X)$ może być dowolnie duże.

Rozwiązanie

{{{3}}}

Ćwiczenie [Wąskie gardło]

Rozważmy zmienne losowe X, Y, Z tworzące łańcuch Markowa $X\to Y\to Z$ (czyli $Pr(Z=z|X,Y)=Pr(Z=z|Y)$).

Udowodnij że $I(X;Z|Y)=0$ (czyli cała wspólna informacja między X i Z musi zawierać się w Y).

Udowodnij własność wąskiego gardła, mówiącą że $I(X;Z)\le H(Y)$.

Rozwiązanie

{{{3}}}

Laboratorium

Zadanie 1

Treść

Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:

1. Kodowanie Huffmana zastosowane do bloków 2 symboli.
2. Kodowanie kolejnego symbolu pliku, $a_{n+1}$, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, $a_n$.
   W algorytmie tym, dla każdego symbolu $a$ występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, $b$, pod warunkiem $a$: $p(b|a)$. Dla takiego rozkładu symboli $b$ (przy ustalonym $a$) obliczany jest kod Huffmana ${\phi }_a$. Kody są generowane dla wszystkich symboli $a$.
   Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol $a_{n+1}$ kodowany jest za pomocą kodu ${\phi }_{a_n}$. Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania $a_{n+1}$ symbol $a_n$ jest już znany.
3. Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu ${\phi }_{a_{n+1}}$ do zakodowania $a_n$. W tym przypadku ${\phi }_b$ jest kodem wygenerowanym dla rozkładu $p(a|b)$ symboli $a$ poprzedzających ustalony symbol $b$.

Polecenie

1. Porównaj warianty (1) i (2) oraz (2) i (3) pod względem osiąganego stopnia kompresji:
   • Który z wariantów pozwoli uzyskać większy stopień kompresji? Czy zależy to od charakterystyki danych wejściowych? Jeśli to możliwe, podaj ścisły dowód.
   • Czy fakt, że znaki w pliku tekstowym są zapisane w "naturalnej" kolejności, czyli w takiej, w jakiej są odczytywane przez człowieka, pozwala na uzyskanie większego stopnia kompresji za pomocą metody (2) niż (3)?
   • Oprócz wariantów (1)-(3) rozważ też sytuację, gdy zamiast kodu Huffmana stosowany jest kod, którego średnia długość jest dokładnie równa entropii odpowiedniego rozkładu (dla zainteresowanych: kodowanie arytmetyczne jest metodą, która w pewnym sensie pozwala osiągnąć średnią długość kodu równą entropii; zob. arithmetic coding).
2. Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
3. Napisz programy kompresuj1, kompresuj2 i kompresuj3, implementujące algorytmy (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania.

Wskazówki

Wskazówka I:

{{{3}}}

Wskazówka II:

{{{3}}}

Rozwiązanie

Rozwiązanie zadania powinno zawierać:

• wykonywalne programy,
• kody źródłowe programów,
• dane wejściowe wykorzystane do eksperymentów,
• raport zawierający:
  • odpowiedzi na pytania, być może z dowodami,
  • opis wykonanych eksperymentów i wykorzystanych danych wejściowych,
  • interpretację wyników eksperymentów.

Pliki źródłowe i raport należy podpisać imieniem i nazwiskiem autora.

Ocenie podlegać będzie: poprawność i ścisłość rozumowania, poprawność implementacji, umiejętność zaplanowania eksperymentów i interpretacji ich wyników. Nie będzie brana pod uwagę efektywność czasowa i pamięciowa programów.

Zadanie 2

Treść

Dane wejściowe mają postać ciągu $\{a_i{\}}_1^n$ symboli nad alfabetem $A=A_0\cup A_1\cup A_2$, gdzie $A_0=\{spacja\}$, $A_1={\{}^{\prime }{a}^{\prime },...{,}^{\prime }{z}^{\prime }\}$, $A_2={\{}^{\prime }{0}^{\prime },...{,}^{\prime }{9}^{\prime }\}$. Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu prawdopodobieństwa:

• symbol $a_1$ jest generowany z rozkładu $({\mu }_1+{\mu }_2)/2$,
• jeśli $a_n\in A_0$ , to $a_{n+1}$ jest generowany z rozkładu $({\mu }_1+{\mu }_2)/2$,
• jeśli $a_n\in A_1$ , to $a_{n+1}$ jest generowany z rozkładu $({\mu }_0+{\mu }_1)/2$,
• jeśli $a_n\in A_2$ , to $a_{n+1}$ jest generowany z rozkładu $({\mu }_0+{\mu }_2)/2$,

gdzie ${\mu }_0$, ${\mu }_1$ i ${\mu }_2$ to rozkłady prawdopodobieństwa na zbiorze $A$ takie, że:

• ${\mu }_0(A_0)=1$ (czyli rozkład ${\mu }_0$ jest skupiony na zbiorze $A_0$ ),
• ${\mu }_1(A_1)=1$,
• ${\mu }_2(A_2)=1$.

Polecenie

1. Opracuj możliwie najskuteczniejszą metodę kompresji danych o powyższej charakterystyce, opartą na kodowaniu Huffmana. Zaimplementuj ją.
2. Oszacuj teoretycznie ile średnio bitów $L$ pliku skompresowanego będzie przypadało na jeden symbol pliku wejściowego. Przyjmij, że znana jest entropia rozkładów ${\mu }_1$ i ${\mu }_2$ .
3. Wykonaj eksperymenty, aby sprawdzić swoje przewidywania. Wygeneruj kilka ciągów o podanej wyżej charakterystyce, dla różnych wyborów rozkładów ${\mu }_1$ i ${\mu }_2$ , skompresuj je Twoją metodą i porównaj rozmiary plików wejściowych i wynikowych.
4. Oszacuj teoretycznie wartość $L$ dla zwykłej kompresji Huffmana zastosowanej do danych o podanej charakterystyce. Czy Twój algorytm osiąga lepszą kompresję?
5. Jaka dodatkowa informacja musiałaby być zapisana w skompresowanym pliku, aby umożliwić jego dekompresję? Oszacuj jej rozmiar.

Wskazówka:

W algorytmie kompresji wykorzystaj jednocześnie kilka różnych kodów Huffmana.

Zadanie 3 (konkurs)

Wstęp

Prowadzący powinien przygotować dwa pliki, dane1 i dane2, zawierające dane o pewnej szczególnej charakterystyce (takiej samej w obu plikach). Plik dane1 zostanie udostępniony studentom, którzy na jego podstawie będą musieli określić typ redundacji występującej w danych i opracować możliwie najskuteczniejszy algorytm kompresji oparty na kodowaniu Huffmana.

Każdy student zaimplementuje swój algorytm w postaci dwóch programów, kompresuj i dekompresuj. Programy zostaną przesłane do prowadzącego, który wykona za ich pomocą następujące czynności:

1. skompresuje plik dane2, otrzymując plik skompresowany,
2. zdekompresuje plik skompresowany, otrzymując plik zdekompresowany,
3. jeśli pliki dane2 i zdekompresowany będą identyczne, przyzna autorowi danego algorytmu liczbę punktów równą: <rozmiar_pliku_dane2> / <rozmiar_pliku_skompresowany>,
4. w przeciwnym przypadku (gdy pliki się różnią), przyzna 0 punktów.

Wygra student, który otrzyma najwięcej punktów, czyli ten, którego program poprawnie skompresuje i zdekompresuje plik dane2, uzyskując przy tym największy stopień kompresji. Prowadzący może też osobno przyznawać punkty za pomysłowość w opracowaniu algorytmu, wówczas punkty może otrzymać też student, którego implementacja okazała się niepoprawna.

W celu opracowania skutecznego algorytmu kompresji studenci będą musieli wykonać dokładną analizę (np. statystyczną) pliku dane1. Prowadzący może też podać dodatkowe informacje, np. źródło pochodzenia danych i ich znaczenie -- ułatwi to opracowanie skutecznego algorytmu.

Przykład

Fragment pliku dane1 lub dane2 może wyglądać następująco (uwaga: zwykle oba pliki powinny być znacznie dłuższe):

3             6             1998         40.6
3             7             1998         44.2
3             8             1998         42.5
3             9             1998         47.6
3             10            1998         47.1
3             11            1998         29.0
3             12            1998         25.2
3             13            1998         29.5
3             14            1998         37.9
3             15            1998         38.1
3             16            1998         35.1
3             17            1998         37.8
3             18            1998         38.2
3             19            1998         38.8
3             20            1998         40.6
3             21            1998         38.0
3             22            1998         33.7
3             23            1998         38.2
3             24            1998         42.6
3             25            1998         41.1
3             26            1998         46.6
3             27            1998         63.6
3             28            1998         69.9
3             29            1998         67.7
3             30            1998         68.1
3             31            1998         72.0

Powyższe dane są zapisem dziennych temperatur w Nowym Jorku, wyrażonych w stopniach Fahrenheita. Pochodzą ze strony Uniwersytetu w Dayton.

Znakomitym źródłem danych o przeróżnych charakterystykach jest Internet. Inne przykłady: ...