Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Kodowanie Huffmana
Dawid Duda
4 marca 2004
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Wstęp
Podstawowe oznaczenia i definicje
Statyczne kody Huffmana
Wymagania wobec kodu
Podstawowa idea
Podsumowanie
Dynamiczne kody Huffmana
Wstęp
Algorytm FGK (Faller, Gallager i Knuth)
Algorytm Vittera
Praktyka
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Podstawowe oznaczenia i definicje
Dynamiczne kody Huffmana
Praktyka
Podstawowe oznaczenia i definicje:

alfabet wejściowy: A = {a1, a2, . . . , am}

informacja własna litery:
1
i(A) = log = - log P(A) (1)
P(A)

entropia (średnia informacja własna):

H = P(Ai)i(Ai) = - P(Ai) log P(Ai) (2)

Tw. Shannona: średnia ilość bitów przypadająca na jeden
zakodowany symbol nie jest mniejsza od entropii z
ródła

kod prefiksowy: kod, w którym żadne słowo kodowe nie jest
prefiksem innego słowa kodowego
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Co chcemy uzyskać:

każdemu symbolowi z alfabetu chcemy przypisać
jednoznacznie słowo kodowe

symbolom rzadko występującym chcemy przypisać dłuższe
słowa kodowe, a częściej występującym krótsze

chcemy móc jednoznacznie dekodować zakodowane dane

ale takich kodów jest wiele, który wybrać?

no i jak wybrać, aby taki kod móc szybko zbudować?
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Cel: optymalny kod spełniający wymienione wymagania.
Kluczowe obserwacje:

dla każdego jednoznacznie dekodowalnego kodu istnieje nie
gorszy (w sensie średniej ilości bitów na symbol) kod
prefiksowy

w kodzie optymalnym częściej występującym symbolom będą
odpowiadały krótsze słowa kodowe a rzadziej występującym
dłuższe

w kodzie optymalnym dwa symbole występujące najrzadziej
będą miały słowa kodowe o tej samej długości
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
A P(A) c(A) A P(A) c(A) A P(A) c(A)
a2 0.4 c(a2) a2 0.4 c(a2) a2 0.4 c(a2)

a1 0.2 c(a1) a1 0.2 c(a1) a3 0.4 Ä…2
a3 0.2 c(a3) a3 0.2 c(a3) a1 0.2 c(a1)

a4 0.1 c(a4) a4 0.2 Ä…1
a5 0.1 c(a5)

c(a3) = Ä…2
·0 c(a3) = Ä…3
·0

c(a4) = Ä…1
·0 c(a4) = Ä…2
·1 c(a1) = Ä…3
·1
c(a5) = Ä…1
·1 Ä…1 Ä…2
= ·1 Ä…2 Ä…3
= ·0
A P(A) c(A)

a3 0.6 Ä…3
c(a2) = 1
a2 0.4 c(a2)
c(a1) = 01
c(a3) = 000
c(a4) = 0010

c(a3 ) =0
c(a5) = 0011
c(a2) =1
Ä…3
=0
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Algorytm konstrukcji drzewa Huffmana:
1. umieść m liści na liście L
2. dopóki lista L zawiera przynajmniej dwa elementy wykonuj
2.1 usuń z listy L dwa elementy x oraz y o najmniejszej wadze
2.2 stwórz nowy wierzchołek p, który będzie rodzicem x i y
2.3 ustaw wagę wierzchołka p na sumę wag x i y
2.4 umieść wierzchołek p na liście L
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Algorytm Huffmana generuje optymalny kod, ale jaka jest jego
średnia długość l? Twierdzenie:
H(S) d" l d" H(S) + 1 (3)
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Istnieje możliwość dokładniejszego oszacowania. Niech
Pmax = max {P(ai)}m
i=1
wówczas

Pmax < 0.5 =Ò! l d" H(S) + Pmax

Pmax e" 0.5 =Ò! l d" H(S) + Pmax + 0.086
Dawid Duda Kodowanie Huffmana
Wstęp
Wymagania wobec kodu
Statyczne kody Huffmana
Podstawowa idea
Dynamiczne kody Huffmana
Podsumowanie
Praktyka
Zalety:

kod Huffmana minimalizuje sumę ważoną długości kodów, tj.
jest optymalnym kodem prefiksowym

procedura budowy drzewa Huffmana jest szybka i prosta
w implementacji

