Kompresja danych - algorytm Huffmana

Algorytm Huffmana należy do metody kompresji statycznej. Polega ona na analizie częstości występowania elementów w zborze danych i przydzielaniu krótszych kodów tym elementom, których jest najwięcej.

Za pomocą algorytmu Huffmana zakodujemy wyraz KAWANTANNA oraz obliczymy współczynnik kompresji, czyli stosunek rozmiaru danych przed zakodowaniem do rozmiaru danych po zakodowaniu. W pierwszej kolejności tworzymy tabelę zawierającą statystykę liter.

Następnie tworzymy drzewo binarne, w którego koronie umieszcza się, jako liście, znaki według zasady: występujące najczęściej - na zewnątrz grafu, najrzadziej - w jego środku. Drzewo tworzy się, łącząc kolejno w pary elementy o najmniejszej liczbie powtórzeń. W naszym przypadku najrzadziej (po jednym razie) występują litery K, W i T. Umieszczamy je więc w środku. Literę występującą najrzadziej umieszczamy z lewej strony. Ponieważ nasze 3 litery (K, W i T) mają jednakową częstość występowania nie ma znaczenia od której zaczniemy. Wybieramy więc parę K i T. Utworzoną sumę powtórzeń liter K i T łączymy i sumujemy z kolejnym elementem o najmniejszej liczbie powtórzeń - literą W. Obliczamy sumę wystapień dla tych trzech znaków (razem 3), a następnie łączymy i sumujemy z kolejnym elementem najrzadziej występującym - literą N. Postępujemy tak długo aż wyczerpiemy wszystkie znaki występujące w rozpatrywanym ciągu znaków.

Drzewo binarne otrzymane algorytmem Huffmana

Wygenerowanie nowego kodu dla wybranego znaku następuje w wyniku przejścia drogi od korzenia drzewa do odpowiedniego liścia, przy czym każdy krok w lewą stronę powoduje dodanie do kodowanego znaku zera, krok w prawo - jedynki. Powstajacy w ten sposób unikatowy alfabet kodu musi być dołączony do kompresowanego zbioru.

W naszym przypadku z drzewa odczytujemy nowe kody znaków, idąc od korzenia drzewa do liścia zawierającego dany znak tak jak dla litery W.

Kod każdej litery jest inny i nie jest początkowym fragmentem kodu innego znaku. Nie musimy więc używać dodatkowego symbolu, oddzielającego właściwe znaki zakodowanego tekstu od siebie. Kody o tej własności nazywa się kodami prefiksowymi.

Kod wynikowy dla ciągu KAWANTANNA jest następujący:

K	A	W	A	N	T	A	N	N	A
1011	0	100	0	11	1010	0	11	11	0

Obliczenie współczynnika kompresji
Rozmiar znaków w wyrazie KAWANTANNA wynosi 10 bajtów, czyli 80 bitów (w kodzie ASCII). Kod wynikowy dla algorytmu Huffmana tego samego ciągu zajmuje 21 bitów. A zatem współczynnik kompresji wynosi 80/21 czyli około 4/1. Jednak uwzględniając pełną kompresję tą metodą będzie nieco mniejszy. Dlaczego?

Stosując statystyczną częstość występowania liter w polskich tekstach kody liter będą inne. Poniżej znajduje się tabela przedstawiająca te częstości (źródło: http://www-users.mat.uni.torun.pl/~krypto/zasoby/wlasn_stat_liter.htm). Wynik otrzymano na podstawie próby zawierającej 50 utworów literackich, tekstów naukowych, artykułów oraz tłumaczeń.
W tekstach wystąpiło :
12480217 liter (łącznie ze spacją),
201305 innych znaków (głównie symboli sterujących oraz znaków przystankowych).