Huffmana, kodowanie

Dryobates

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.
Huffman.gif

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

3 komentarzy

Bardzo fajne !!!

Moim zdaniem powinienes troche tutaj dac kodu z tego przykladu i go omowic... ale OK! :)