Teoria informacji/TI Ćwiczenia 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
mNie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 29: | Linia 29: | ||
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. | 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. | ||
== 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, <math>a_{n+1}</math>, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, <math>a_n</math>. 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 obliczany jest kod Huffmana. | |||
<!-- | <!-- | ||
| Linia 35: | Linia 41: | ||
* przewidywanie kolejnego symbolu na podstawie poprzedniego | * przewidywanie kolejnego symbolu na podstawie poprzedniego | ||
* od końca: przewidywanie poprzedniego na podstawie następnego | * od końca: przewidywanie poprzedniego na podstawie następnego | ||
Który wariant powinien być najlepszy? Porównaj, udowodnij, skomentuj, zaimplementuj. | Który wariant powinien być najlepszy? Porównaj (stopień kompresji, złożoność pamięciowa), udowodnij, skomentuj, zaimplementuj. | ||
Przeprowadź rozumowanie dla dwóch sytuacji: słowa kodowe muszą mieć długość całkowitą lub nie muszą. (dla zainteresowanych: zob. kodowanie arytmetyczne) | Przeprowadź rozumowanie dla dwóch sytuacji: słowa kodowe muszą mieć długość całkowitą lub nie muszą. (dla zainteresowanych: zob. kodowanie arytmetyczne) | ||
--> | --> | ||
Wersja z 20:03, 20 lip 2006
Zadanie 1: kompresja danych
Treść
- 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.
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.
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 obliczany jest kod Huffmana.
