Algorytm Huffmana

Zadanie AL10.1 Jaki jest optymalny kod Huffmana dla następujących częstości wystąpień znaków a:3, d:5, e:6, o:8, p:8, r:9, u:12, t:12, v:13, z:20? Zakoduj słowo arvopart.

Zadanie AL10.2 Udowodnij indukcyjnie (po liczbie liści), że koszt całego drzewa kodu Huffmana można obliczyć jako sumę, po wszystkich węzłach wewnętrznych, sum częstości wystąpień ich potomków.

Zadanie AL10.5 (5 pkt.) Napisz program, który: pobiera na wejściu plik, zlicza częstości wystąpień znaków (można przyjąć, że każdy bajt pliku jest znakiem), tworzy kod Huffmana, drukuje tabelę kodów w postaci trójek: znak, ilość wystąpień, kod Huffmana, a na koniec porównuje długości tekstów oryginalnego i zakodowanego uzyskanym kodem Huffmana. (Tekstu nie trzeba kodować, tylko policzyć długość jaka byłyby po zakodowaniu).

Uwaga tak jak napisano powyżej, można przyjąć, że każdy bajt czytanego pliku jest znakiem, czyli tekst w kodzie ASCII, ale też dopuszczamy pliki binarne do kodowania. Na wejściu więc mamy znaki o kodach z zakresu 0-255, ale te które nie wytąpią w kodowanym tekście po prostu pomijamy w tworzaniu kodu Huffmana.

Zadanie AL10.6 (5+1* pkt). Napisz program, który pobiera na wejściu (z pliku) ciąg cyfr ze zbioru {0, 1, 2, 3, 4, 5, 6, 7}, zlicza częstości wystąpień cyfr, a następnie wyznacza, wypisuje i porównuje kodowania Huffmana uzyskane przez kodowanie po jednym znaku oraz po dwóch znakach. Wynik porównania to długość zakodowanego tekstu (w bitach) w pierwszym i drugim przypadku (tekstu nie trzeba kodować, tylko policzyć długości jakie byłyby po zakodowaniu).