zarówno kodowanie jak i dekodowanie jest proste i efektywne
Wady:

do budowy drzewa konieczne sÄ… statystyki kodowanej
wiadomości

do przekazywanej/zapisywanej wiadomości trzeba dołączyć
opis drzewa
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Cel: stworzenie jednoprzebiegowego algorytmu kodujÄ…cego
Metoda: utrzymywanie drzewa Huffmana obliczonego zgodnie
z częstościami wystąpień symboli w dotychczas przetworzonym
fragmencie
Co zyskamy:

tylko jeden przebieg

nie trzeba przesyłać drzewa
Problem: jak szybko uaktualniać drzewo Huffmana?
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Wierzchołkom w drzewie przypisujemy wagę, która dla liści jest
równa ilości wystąpień kodowanego symbolu w dotychczasowym
tekście, a dla wierzchołków wewnętrznych sumie wag dzieci. Niech
Mt = ai1ai2 . . . aik będzie dotychczas przetworzonym fragmentem.
Następna litera aik+1 będzie zakodowana oraz odkodowana przy
użyciu drzewa Huffmana dla Mt.
Główna trudność: jak szybko zmodyfikować drzewo dla Mt aby
otrzymać drzewo dla Mt+1? Proste zwiększenie o 1 wagi
wierzchołka i jego rodziców nie zawsze da drzewo Huffmana.
Rozwiązanie: wykorzystać własność sąsiedztwa
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Do wyprowadzenia algorytmu wykorzystamy pewnÄ… charakteryzacjÄ™
drzew Huffmana:
Własność sąsiedztwa
Drzewo binarne o p liściach oraz nieujemnych wagach
wierzchołków wi jest drzewem Huffmana wtedy i tylko wtedy gdy:
1. waga każdego wierzchołka jest sumą wag jego dzieci
2. istnieje niemalejąca numeracja wierzchołków zgodna
z niemalejącym uporządkowaniem według wagi taka, że dla
1 d" j d" p - 1 wierzchołki 2j - 1 i 2j są sąsiadami i ich
wspólny rodzic ma wyższy numer
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Rozwiązanie: aktualizacje drzewa wykonamy w dwóch fazach:
1. przekształcenie drzewa do takiej postaci, w której proste
zwiększenie wagi odpowiednich wierzchołków nie zaburzy
własności sąsiedztwa
2. zwiększenie wagi wierzchołka odpowiadającego
przetwarzanemu symbolowi i jego rodzicom
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Pytanie: co zrobić z drzewem, aby można było po prostu
zwiększyć wagi wierzchołków?
Odpowiedz
: zaczynając od wierzchołka, który odpowiada
kodowanemu symbolowi, zamieniać aktualny wierzchołek
z wierzchołkiem o najwyższym numerze (w sensie numeracji
z własności sąsiedztwa) spośród wierzchołków o tej samej wadze
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
procedure update;
q := wierzchołek odpowiadający otrzymanej literze;
if (q = wierzchołek 0) and (k < m - 1) then
dodaj q dwoje dzieci (numeracja: lewe, prawe, rodzic)
q := prawe dziecko
if q jest sąsiadem wierzchołka 0 then
zamień q z liściem o tej samej wadze i najw. numerze
zwiększ wagę q o 1
q := rodzic q
while q nie jest korzeniem
zamień q z wierz. o tej samej wadze i najw. num.
zwiększ wagę q o 1
q := rodzic q
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Obserwacje:

zamiany wierzchołków, wykonywane przez algorytm, nie
powodują, że drzewo przestaje być drzewem Huffmana dla
Mt (co wynika z własności sąsiedztwa)

po zwiększeniu odpowiednich wag (w drzewie otrzymanym
przez wykonanie zamian) dostaniemy drzewo Huffmana dla
Mt+1 (co ponownie wynika z własności sąsiedztwa)
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Ile nas to kosztuje? O ile więcej bitów wygeneruje algorytm FGK
w porównaniu z klasycznymi kodami Huffmana?
Odpowiedz
: Jeżeli S jest ilością bitów wygenerowanych przez
oryginalny algorytm Huffmana, S ilością bitów wygenerowanych
przez algorytm FGK, a m rozmiarem alfabetu, to zachodzi:
S d" 2S + m (4)
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Pytanie: Czy można lepiej?
Odpowiedz
: Tak, używając algorytmu Vittera można mieć:
S < S + m (5)
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Podstawowa idea:

