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$ znaków nad alfabetem {'a',...,'z','0',...,'9',' '}. Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu:

1. $a_1$ jest generowany z rozkładu $\mu$