Kompresja metodą Huffmana
Kompresja danych polega na takim kodowaniu informacji, aby w wyniku otrzymać jak najkrótszy ciąg
bitów. Algorytm Huffmana realizuje zadanie kompresji tworząc bezprzystankowe kody binarne, gdzie
symbole występujące najczęściej w kodowanej informacji otrzymują kody najkrótsze, a symbole
występujące rzadziej otrzymują kody dłu\
sze.
Dla zobrazowania zasady działania algorytmu Huffmana załó\
my, i\
mamy skompresować tekst
zawierający 8 symboli A, B, C, D, E, F, G i H:
EAEACDGDGEGGFGDFGHGAGGBEEEDGHH
Jeśli zastosujemy normalne kodowanie binarne, to ka\
demu z 8 symboli musimy przypisać kod 3 bitowy,
np:
A - 000, B - 001, C - 010, D - 011, E - 100, F - 101, G - 110, H - 111
Wtedy powy\
szy napis mo\
na przedstawić w postaci strumienia bitów:
100000100000010011110011110100110110101110011101110111110000110110001100100100011110111
111
Jak łatwo policzyć, strumień ten zawiera 30 znaków x 3 bity na znak = 90 bitów.
Policzmy teraz ilość wystąpień ka\
dego znaku w tekście. Otrzymamy następujące wartości:
Znak A B C D E F G H
Częstość 3 1 1 4 6 2 10 3
Ze znaku i jego częstości tworzymy węzeł-liść drzewa binarnego. Węzły nie są jeszcze połączone w
drzewo. Umieszczamy je na liście dwukierunkowej:
Z listy wybieramy dwa węzły o najmniejszych częstościach występowania:
Wyjęte z listy węzły łączymy w drzewo binarne. Korzeń staje się nowym elementem, którego częstość jest
równa sumie częstości obu liści. Korzeń wstawiamy z powrotem na listę:
Ostatnie operacje (wybranie z listy dwóch węzłów o najmniejszej częstości, utworzenie z nich drzewa i
wstawienie korzenia na listę) powtarzamy dotąd, a\
lista będzie zawierała tylko jeden element - binarne
drzewo kodu Huffmana:
- 1 -
Kompresja metodą Huffmana
- 2 -
Kompresja metodą Huffmana
Zgodnie z drzewem wynikowym otrzymaliśmy następujące kody dla poszczególnych znaków:
A - 100, B - 00000, C - 00001, D - 001, E - 11, F - 0001, G - 01, H - 101
Tekst zakodowany za pomocą tych kodów ma postać:
11100111000000100101001011101010001010010001011010110001010000011111100101101101
a oryginalny był następujący:
100000100000010011110011110100110110101110011101110111110000110110001100100100011110111
111
Nawet wzrokowo widzimy, i\
kod Huffmana jest krótszy. Dokonaliśmy zatem kompresji danych. Kod
Huffmana daje efektywną kompresję tylko wtedy, gdy częstości występowania symboli ró\
nią się od siebie.
W przeciwnym wypadku powstaje kod o stałej liczbie bitów na symbol.
- 3 -