ograniczyć ilość zamian, w których wierzchołek q porusza się
w górę drzewa, do co najwyżej jednego przy każdym
wywołaniuupdate

konstruować drzewo w ten sposób, aby minimalizowało nie

tylko sumę ważoną długości ścieżek w drzewie wjLj, ale
j

również sumę nieważoną długości ścieżek Lj oraz długość
j
najdłuższej ścieżki maxj {Lj} - intuicyjnie powinno to
ograniczyć długość słowa kodowego dla następnej litery
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Klasyfikacja zamian:

ę! wierzchołek q przesuwa się do góry o jeden poziom

wierzchołek q zamieniamy z wierzchołkiem z tego samego
poziomu

“! wierzchoÅ‚ek q zamieniamy z wierzchoÅ‚kiem na niższym
poziomie

ę!ę! wierzchołek q zamieniamy z wierzchołkiem położonym
o dwa poziomy wyżej
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Niejawna numeracja
Pomysł: numerować wierzchołki drzewa w sposób odpowiadający
reprezentacji wizualnej:

wierzchołki numerujemy w sposób zgodny z poziomami
drzewa: wierzchołki na tym samym poziomie mają numery
niższe niż te na następnym, wyższym poziomie

wierzchołki na tym samym poziomie numerujemy rosnąco
od lewej do prawej
Gdy używamy niejawnej numeracji, nie bÄ™dzie zamian typu “!.
Oprócz tego, jeżeli wierzchołek przesuwa się do góry w zamianie
typu ę!, to ten, który przesuwa się w dół, jest liściem.
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Niezmiennik algorytmu
Kluczem do polepszenia algorytmu jest uniknięcie zamian typu ę!
poza pierwszą iteracją pętliwhile. Aby to zrobić będziemy
utrzymywać następujący niezmiennik:

dla każdej wagi w, wszystkie liście o wadze w poprzedzają
w niejawnej numeracji wszystkie wierzchołki wewnętrzne
o wadze w
Można pokazać, że drzewo Huffmana, które spełnia ten

niezmiennik, minimalizuje Lj oraz maxj {Lj}.
j
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Kilka definicji:
- klasa równoważności relacji na wierzchołkach drzewa:
blok
wierzchołki v i x są w relacji, jeśli mają tą samą wagę oraz
obydwa są wierzchołkami lub obydwa są liśćmi (w algorytmie
FGK nie zwracaliśmy uwagi na liście/wierzch. wewn.)

lider bloku - wierzchołek o najwyższym numerze należący
do bloku
Bloki są połączone w listę w kolejności rosnącej wagi, blok liści
zawsze poprzedza blok wierzchołków wewnętrznych o tej samej
wadze.
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
procedure update;
leafToIncrement := 0;
q := wierzchołek odpowiadający otrzymanej literze;
if (q = wierzchołek 0) and (k < m - 1) then
dodaj q dwoje dzieci, prawe odpowiadajÄ…ce literze
q := wierzchołek, który właśnie został tatusiem
leafToIncrement := prawe dziecko q
else
zamień q z liderem jego bloku
if q jest sąsiadem wierzchołka 0 then
leafToIncrement := q;
q := rodzic q
while q nie jest korzeniem
slideAndIncrement(q);
if leafToIncrement = 0 then

slideAndIncrement(leafToIncrement);
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
procedure slideAndIncrement(p);
wt := waga wierzchołka p;
b := następny blok na liście po bloku wierzchołka p;
if p jest liściem and
b jest blokiem wierzch. wewn. o wadze wt
or p jest wierzch. wewn. and
b jest blokiem liści o wadze wt+1
then
zjedz
wierzch. p w drzewie w kierunku wierzch. z b
p.weight := wt + 1;
if p jest liściem then
p := nowy rodzic p
else
p := dawny rodzic p
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Dawid Duda Kodowanie Huffmana
Wstęp
Wstęp
Statyczne kody Huffmana
Algorytm FGK (Faller, Gallager i Knuth)
Dynamiczne kody Huffmana
Algorytm Vittera
Praktyka
Podsumowanie

długość danych zakodowanych algorytmem Vittera może się
różnić od długości danych zakodowanych statycznym
algorytmem Huffmana co najwyżej o długość alfabetu

