Kody i szyfry

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.