Teoria informacji/TI Ćwiczenia 5

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:

Aby odpowiedzieć na pytania z pkt. 1 skorzystaj z własności entropii łącznej i warunkowej.

Wskazówka II:

W eksperymentach możesz wykorzystać dwa pliki tekstowe:

• naturalny.txt - zawierający fragment tekstu w języku polskim lub angielskim,
• cyfry.txt - zawierający ciąg cyfr z przedziału '1' - '3', generowanych niezależnie z rozkładu równomiernego.

Pamiętaj, aby pliki były dostatecznie długie - tylko wtedy uzyskane wyniki będą wiarygodne.

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=\{spacja\}\cup {\{}^{\prime }{a}^{\prime },...{,}^{\prime }{z}^{\prime }\}\cup {\{}^{\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$ to rozkład jednopunktowy na zbiorze $A_0$ ,
• ${\mu }_1$ to pewien ustalony rozkład prawdopodobieństwa na zbiorze $A_1$ ,
• ${\mu }_2$ to pewien ustalony rozkład prawdopodobieństwa na zbiorze $A_2$ .

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.