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 1: | Linia 1: | ||
== Zadanie 1: kompresja danych == | == 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 [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]. | ||
# Napisz program <tt>litery</tt>, 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ęstotliwością, w formie: '''A 0.134 <nowa_linia> b 0.126 ...''' Nie musisz poprawnie wypisywać znaków narodowych. Program powinien wypisać też entropię binarną <!--link--> obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki. | # Napisz program <tt>litery</tt>, 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ęstotliwością, w formie: '''A 0.134 <nowa_linia> b 0.126 ...''' Nie musisz poprawnie wypisywać znaków narodowych. Program powinien wypisać też entropię binarną <!--link--> obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki. | ||
# Napisz program <tt>huffman</tt>, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana <!--link--> 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 <tt>shannon</tt>, który oblicza kod Shannona-Fano. <!--link--> 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 <tt>huffman</tt>, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana <!--link--> dla rozkładu symboli występujących w tym pliku. Program powinien wypisać otrzymany kod w formie: '''A 001 <nowa_linia> b 0001010 ...''' <br/> Napisz program <tt>shannon</tt>, który oblicza kod Shannona-Fano. <!--link--> 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ą. | ||
<!-- Uwaga: czy na wykladzie jest konstruktywna metoda obliczania kodu S-F? --> | <!-- Uwaga: czy na wykladzie jest konstruktywna metoda obliczania kodu S-F? --> | ||
# Napisz program <tt>kompresuj</tt> | # Napisz program <tt>kompresuj</tt>, 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 <tt>kompresuj</tt> 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 <tt>kompresujbloki</tt>, 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 fragmentów zadań, np. zrobić tylko kodowanie Huffmana, bez Shannona-Fano --> | <!-- Prowadzący laboratorium może zrezygnować z fragmentów zadań, np. zrobić tylko kodowanie Huffmana, bez Shannona-Fano --> | ||
=== Rozwiązanie === | |||
Rozwiązanie zadania powinno zawierać: | |||
* wykonywalne programy, | |||
* kody źródłowe programów, | |||
* pliki wykorzystane do eksperymentów, | |||
* raport z omówieniem 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. | |||
<!-- | <!-- | ||
Wersja z 16:22, 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ęstotliwością, w formie: A 0.134 <nowa_linia> b 0.126 ... Nie musisz 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 wykorzystane do eksperymentów,
- raport z omówieniem 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.
