Teoria informacji/TI Ćwiczenia 3

Zadanie 1

Polecenie

1. Przygotuj trzy pliki, zawierające tekst w trzech różnych językach: polskim, angielskim i trzecim dowolnie wybranym. Każdy plik powinien zawierać przynajmniej 50000 znaków. Duży wybór tekstów w różnych językach można znaleźć na przykład na stronie Projektu Gutenberg.
2. Napisz program litery, który czyta plik tekstowy o podanej nazwie (przekazanej jako parametr wywołania programu) i wypisuje wszystkie symbole występujące w pliku wraz z ich częstością, w formie: A 0.134 <nowa_linia> b 0.126 ... Nie musi poprawnie wypisywać znaków narodowych. Program powinien wypisać też entropię binarną obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki.
3. Napisz program huffman, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana dla rozkładu symboli występujących w tym pliku. Program powinien wypisać otrzymany kod w formie: A 001 <nowa_linia> b 0001010 ...
   Napisz program shannon, który oblicza kod Shannona-Fano. Uwaga: aby otrzymać poprawny kod Shannona-Fano, nie można korzystać w obliczeniach z liczb zmiennoprzecinkowych (dlaczego?), jedynie z liczb całkowitych. Prawdopodobieństwo danego symbolu można pomnożyć przez ustaloną liczbę całkowitą (najlepiej potęgę 2, np. 65536) i zaokrąglić, otrzymując w ten sposób reprezentację całkowitoliczbową.
4. Napisz program kompresuj, który koduje podany plik tekstowy plik.txt za pomocą kodu Huffmana i Shannona-Fano. Wynik kodowania powinien zostać zapisany do plików plik.huf i plik.sf. Dla ułatwienia można każdy bit wynikowego kodu zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
5. Uruchom program kompresuj dla trzech przygotowanych plików tekstowych. Dla każdego z nich porównaj następujące wielkości:
   • liczbę bitów oryginalnego pliku,
   • liczbę znaków "0" i "1" w plikach .huf i .sf,
   • entropię rozkładu prawdopodobieństwa symboli w oryginalnym pliku.
     Czy te wielkości zależą od języka kompresowanego tekstu?
6. Napisz program kompresujbloki, który kompresuje podany plik metodą Huffmana i Shannona-Fano, zastosowanymi do bloków długości 2, 3, 4 lub więcej (tzn. kod jest generowany nie dla pojedynczych symboli, lecz dla par, trójek, czwórek ... sąsiednich symboli). Porównaj efektywność kompresji pojedynczych symboli i bloków, pod względem:
   • rozmiaru zakodowanego pliku,
   • rozmiaru kodu (aby móc wykonać dekompresję, kod musi być zapisany razem z zakodowaną informacją),
   • złożoności czasowej i pamięciowej algorytmu.

Prowadzący laboratorium może zrezygnować z części zadania, np. z implementacji kodowania Shannona-Fano.

Rozwiązanie

Rozwiązanie zadania powinno zawierać:

• wykonywalne programy,
• kody źródłowe programów,
• pliki tekstowe wykorzystane do eksperymentów,
• raport z analizą otrzymanych wyników i odpowiedziami na postawione wyżej pytania.

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

Ocenie podlegać będzie poprawność implementacji oraz umiejętność analizy i interpretacji wyników eksperymentalnych. Dodatkowe programy, eksperymenty, komentarze będą mile widziane. Nie będzie natomiast brana pod uwagę efektywność czasowa i pamięciowa programów.

[Uwagi: jest to przetłumaczone zadanie Hugo, trochę skrócone i z niewielkimi modyfikacjami. Zadanie jest elementarne - implementacja podstawowego algorytmu kompresji - bez niego nie da się robić kolejnych zadań (ew. można pominąć kodowanie bloków albo wydzielić jako osobne zadanie).]

Zadanie 2

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 jednostajnego.

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.

[Uwagi: zadanie wymaga znajomości pojęcia entropii łącznej i warunkowej.]