Podręcznik

6. Kompresja informacji

6.2. Kod Huffmana

Kod Huffmana to kod ale jednocześnie najbardziej znana, powszechnie stosowana, efektywna metoda kompresji danych. W zależności od typu kompresowanego pliku, osiąga się oszczędności w objętości danych od 20% do nawet 90%. Kod Huffmana to kod prefiksowy spełniający następujące warunki:

obiektom kodowanym występującym częściej (mającym większe prawdopodobieństwo wystąpienia) odpowiadają krótsze słowa niż obiektom występującym rzadziej (mającym mniejsze prawdopodobieństwo wystąpienia);
dwa najrzadziej występujące (najmniej prawdopodobne) mają słowa tej samej długości.

Będziemy dalej zakładać, że obiektami kodowanymi są litery (symbole) z pewnego alfabetu V₁ {a₁, a₂,..., a_n} i znamy prawdopodobieństwo pojawienia się każdej litery tzn. podane są prawdopodobieństwa binarnego {0,1}. P(a_i)  p_i dla i  1, 2,..., n . Ponadto używamy jako alfabetu V₂ zbioru

Algorytm kodowania Huffmana czyli algorytm Huffmana jest następujący:

dla każdej litery tworzymy drzewo złożone tylko z korzenia i ustawiamy te drzewa w malejącym porządku prawdopodobieństwa użycia danej litery

while (istnieją przynajmniej 2 drzewa)
Z drzew t₁i t₂ o najmniejszych prawdopodobieństwach p₁i p₂tworzymy nowe drzewo zawierające w korzeniu prawdopodobieństwo p₁ p₂ i mające t₁i t₂ jako lewe i prawe poddrzewo. Przypisujemy 0 każdej lewej krawędzi i 1 każdej prawej krawędzi;
Tworzymy słowo kodowe dla każdej litery przechodząc drzewo od korzenia do liścia zawierającego prawdopodobieństwo stowarzyszone z tą literą i łącząc napotkane 0 i 1;

Przykład: Załóżmy, że chcemy zbudować kod Huffmana dla 4 literowego alfabetu V₁ {a₁, a₂, a₃, a₄} przy czym P(a₁)  0,1 , P(a₂)  0, 2 , P(a₃)  0, 3 , P(a₄)  0, 4 .

Postępując zgodnie z podanym algorytmem Huffmana tworzymy drzewo pokazane na Rys. 1. Odczytany z tego drzewa kod Huffmana jest następujący:

a₁ 000 , a₂ 001

a₃ 01, a₄ 1.

Rys. 1. Tworzenie kodu Huffmana.

Metoda kompresji plików tekstowych oparta na wykorzystaniu kodu Huffmana jest bardzo prosta. Kodujemy kolejne litery wchodzące w skład tekstu za pomocą kodu Huffmana i tak uzyskane ciągi konkatenujemy. Warto przy tym przypomnieć, że kod Huffmana jest kodem prefiksowym, a więc jednoznacznie dekodowalnym.