algorytm jest dosyć skomplikowany, ale Vitter opublikował
jego wzorcowÄ… implementacjÄ™

algorytm wymaga specyficznych struktur danych, opisanych
dokładnie w pracach Vittera
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Wyniki testów
Typ Rozmiar Stat. kody FGK Vitter
pliku poczÄ…tkowy Huffmana
Postscript 506197 334785 334907 334891
BMP 481078 448533 448821 448739
Poczta 1657081 1112169 1112278 1112264
y
ródła w C 1331200 778081 778207 778182
WAV 1000000 763453 763933 763717
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Współczynnik kompresji
Typ Stat. kody FGK Vitter
pliku Huffmana
Postscript 0,6614 0,6616 0,6616
BMP 0,9323 0,9329 0,9328
Poczta 0,6712 0,6712 0,6712
y
ródła w C 0,5845 0,5846 0,5846
WAV 0,7635 0,7639 0,7637
Åšrednio 0,7226 0,7229 0,7228
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Dawid Duda Kodowanie Huffmana
Wstęp
Statyczne kody Huffmana
Dynamiczne kody Huffmana
Praktyka
Gdzie szukać dalszych informacji:

Khalid Sayood,  Kompresja danych - wprowadzenie ,
wydawnictwo Read Me, kwiecień 2002.

Jeffrey S. Vitter,  Design and Analysis of Dynamic Huffman
Codes , JACM Vol. 34, paz
dziernik 1987.

Jeffrey S. Vitter,  Dynamic Huffman Coding , ACM
Transactions on Mathematical Software Vol. 15, czerwiec
1989.
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Algorytm Huffmana generuje optymalny kod, ale jaka jest jego
średnia długość l? Twierdzenie:
H(S) d" l d" H(S) + 1 (6)
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Lemat (Kraft, McMillan):

(McMillan) Niech C będzie jednoznacznie dekodowalnym
kodem. Niech A = {a1, a2, . . . , am} będzie alfabetem
wejściowym oraz niech li = |C(ai)|. Wówczas:
m

2-li d" 1 (7)
i=1

(Kraft) Dla dowolnego ciągu dodatnich liczb całkowitych
{li}m spełniającego (7) istnieje jednoznacznie dekodowalny
i=1
kod o długościach {li}m
i=1
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Wpierw pokażemy, że H(S) d" l. Prawdopodobieństwo wystąpienia
litery ai oznaczmy przez P(ai). Wtedy mamy:
m

l = P(ai)li (8)
i=1
m m

H(S) - l = - P(ai) log P(ai) - P(ai)li
i=1 i=1

m

1
= P(ai) log - li
P(ai)
i=1

m


1
= P(ai) log - log 2li
P(ai)
i=1

m

2-li
= P(ai) log
P(ai)
i=1
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Nierówność Jensena: dla każdej wklęsłej funkcji ()") f (x)
zachodzi:
E [f (X )] d" f (E[X ]) (9)
Ponieważ funkcja log jest wklęsła, wobec tego:


m m

2-li
H(S) - l = P(ai) log d" log 2-li (10)
P(ai)
i=1 i=1
Ponieważ kod jest optymalny, to z lematu Krafta-McMillana (7)
m
mamy że 2-li d" 1, a więc
i=1
H(S) - l d" 0
co kończy pierwszą część dowodu.
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Górna granica - wiemy, że kod jest optymalny, więc wystarczy
pokazać istnienie kodu takiego, że l d" H(S) + 1. Zdefiniujmy:

1
li = log (11)
P(ai)
Ponieważ "x. " " [0, 1). x = x + to zgodnie z (11) mamy:
1 1
log d" li d" log + 1 (12)
P(ai) P(ai)
Dawid Duda Kodowanie Huffmana
Długość kodów Huffmana
Zauważmy, że z lewej nierówności z (12) mamy:
2-li d" P(ai)
wobec czego, sumujÄ…c obustronnie, otrzymujemy:
m m

2-li d" P(ai) = 1
i=1 i=1
skąd z kolei, przez drugą część lematu Krafta-McMillana, istnieje
jednoznacznie dekodowalny kod o długościach {li}.
Długość tego kodu możemy oszacować następująco:

m m

1
l = P(ai)li < P(ai) log + 1 = H(S) + 1 (13)
P(ai)
i=1 i=1
co kończy dowód.
Dawid Duda Kodowanie Huffmana