Kodowanie Huffmana

Z Wikipedii

Kodowanie Huffmana (ang. Huffman coding) to jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.

Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej jak i stratnej, np. MP3 lub JPEG. Pomimo, że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych.

Spis treści 1 Kodowanie Huffmana 2 Algorytm statycznego kodowania Huffmana 2.1 Przykład 2.2 Praktyczne zastosowanie 2.3 Przykład kodowania po 2 znaki naraz 2.4 Przykładowa implementacja algorytmu budowy drzewa 3 Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi 4 Algorytm dynamicznego kodowania Huffmana

[edytuj] Kodowanie Huffmana

Dany jest alfabet źródłowy (zbiór symboli) oraz zbiór stowarzyszonych z nim prawdopodobieństw . Symbolami są najczęściej bajty, choć nie ma żadnych przeszkód żeby było nimi coś innego (np. pary znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego zestawu danych, np. poprzez wyznaczenie częstotliwości występowania znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego zestawu danych.

Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa p_i. Tzn. im częściej dane słowo występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów.

Własności kodu są następujące:

• kod Huffmana jest kodem prefiksowym; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;
• jeśli prawdopodobieństwa są różne, tzn. p_j > p_i, to długość kodu dla symbolu x_j jest niewiększa od kodu dla symbolu x_i;
• słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość;
• dwa najdłuższe symbole różnią się tylko jednym, ostatnim bitem.

Kompresja polega na zastąpieniu symboli otrzymanymi kodami.

[edytuj] Algorytm statycznego kodowania Huffmana

Algorytm Huffmana:

1. Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.
2. Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.
3. Dopóki na liście jest więcej niż jedno drzewo powtarzaj:
   1. Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.
   2. Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństw usuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu.

Drzewo które pozostanie na liście jest nazywane drzewem Huffmana – prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są symbole.

Algorytm Huffmana jest algorytmem niedeterministycznym ponieważ nie określa w jakiej kolejności wybierać drzewa z listy, jeśli mają takie samo prawdopodobieństwo. Nie jest również określone, które z usuwanych drzew ma stać się lewym bądź prawym poddrzewem. Jednak bez względu na przyjęte rozwiązanie średnia długość kodu pozostaje taka sama.

Na podstawie drzewa Huffmana tworzone są słowa kodowe; algorytm jest następujący:

1. Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie).
2. Przechodź w głąb drzewo od korzenia do każdego liścia (symbolu):
   1. Jeśli skręcasz w prawo dopisz do kodu bit o wartości 1.
   2. Jeśli skręcasz w lewo dopisz do kodu wartości 0.

Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zależy od jego położenia w drzewie.

[edytuj] Przykład

Mamy symbole A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].

• Łączymy węzły odpowiadające symbolom (A) i (B). Teraz mamy (A + B) = 0.3, (C) = 0.3, (D) = 0.4
• Łączymy węzły odpowiadające drzewku (A + B) oraz (C). Teraz mamy ((A + B) + C)=0.6 i (D) = 0.4
• Łączymy węzły odpowiadające drzewku ((A + B) + C) oraz (D). Teraz mamy tylko jeden wolny węzeł - drzewko (((A + B) + C) + D) = 1.0
• Obliczamy kody znaków:
  • A = lewo, lewo, lewo= 000
  • B = lewo, lewo, prawo = 001
  • C = lewo, prawo = 01
  • D = prawo = 1

Jak łatwo sprawdzić statystyczny znak zajmie w naszym kodzie:

p[A] * 3 + p[B] * 3 + p[C] * 2 + p[D] * 1 = 0.3 + 0.6 + 0.6 + 0.4 = 1.9 bitów. Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku.

Jednakże entropia znaku wynosi: E = -0.1*log₂(0.1) - 0.2*log₂(0.2) - 0.3 * log₂(0.3) - 0.4 * log₂(0.4) = 1.8464

Czyli "znacznie" mniej.

[edytuj] Praktyczne zastosowanie

Jednym z głównych problemów stosowania statycznego algorytmu Huffmana jest konieczność transmisji całego drzewa lub całej tablicy prawdopodobieństw (zwykle to drugie jako bardziej efektywne).

Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań pamięciowych, uzyskuje się kodując kilka kolejnych znaków na raz, nawet jeżeli nie są one skorelowane.

[edytuj] Przykład kodowania po 2 znaki naraz

