Teoria informacji/TI Ćwiczenia 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
mNie podano opisu zmian |
||
| Linia 4: | Linia 4: | ||
# 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 | # 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 musi 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 ...''' <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ą. | # 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? --> | ||
| Linia 25: | Linia 25: | ||
* kody źródłowe programów, | * kody źródłowe programów, | ||
* pliki wykorzystane do eksperymentów, | * pliki wykorzystane do eksperymentów, | ||
* raport z | * 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. | Pliki źródłowe i raport należy ''podpisać'' imieniem i nazwiskiem autora. | ||
Wersja z 16:33, 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 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 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.
