Stopień kompresji

Mam taką zagwozdkę w jaki sposób obliczyć stopień kompresji dla zadania (przypuszczam, że chodzi tutaj o medianę, ale mogę być w błędzie):

 
1.       Pobierz z Internetu dowolny plik tekstowy (może być dokument HTML) o długości pomiędzy 20 a 500 KB. Każdy student/-ka powinien/-na postarać się o innych plik niż jego/jej koledzy/-żanki  z grupy
2.       W dowolnym języku programowania napisz program, który:
a.       policzy liczebności poszczególnych znaków w tym pliku
b.      uwzględniając powyższe i całkowitą długość pliku, obliczy szacunkowe prawdopodobieństwa występowania poszczególnych symboli
c.       uwzględniając powyższe i zakładając, że mamy do czynienia ze źródłem bez pamięci, wyliczy jego entropię
d.      uwzględniając powyższe i całkowitą długość pliku, obliczy minimalny rozmiar pliku, gdyby skompresować go w oparciu o tak zdefiniowany model źródła
3.       Upewnij się, że w systemie dostępny jest program do kompresji typu Zip. Pobierz z Internetu odpowiedni program, jeżeli go brak w systemie (np. WinZip, Info-Zip, Total Commander, itp.)
4.       Dokonaj kompresji pliku testowego używając programu typu Zip (domyślne opcje działania).
a.       Porównaj jego długość z długością obliczoną w punkcie 2d
b.      Mając świadomość, że programy typu Zip zakładają inny model źródła niż przyjęty przez nas w punkcie 2, oceń na podstawie porównania 4a, który z modeli lepiej odpowiada faktycznym danym zawartym w pliku testowym

Prosiłbym o nakierowanie mojego toku myślenia.
Z góry dziękuję za pomoc.

1. Wzór na entropię: http://pl.wikipedia.org/wiki/Entropia_(teoria_informacji)
2. Skompresować do ZIPa to chyba nawet krowa na zasiłku potrafi.

przypuszczam, że chodzi tutaj o medianę, ale mogę być w błędzie

Nie wiem gdzie ty tu widzisz medianę. Masz pobrać z Internetu dowolny plik tekstowy (może być dokument HTML) o długości pomiędzy 20 a 500 KB i tyle. Żadnych median nie musisz robić.

Wibowit napisał(a):

1. Wzór na entropię: http://pl.wikipedia.org/wiki/Entropia_(teoria_informacji)
2. Skompresować do ZIPa to chyba nawet krowa na zasiłku potrafi.

przypuszczam, że chodzi tutaj o medianę, ale mogę być w błędzie

Nie wiem gdzie ty tu widzisz medianę. Masz pobrać z Internetu dowolny plik tekstowy (może być dokument HTML) o długości pomiędzy 20 a 500 KB i tyle. Żadnych median nie musisz robić.

**uwzględniając powyższe i całkowitą długość pliku, obliczy minimalny rozmiar pliku, gdyby skompresować go w oparciu o tak **
Entropię mam policzoną, co do mediany napisałem, że "przypuszczam"

c. uwzględniając powyższe i zakładając, że mamy do czynienia ze źródłem bez pamięci, wyliczy jego entropię
d. uwzględniając powyższe i całkowitą długość pliku, obliczy minimalny rozmiar pliku, gdyby skompresować go w oparciu o tak zdefiniowany model źródła

minimalny rozmiar pliku == entropia z podanego wzoru, ewentualnie zaokrąglone w górę do pełnych bajtów.

W rzeczywistości nie robi się dokładnie takiej kompresji, żeby się maksymalnie zbliżyć do entropii, typowe kodowanie arytmetyczne ma pewien narzut związany z celowymi niedokładnościami, które drastycznie przyspieszają algorytm. Ten narzut to jednak malutki ułamek procenta i dlatego nie próbuje się kombinować z teoretycznymi limitami entropii.