• Symbole to tak jak wtedy - A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].
• Jeśli ilość symboli jest nieparzysta, robimy coś z pierwszym lub ostatnim symbolem. Nie jest to w praktyce duży problem.
• Zastępujemy symbole parami symboli - AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD o prawdopodobieństwach odpowiednio - [0.01, 0.02, 0.03, 0.04, 0.02, 0.04, 0.06, 0.08, 0.03, 0.06, 0.09, 0.12, 0.04, 0.08, 0.12, 0.16].
• Drzewko rośnie po kolei:
  • (AA + AB) = 0.03
  • (BA + AC) = 0.05
  • (CA + (AA + AB)) = 0.06
  • (BB + AD) = 0.08
  • (DA + (BA + AC)) = 0.09
  • (BC + CB) = 0.12
  • ((CA + (AA + AB)) + BD) = 0.14
  • (DB + (BB + AD)) = 0.16
  • ((DA + (BA + AC)) + CC) = 0.18
  • (CD + DC) = 0.24
  • ((BC + CB) + ((CA + (AA + AB)) + BD)) = 0.26
  • (DD + (DB + (BB + AD))) = 0.32
  • (((DA + (BA + AC)) + CC) + (CD + DC)) = 0.42
  • (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD)))) = 0.58
  • ((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 1.0

Zatem odpowiednim parom znaków odpowiadają:

• AA - 101010
• AB - 101011
• AC - 00011
• AD - 11111
• BA - 00010
• BB - 11110
• BC - 1000
• BD - 1011
• CA - 10100
• CB - 1001
• CC - 001
• CD - 010
• DA - 0000
• DB - 1110
• DC - 011
• DD - 110

Średnia ilość bitów przypadająca na parę symboli to 3.73, a więc średnia ilość bitów na symbol to 1.865. Jest to znacznie lepsza kompresja (6.75% zamiast 5% przy maksymalnej możliwej 7.68%) niż poprzednio. Używając większych ilości znaków można dowolnie przybliżyć się do kompresji maksymalnej, jednak znacznie wcześniej wyczerpie się pamięć, ponieważ wymagania pamięciowe rosną wykładniczo do liczby kompresowanych jednocześnie symboli.

[edytuj] Przykładowa implementacja algorytmu budowy drzewa

Zwracana jest tablica (2*N-1) węzłów, z czego N pierwszych odpowiada odpowiednim symbolom, a ostatni korzeniowi drzewa. Algorytm wyszukiwania węzłów o najmniejszej wartości nie jest specjalnie efektywny. W rzeczywistym kodzie raczej należałoby utworzyć posortowaną tablicę wolnych węzłów i efektywnie zakodować operację jednoczesnego usunięcia z niej 2 skrajnych elementów i wprowadzenia 1 nowego.

struct Node {
    int value;
    struct Node *left, *right, *parent;
};

struct Node* make_huffman_tree (int symbols, int *values)
{
    struct Node *nodes = malloc (sizeof (struct Node) * (symbols * 2 - 1));
    int first_free_node = symbols;
    struct Node *tmp1, *tmp2;
    int i;

    for (i=0; i<symbols; i++)
    {
        nodes[i].left = NULL;
        nodes[i].right = NULL;
        nodes[i].parent = NULL;
        nodes[i].value = values[i];
    }
    while (first_free_node != (symbols * 2 - 1))
    {
        tmp1 = NULL;
        tmp2 = NULL;
        for (i=0; i<first_free_node; i++)
        {
            if (nodes[i].parent)
                continue;
            if (!tmp1)
            {
                tmp1 = &nodes[i];
            }
            else if (!tmp2)
            {
                tmp2 = &nodes[i];
            }
            else if (tmp1->value > nodes[i].value)
            {
                tmp2 = tmp1;
                tmp1 = &nodes[i];
            }
        }
        nodes[first_free_node].left  = tmp1;
        nodes[first_free_node].right = tmp2;
        nodes[first_free_node].parent = NULL;
        nodes[first_free_node].value = tmp1->value + tmp2->value;
        tmp1->parent = &nodes[first_free_node];
        tmp2->parent = &nodes[first_free_node];
        first_free_node ++;
    }

    return nodes;
}

int main()
{
    struct Node *nodes;
    int value_table[4] = {1,2,3,4};

    nodes = make_huffman_tree (4, value_table);

    return 0;
}

[edytuj] Kodowanie Huffmana z mniejszymi wymaganiami pamięciowymi

Jeśli kodowane są pary symboli (tak jak w przykładzie powyżej), albo trójki symboli, czy ogólnie n-tki symboli, to rozmiar drzewa Huffmana rośnie znacząco - drzewo Huffmana należy zapisać razem z zakodowanym komunikatem, aby można go było zdekodować; także im większe drzewo, tym dłuższe stają się kody rzadziej występujących symboli. C. Weaver zaproponował modyfikację algorytmu Huffmana, która redukuje pamięć potrzebną do zapamiętania drzewa. Pomysł został opracowany przez Michaela Hankamera, który opublikował wyniki w artykule "A modified Huffman procedure with reduced memory reqiument" (IEEE Transactions on Communication COM-27, 1979, s. 930-932).

Modyfikacja polega na wprowadzeniu dodatkowego symbolu nazywanego ELSE, który zastępuje wszystkie rzadko występujące symbole - jeśli pojedynczy symbol opisuje N bitów, to symbol trafi do zbioru ELSE, gdy jego prawdopodobieństwo . Prawdopodobieństwo przypisane do ELSE jest równe sumie zastępowanych przez niego symboli. Przy kodowaniu symbolu należącego do klasy ELSE zapisywany jest kod dla ELSE, oraz nieskompresowany symbol; np. gdy kod ELSE to 010₂, to kodując symbol 'H' (kod ASCII 72₁₀ = 00101000₂) zapisane zostanie .

Dzięki temu drzewo staje się mniejsze, ponieważ zachowuje tylko symbole nie należące do ELSE i to w zupełności wystarczy, ponieważ symbole ze zbioru ELSE są bezpośrednio zapisane w komunikacie. Zastosowanie tej modyfikacji może nawet polepszyć nieco stopień kompresji w stosunku do niezmodyfikowanej wersji algorytmu.

[edytuj] Algorytm dynamicznego kodowania Huffmana

Dynamiczne kodowanie Huffmana to kodowanie danych o nieznanej statystyce. Statystykę buduje się w miarę napływania danych i co znak lub co daną ilość znaków poprawia się drzewo. Pełna procedura odbudowy drzewa byłaby bardzo nieefektywna, na szczęście istnieje procedura nanoszenia poprawek na gotowe drzewo, która jest całkiem efektywna w większości przypadków.