25
1.3.2001 SWI072 Algoritmy komprese dat 1 Algoritmy komprese dat Adaptivní Huffmanův kód
1.3.2001 SWI072 Algoritmy komprese dat 1
Algoritmy komprese dat
Adaptivní Huffmanův kód
1.3.2001 SWI072 Algoritmy komprese dat 2
Statické adaptivní metody statický model
model
kodér dekodér
model
zdroj
1.3.2001 SWI072 Algoritmy komprese dat 3
Statické adaptivní metody adaptivní model
model
kodér
dekodér
model
zdrojaktualizace
modelu
aktualizacemodelu
1.3.2001 SWI072 Algoritmy komprese dat 4
Adaptivní Huffmanův kód - algoritmus FGK Faller(1973), Gallagher(1978), Knuth(1985). Algoritmus FGK: Kódování
Inicializuj Huffmanův stromread(znak)while znak EOF do zakóduj znak
aktualizuj strom read(znak) od .
Algoritmus FGK: Dekódování Inicializuj Huffmanův strom dekóduj(znak)while znak EOF do write(znak)
aktualizuj strom dekóduj(znak) od .
1.3.2001 SWI072 Algoritmy komprese dat 5
Charakterizace Huffmanových stromů Huffmanův strom - binární strom s ohodnocenými vrcholy. Dva vrcholy binárního stromu, které mají stejného otce,
nazveme sourozenci. Binární strom s ohodnocenými vrcholy má sourozeneckou vlastnost, pokud– každý vrchol kromě kořene má sourozence– vrcholy lze uspořádat do neklesající posloupnosti dle jejich vah
tak, že sourozenci jsou vždy na sousedních místech. Věta(Gallagher): Binární strom s ohodnocenými vrcholy je
Huffmanovým stromem právě tehdy, když má sourozeneckou vlastnost.
3
c:2 d:2
4
7 8
15
a:1 b:2
3
c:2 d:2
4
7 8
15
a:1 b:21 2 3 4
5 6
7 8
9
načti znak ´a´
3
c:2 d:2
4
7 8
15
a:2 b:21 2 3 4
5 6
7 8
9
4
c:2 d:2
4
8 8
16
a:2 b:21 2 3 4
5 6
7 8
9
načti znak ´a´
4
c:2 d:2
4
8 8
16
a:3 b:21 2 3 4
5 6
7 8
9
4
c:2 a:3
4
8 8
16
d:2 b:21 2 3 4
5 6
7 8
9
4
c:2 a:3
5
8 8
16
d:2 b:21 2 3 4
5 6
7 8
9
4
c:2 a:3
5
9 8
16
d:2 b:21 2 3 4
5 6
7 8
9
8
16
64
c:2 a:3
5
9
d:2 b:21 2 3 4
5
7 8
9
8
17
64
c:2 a:3
5
9
d:2 b:21 2 3 4
5
7 8
9
1.3.2001 SWI072 Algoritmy komprese dat 16
Problém nulových četností Jak kódovat znaky, které jsou načteny poprvé? 1. řešení: Při počáteční inicializaci jsou do Huffmanova
stromu vloženy všechny znaky vstupní abecedy, každý s četností 1.
2. řešení: Při počáteční inicializaci je do Huffmanova stromu vložen spec. znak ESC. První výskyt znaku z je kódován jako Huffmanův kód znaku ESC, následovaný znakem z. Poté je do Huffmanova stromu vložen nový list, odpovídající znaku z.
1.3.2001 SWI072 Algoritmy komprese dat 17
Problém znaků, které jsou načteny poprvé Počáteční inicializace Huffmanova stromu
esc:0
esc:0 0
esc:0 z:0
z je nově načtený znak, který se ve stromě nevyskytuje
aktualizuj strom
1.3.2001 SWI072 Algoritmy komprese dat 18
Aktualizace Huffmanova stromu z je znak načtený na vstupu if z se ve stromě nevyskytuje
then
k
esc:k z:0vesc:k
else v:= list Huffmanova stromu se znakem zfi.
1.3.2001 SWI072 Algoritmy komprese dat 19
Aktualizace Huffmanova stromu if v je sourozenec vrcholu esc then vyměň v s listem, který
má nejvyšší pořadí mezi vrcholy se stejnou váhou jako v v.váha++; v := otec(v) fi while v kořen-stromu do vyměň v s vrcholem, který má nejvyšší pořadí mezi vrcholy
se stejnou váhou jako v (vymění se celé podstromy) v.váha++; v := otec(v) od.
1.3.2001 SWI072 Algoritmy komprese dat 20
FGK:Kódování Inicializuj Huffmanův strom (T)
repeat read(znak) if první výskyt znaku then write(kód(ESC))
write(znak) else write(kód(znak)) fi
aktualizuj strom(T,znak) until znak EOF.
1.3.2001 SWI072 Algoritmy komprese dat 21
FGK:Dekódování InicializujHuffmanůvStrom(T); vrchol := kořen-stromu repeat while vrchol není list do read(bit)
if bit=0 then vrchol := vrchol.levý-syn else vrchol := vrchol.pravý-syn fi od
if vrchol.znak = ESCthen read(znak) else znak := vrchol.znak fi if znak EOF then zapiš znak na výstup
AktualizujStrom(T,znak) fi until znak = EOF .
1.3.2001 SWI072 Algoritmy komprese dat 22
Vitterův algoritmus J.S.Vitter (1987) Pouze 1 výměna při aktualizaci stromu
(FGK nejvýše l/2 výměn, kde l = délka právě zapsaného k. s.) Vitter minimalizuje i li a maxi li ( li = délka i-tého k. s. ) lA - průměrná délka kódového slova pro algoritmus A
lFGK 2 lH
lV lH +1 lFGK lH + O(1) (Milidiu, Laber, Pessoa,1999) D.E.Knuth: Dynamic Huffman Coding. J. Algorithms 6(1985),163-
180.J.S.Vitter: Design and analysis of dynamic Huffman codes. J. ACM 34(1987),825-845.
1.3.2001 SWI072 Algoritmy komprese dat 23
Další empirické výsledky E.R.Fiala,D.H.Greene (1989)
SC TM NS CC BF SF RCF SNI SCI BI
FGK 75.1 62.5 59.5 80.4 75.6 63.7 76.7 41.5 85.0 20.5
V 74.9 62.4 59.5 80.2 75.6 63.7 76.6 41.4 85.0 20.5
SC zdrojový kódTM ASCII (technické memoranda)NS ASCII (news service)CC zkompilovaný kódBF boot file
SF splajnové fontyRCF bitové mapy fontů kódované RLESNI syntetické obrázkySCI digitalizované barevné fotografie (8bitů/pixel)BI digitalizované faxové dokumenty
1.3.2001 SWI072 Algoritmy komprese dat 24
Implementační poznámky Problém přetečení
– délka souboru (kořen-stromu.váha)– délka nejdelšího kódového slova
Řešení: vynásobím váhy všech vrcholů koeficientem r < 1.
Nevýhoda: nutná reorganizace stromu
6
6 6
12
18
3 3
r = 1/2
1.3.2001 SWI072 Algoritmy komprese dat 25
Reorganizace stromu
Je třeba znovu postavit celý strom
6
6 6
12
18
3 3 3 31 1
?
3
2 3
5
8
1 1
