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