Przekazywanie informacji multimedialnych

Opis opracowanej przez D. A. Huffmana w 1952 roku metody kodowania jest najczęściej publikowana publikacją z teorii informacji. Przez lata metodę Huffmana optymalizowano ze względu na rosnący stopień różnych form adaptacji. Wykorzystywano ją także w szeregu standardów dotyczących kodowania faksów (a więc obrazów dwupoziomych) Grupy 3 i Grupy 4, kompresji obrazów wielopoziomych JPEG, czy też sekwencji obrazów MPEG-1 i MPEG-2, wykorzystywanych do dziś.

Algorytm

Kod Huffmana jest optymalny w kategorii kodów symboli realizując podstawową zasadę różnicowania długości słów kodowych symboli ze względu na przewidywana częstość ich występowania w kodowanym strumieniu danych. Konstrukcja słów kodowych realizowana jest za pomocą drzewa binarnego, budowanego od liści do korzenia na podstawie rozkładu wag łączonych kolejno liści.

Inicjalizacja algorytmu zakłada ustalenie zbioru wolnych węzłów zewnętrznych -- liści z przypisanymi im symbolami alfabetu oraz wagami. Początkowo, dwa węzły o najmniejszych wagach łączone są ze sobą w elementarne poddrzewo, z wierzchołkiem rodzica o wadze równej sumie wag węzłów łączonych. Następnie wyszukiwane i łączone ze sobą są kolejne wierzchołki o najniższych wagach (wśród pozostałych liści i wierzchołków poddrzew), tworząc kolejne poziomy drzewa, aż do podłączenia wszystkich wolnych węzłów. Algorytm ten zobrazowano na rys. 2.3. Dwa liście symboli o najmniejszych wagach $w_1$ i $w_2$ połączono tworząc elementarne poddrzewo $T_{1+2}$, ustalając przy tym odpowiednią wagę rodzica, reprezentowanego teraz na liście wolnych węzłów. W kolejnych krokach maleje liczba wolnych węzłów, aż do utworzenia pełnej struktury drzewa.

Rys. 2.4 Przykładowa inicjalizacja metody Huffmana: a) utworzenie elementarnego poddrzewa poprzez łączenie dwóch węzłów o najmniejszych wagach; b)zestaw wolnych węzłów podlegający analizie w kolejnym kroku algorytmu.
 

Taka procedura tworzenia drzewa zapewnia, że:

• liść symbolu o najmniejszej wadze ma najdłuższe słowo, leżąc najgłębiej w drzewie na poziomie $m_{\max}$;
• liść symbolu o drugiej w kolejności najmniejszej wadze należy do tego samego, elementarnego poddrzewa, a więc leży również na poziomie $m_{\max}$, gdyż jedynie drzewo lokalnie pełne jest efektywne w kodowaniu. 

W ten sposób symbole o wagach mniejszych znajdą się na niższych poziomach (lub najwyżej równych) w stosunku do liści symboli o większych wagach. Konsekwencją będą niekrótsze słowa kodowe, co dowodzi optymalności konstruowanego iteracyjnie według powyższej zasady drzewa kodowego. Kryterium optymalizacji określa postać wyrażenia: $\sum_{a_i \in A_S} w_i|\varsigma _i|$  , minimalizowana po wszystkich możliwych postaciach drzewa binarnego z ustalonym alfabetem symboli przypisanych liściom zewnętrznym drzewa. 

Podsumowując, algorytm kodu Huffmana przedstawia się następująco: 

Algorytm 2.1 Kod Huffmana 

1. Określ wagi wszystkich symboli alfabetu (na podstawie liczby wystąpień w wejściowym ciągu danych); symbole te wraz z wagami przypisz liściom konstruowanej struktury drzewa binarnego, stanowiącym początkowy zbiór tzw. wierzchołków wolnych (tj. wierzchołków, które mogą być łączone w elementarne poddrzewa z węzłem rodzica umieszczonym na wyższym poziomie drzewa).
2. Sortuj listę wierzchołków wolnych w porządku nierosnącym wartości ich wag.
3. Odszukaj dwa wolne wierzchołki z najmniejszymi wagami i połącz je z nowotworzonym węzłem rodzica w elementarne poddrzewo; wagę nowego wierzchołka ustal jako sumę wag dzieci.
4. Usuń z listy wierzchołków wolnych dwa węzły o najmniejszych wagach; wpisz na tę listę nowy wierzchołek rodzica.
5. Przypisz gałęziom prowadzącym od rodzica do węzłów-dzieci etykiety: 0 i 1 (np. lewa gałąź - 0, prawa - 1).
6. Powtarzaj kroki 3-5 aż do momentu, gdy na liście wierzchołków wolnych pozostanie tylko jeden węzeł - korzeń drzewa.
7. Odczytaj ze struktury drzewa słowa kodowe kolejnych liści (czyli przypisanych im symboli); słowo stanowią łączone binarne etykiety kolejnych gałęzi odczytane przy przejściu od korzenia do danego liścia (od najbardziej znaczącego bitu gałęzi korzenia do najmniej znaczącego bitu gałęzi dochodzącej do liścia).

Proces dekodowania przebiega jak w metodzie S-F, jedynie w p. 2 budowane jest drzewo według kodu Huffmana (algorytm 2.1)

Algorytm 2.2  Dekodowanie metodą Huffmana

