Huffmana, kodowanie

Kodowanie Huffmana

Kodowanie Huffmana w przeciwieństwie do algorytmu Imploding jest algorytmem kompresji statycznej. Oznacza to, że program kompresujący musi przynajmniej raz przelecieć cały kompresowany plik w celu stworzenia histogramu.

Kodowanie Huffmana jest sposobem dopasowania zapisu znaków do rodzaju kompresowanych danych. Wykorzystywane jest m. in. w kompresji JPEG jako końcowy etap przetwarzania.

Teraz już o samym algorytmie:

Algorytm wykorzystuje drzewa binarne i kodowanie znaków zmienną długością kodu.
1. Utwórz histogram (częstotliwość występowania znaków w pliku).
2. Utwórz wierzchołki drzewa o odpowiednich wagach (waga wierzchołka jest równa liczbie znaków).
3. Połącz dwa najlżejsze wierzchołki w jeden dodając do kodu pierwszego cyfrę 0 a drugiemu 1.
4. Powtarzać etap 3, aż osiągniemy koniec drzewa.

Znak	Q	W	E	R	T	Y
Kod	011	010	001	000	10	11
Liczba znaków	2	3	3	4	5	4

5. W ten sposób otrzymujemy listę znaków i ich kodów najlepiej dopasowanych do naszych danych.
Najczęściej występującym znakom przyporządkowywany jest najkrótszy kod.
6. Następnie zapisujemy kody znaków do strumienia bitów.

Odczyt jest znacznie prostszy. Odczytujemy zapisaną tablicę z kodami znaków, a następnie odczytujemy bit po bicie, sprawdzając, czy kod jaki nam powstaje jest na liście i podstawiając odpowiedni znak.

Przykładowy kod źródłowy Huffman.zip