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 == | ||
# 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 [gutenberg.org]. | # 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 i wypisuje wszystkie symbole występujące w pliku wraz z ich częstotliwością, w formie: '''A 0.134 b 0.126 ...''' | # 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 ...''' <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? --> | |||
# Napisz program <tt>kompresuj</tt> | |||
<!-- Rozwiązanie zadania powinno składać się z: kodu źródłowego programu --> | <!-- Rozwiązanie zadania powinno składać się z: kodu źródłowego programu --> | ||
<!-- Prowadzący laboratorium może zrezygnować z fragmentów zadań, np. zrobić tylko kodowanie Huffmana, bez Shannona-Fano --> | |||
<!-- | |||
Różne warianty kompresji: | |||
* blokami o długości 2 | |||
* przewidywanie kolejnego symbolu na podstawie poprzedniego | |||
* od końca: przewidywanie poprzedniego na podstawie następnego | |||
Który wariant powinien być najlepszy? Porównaj, 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) | |||
--> | |||
Wersja z 13:53, 20 lip 2006
Zadanie 1: kompresja danych
- 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