1. Pobierz ze zbioru danych zakodowanych wartości prawdopodobieństw występowania (wagi) poszczególnych symboli alfabetu.
2. Zbuduj drzewo binarne jak w kodzie Huffmana.
3. Dekodowanie kolejnych symboli (prostsza realizacja algorytmu 1.3 dzięki wykorzystaniu struktury drzewa): 
   1. ustaw korzeń drzewa jako aktualny węzeł;
   2. pobierz bit z wejścia: jeśli wczytano 0 to przejdź do lewego syna aktualnego węzła, w przeciwnym razie (wpr) przejdź do jego prawego syna;
   3. jeśli aktualny węzeł to węzeł wewnętrzny -- kontynuuj (b), wpr odczytaj symbol przypisany liściowi, prześlij go na wyjście i powtarzaj od (a) aż do wyczerpania zbioru danych wejściowych. 

Prześledźmy działanie algorytmu Huffmana na następującym przykładzie.

Przyklad 2.1 Kodowanie metodą Huffmana
Dany jest źródłowy ciąg symboli o alfabecie: $A_S=\{A, B, C, D, E\}$, przy czym częstość występowania poszczególnych symboli przedstawia tabela 2.1.

Tab. 2.1 Symbole alfabetu przykładowego zbioru danych wraz z  częstością wystąpień.

Sposób konstrukcji binarnego drzewa kodowego za pomocą algorytmu 2.1 został przedstawiony na rys. 2.4.

Rys_. 2.4 Binarne drzewo kodowe Huffmana z przykładu 2.1. Pochyloną czcionką oznaczono wagi poszczególnych wierzchołków.

//Słowa kodowe przyporządkowane poszczególnym symbolom alfabetu  przedstawiają się następująco: $A\rightarrow \texttt{100},\ B \rightarrow\texttt{0},\ C\rightarrow \texttt{110},\ D\rightarrow \texttt{101},\ E\rightarrow\texttt{111}$. Najczęściej występującemu symbolowi $B$ przypisano jednobitowe słowo kodowe, podczas gdy pozostałym -- trójbitowe. Długości słów kodowych przypisanych poszczególnym symbolom nie oddają w pełni rozkładu ich wag, co jest spowodowane podstawowym ograniczeniem kategorii kodów symboli. Całkowita liczba bitów każdego ze słów zmusza do zaokrągleń wartości entropii własnej, będącej miarą informacji występującej przy pojawieniu się poszczególnych symboli -- zobacz tabelę 2.2. Obliczono w niej efektywność wyznaczonego drzewa  Huffmana. Średnia długość słowa kodowego wynosi $\bar L_\text{Huff}=2,226$, co jest wartością bliską entropii rozważanego źródła informacji, zakładając model bez pamięci:  $H(S_{\textrm{DMS}})=2,176$.  
Tab. 2.2 Efektywność kodu Huffmana dla danych z przykładu 2.1. Zestawiono ilość informacji związaną z wystąpieniem poszczególnych symboli alfabetu z tabeli 2.1 z uzyskaną efektywnością reprezentacji kodowej. W tabeli znajdują się wartości oszacowanych prawdopodobieństw poszczególnych symboli $P(a_i)=N(a_i)/\sum_j N(a_j)$, informacji własnej $I(a_i)$, całkowitej informacji związanej z występowaniem danego symbolu oraz długości słów kodowych i zakodowanej reprezentacji.

Sposób konstrukcji słów kodowych metodą Huffmana według algorytmu 2.1  nie zależy od kolejności wystąpienia symboli w strumieniu wejściowym, gdyż bazuje na posortowanym zbiorze symboli alfabetu. Jeśli symbole  pojawią się seriami: $6 \times A,\ 12 \times B,\ 4\times C,\ 5\times D$ i $4 \times E$, to wystarczy zakodować  liczbę wystąpień kolejnych symboli na czterech bitach, a sam symbol na trzech (zasada RLE), by uzyskać 35 bitową sekwencję kodową jednoznacznie dekodowalną, znacznie krótszą od 69-bitowej reprezentacji Huffmana. Wskazuje to na poważne ograniczenie efektywności kodów symboli budowanych na bazie źródeł bez pamięci, które nie uwzględniają zależności w występujących bezpośrednio po sobie ciągach wartości. Wadę tę częściowo eliminuje np. adaptacyjna metoda Huffmana, jak też stosowanie modeli źródeł z pamięcią i kodów strumieniowych.

Adaptacyjna wersja kodu Huffmana pozwala na bieżące kształtowanie rozkładów prawdopodobieństw występowania symboli, zależnie od lokalnych statystyk w modelu przyczynowym (z uwzględnieniem jedynie danych już zakodowanych). Drzewo  Huffmana jest wtedy stale modyfikowane, zależnie od naliczanych statystyk i aktualizowanych wag poszczególnych symboli, przy czym węzły na poszczególnych poziomach drzewa rozmieszczone są według ustalonego porządku wag (porządek niemalejący od liści do korzenia, zaś na poszczególnych poziomach -- np. od lewej do prawej).  Po zakodowaniu kolejnego symbolu waga odpowiedniego liścia jest inkrementowana, a drzewo korygowane, jeśli zaburzony został przyjęty porządek (tj. gdy węzeł o wyższej wadze znalazł się za węzłem o wadze niższej -- następuje wtedy zamiana). Taka sama procedura adaptacyjnej modyfikacji struktury drzewa Huffmana jest precyzyjnie powtarzana w dekoderze celem wiernej rekonstrukcji sekwencji źródłowej. Adaptacyjna postać algorytmu kodowania jest więc związana z większą złożonością obliczeniową. w typowych implementacjach wzrost ten wynosi 50-100%.