Teoria informacji/TI Ćwiczenia 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
== Zadanie 1: kompresja danych == | == Zadanie 1: kompresja danych == | ||
=== | ==== Polecenie ==== | ||
# 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 [http://gutenberg.org Projektu Gutenberg]. | # 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 [http://gutenberg.org Projektu Gutenberg]. | ||
| Linia 19: | Linia 19: | ||
Prowadzący laboratorium może zrezygnować z części zadania, np. z implementacji kodowania Shannona-Fano. | Prowadzący laboratorium może zrezygnować z części zadania, np. z implementacji kodowania Shannona-Fano. | ||
=== Rozwiązanie === | ==== Rozwiązanie ==== | ||
Rozwiązanie zadania powinno zawierać: | Rozwiązanie zadania powinno zawierać: | ||
| Linia 38: | Linia 38: | ||
# Kodowanie kolejnego symbolu pliku, <math>a_{n+1}</math>, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, <math>a_n</math>. <br/> W algorytmie tym, dla każdego symbolu <math>a</math> występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, <math>b</math>, pod warunkiem <math>a</math>: <math>p(b|a)</math>. Dla takiego rozkładu symboli <math>b</math> (przy ustalonym <math>a</math>) obliczany jest kod Huffmana <math>\varphi_a</math>. Kody są generowane dla wszystkich symboli <math>a</math>. <br/> Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol <math>a_{n+1}</math> kodowany jest za pomocą kodu <math>\varphi_{a_n}</math>. Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania <math>a_{n+1}</math> symbol <math>a_n</math> jest już znany. | # Kodowanie kolejnego symbolu pliku, <math>a_{n+1}</math>, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, <math>a_n</math>. <br/> W algorytmie tym, dla każdego symbolu <math>a</math> występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, <math>b</math>, pod warunkiem <math>a</math>: <math>p(b|a)</math>. Dla takiego rozkładu symboli <math>b</math> (przy ustalonym <math>a</math>) obliczany jest kod Huffmana <math>\varphi_a</math>. Kody są generowane dla wszystkich symboli <math>a</math>. <br/> Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol <math>a_{n+1}</math> kodowany jest za pomocą kodu <math>\varphi_{a_n}</math>. Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania <math>a_{n+1}</math> symbol <math>a_n</math> jest już znany. | ||
# Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu <math>\varphi_{a_{n+1}}</math> do zakodowania <math>a_n</math>. W tym przypadku <math>\varphi_b</math> jest kodem wygenerowanym dla rozkładu <math>p(a|b)</math> symboli <math>a</math> poprzedzających ustalony symbol <math>b</math>. | # Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu <math>\varphi_{a_{n+1}}</math> do zakodowania <math>a_n</math>. W tym przypadku <math>\varphi_b</math> jest kodem wygenerowanym dla rozkładu <math>p(a|b)</math> symboli <math>a</math> poprzedzających ustalony symbol <math>b</math>. | ||
==== Polecenie ==== | |||
# 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. <div class="mw-collapsible mw-made=collapsible mw-collapsed"> Wskazówka: <div class="mw-collapsible-content" style="display:none">skorzystaj z własności entropii łącznej i warunkowej. </div></div> | |||
#* 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). | |||
#* 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 przez metodę (2) niż (3)? | |||
# Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)? | |||
# Zaimplementuj każdy z wariantów (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania. W eksperymentach wykorzystaj przynajmniej dwa pliki tekstowe, każdy o długości co najmniej 50000 znaków: | |||
#* <tt>naturalny.txt</tt> - tekst w języku polskim lub angielskim, | |||
#* <tt>cyfry.txt</tt> - ciąg cyfr '0'-'9' wygenerowanych niezależnie z rozkładu jednostajnego. | |||
[Uwagi: zadanie wymaga znajomości entropii produktowej i zależnej.] | [Uwagi: zadanie wymaga znajomości entropii produktowej i zależnej.] | ||
Wersja z 14:11, 22 lip 2006
Zadanie 1: kompresja danych
Polecenie
- 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.
- 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.
- 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ą. - 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".
- 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?
- 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
Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:
- Kodowanie Huffmana zastosowane do bloków 2 symboli.
- Kodowanie kolejnego symbolu pliku, , za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, .
W algorytmie tym, dla każdego symbolu występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, , pod warunkiem : . Dla takiego rozkładu symboli (przy ustalonym ) obliczany jest kod Huffmana . Kody są generowane dla wszystkich symboli .
Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol kodowany jest za pomocą kodu . Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania symbol jest już znany. - Kodowanie analogiczne do (2), jednak przebiegające od końca pliku do początku, zatem korzystające z kodu do zakodowania . W tym przypadku jest kodem wygenerowanym dla rozkładu symboli poprzedzających ustalony symbol .
Polecenie
- 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. Wskazówka:
- 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).
- 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 przez metodę (2) niż (3)?
- 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.
- Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
- Zaimplementuj każdy z wariantów (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania. W eksperymentach wykorzystaj przynajmniej dwa pliki tekstowe, każdy o długości co najmniej 50000 znaków:
- naturalny.txt - tekst w języku polskim lub angielskim,
- cyfry.txt - ciąg cyfr '0'-'9' wygenerowanych niezależnie z rozkładu jednostajnego.
[Uwagi: zadanie wymaga znajomości entropii produktowej i zależnej.]
