Algoritmy komprese dat
Adaptivní Huffmanův kód
Robert G. Gallager
Massachusetts Institute of Technology
15.10.2014
NSWI072 - 4
Donald Ervin Knuth
Stanford University
Statické × adaptivní metody
(Statistická) komprese dat
• modelování
• kódování
Statický model
zdroj
model
model
kodér
dekodér
2
Statické × adaptivní metody
Adaptivní model
model
zdroj
kodér
aktualizace
modelu
model
dekodér
3
aktualizace
modelu
Adaptivní Huffmanův kód
Algoritmus AdaptivníHuffman: Kódování
Inicializuj Huffmanův strom
while not EOF do read(znak)
"
"
zakóduj znak
"
"
"
aktualizuj strom
Algoritmus AdaptivníHuffman: Dekódování
Inicializuj Huffmanův strom
while not EOF do dekóduj(znak)
!
!
!
write(znak)
"
"
"
aktualizuj strom
4
Adaptivní Huffmanův kód - hrubá síla
Rekonstrukce Huffmanova stromu
• po každé změně četností
• po načtení dalších k znaků
• po změně uspořádání znaků podle četností
5
Charakterizace Huffmanových stromů
Huffmanův strom - binární strom s nezáporně
ohodnocenými vrcholy.
Dva vrcholy binárního stromu, které mají stejného
rodiče, nazveme sourozenci.
Binární strom s nezáporně ohodnocenými vrcholy
má sourozeneckou vlastnost, pokud
• ∀ rodiče: ohodnocení(rodiče) = Σ ohodnocení(synů)
• každý vrchol kromě kořene má sourozence
• vrcholy lze uspořádat do nerostoucí posloupnosti dle
jejich ohodnocení tak, že sourozenci jsou vždy na
sousedních místech
6
Charakterizace Huffmanových stromů
☝Věta (Faller 1973, Gallagher 1978)
Binární strom s ohodnocenými vrcholy je
Huffmanovým stromem právě tehdy, když má
sourozeneckou vlastnost.
☞ Algoritmus FGK
• Faller(1973), Gallagher(1978), Knuth(1985)
7
15
7
e:8
4
3
a:1
b:2
c:2
d:2
8
1
15
3
2
7
3
e:8
4 4
5
a:1
b:2
c:2
d:2
9
8
7
6
9
1
15
3
2
7
3
e:8
4 4
5
a:1
b:2
c:2
d:2
9
8
7
6
načti znak ´a´
10
1
15
3
2
7
3
e:8
4 4
5
a:2
b:2
c:2
d:2
9
8
7
6
11
1
16
3
2
8
4
e:8
4 4
5
a:2
b:2
c:2
d:2
9
8
7
6
načti znak ´a´
12
1
16
3
2
8
4
e:8
4 4
5
a:3
b:2
c:2
d:2
9
8
7
6
13
1
16
3
2
8
4
e:8
4 4
5
d:2
b:2
c:2
a:3
9
8
7
6
14
1
16
3
2
8
4
e:8
5 4
5
d:2
b:2
c:2
a:3
9
8
7
6
15
1
16
3
2
9
4
e:8
5 4
5
d:2
b:2
c:2
a:3
9
8
7
6
16
1
16
e:8 3
9
4 5
d:2
b:2
9
8
17
2
5
c:2
7
4
a:3
6
1
17
e:8 3
9
4 5
d:2
b:2
9
8
18
2
5
c:2
7
4
a:3
6
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 speciální 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
19
Problém znaků, které jsou načteny poprvé
Počáteční inicializace Huffmanova stromu
esc:0
z je nově načtený znak, který se ve stromě nevyskytuje
0
esc:0
esc:0
aktualizuj strom
20
z:0
Aktualizace Huffmanova stromu
z je znak načtený na vstupu
if z se ve stromě nevyskytuje
then
esc:0
i
esc:0
i+2
0
i
v
z:0
i+1
else v:= list Huffmanova stromu
se znakem z
21
Aktualizace Huffmanova stromu
if v je sourozenec vrcholu esc
then vyměň v s listem, který má nejnižší pořadí mezi
vrcholy se stejnou váhou jako v
v.váha++; v := otec(v)"
while v ≠ kořen-stromu
do vyměň v s vrcholem, který má nejnižší pořadí mezi
vrcholy se stejnou váhou jako v
(vymění se celé podstromy)
v.váha++; v := otec(v)
je-li z poslední znak,
lze ho uložit přímo do vrcholu esc
22
FGK:Kódování
InicializujHuffmanůvStrom(T)
repeat read(znak)
"
if první výskyt znaku
then write(kód(ESC))
write(znak)
"
else write(kód(znak))
aktualizuj strom(T,znak)
until EOF.
23
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
if vrchol.znak=ESC then read(znak)
else znak := vrchol.znak
zapiš znak na výstup
AktualizujStrom(T,znak)
until EOF.
24
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
lV ≤ lH +1
lFGK ≤ lH + O(1)
&
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.
&
R.L.Milidiú, E.S.Laber,A.A.Pessoa: Bounding the compression loss of the FGK
algorithm. J. Algorithms 32(1999),195-211.
25
Empirické výsledky
E.R.Fiala, D.H.Greene
SC
TM
NS
CC
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
59.5
80.2 75.6 63.7
41.4
85.0
20.5
74.9 62.4
BF
SC zdrojový kód
TM ASCII (technická memoranda)
NS ASCII (news service)
CC zkompilovaný kód
BF boot file
SF
76.6
SF splajnové fonty
RCF bitové mapy fontů kódované RLE
SNI syntetické obrázky
SCI digitalizované barevné fotografie
(8bitů/pixel)
BI digitalizované faxové dokumenty
26
Implementační poznámky
Problém přetečení
• délka nejdelšího kódového slova
• délka souboru (kořen-stromu.váha)
Řešení: vynásobím váhy všech vrcholů
koeficientem r < 1
Nevýhoda: nutná reorganizace stromu
18
12
6
3
3
r = 1/2
6
6
27
Reorganizace stromu
18
6
3
?
12
3
6
6
1
1
3
3
8
5
3
2
Je třeba znovu postavit celý strom!
1
28
3
1
„Stárnutí“ statistik
každá četnost /= 2 ⇒ starší četnosti mají nižší váhu nežli nové
⇒ lepší kompresní poměr
každá četnost *= (1- x) v každém kroku, x → 0
četnost_aktuálního_znaku += (1+ x)t v čase t
Příklad: chceme (1+x)d = 2
• x ≈ ln(1+x) pro x → 0
• ⇒ x ≈ (ln 2)/d pro x → 0
Volba d: stabilní rozložení psti × časté fluktuace
• d = 1000, 1+x = 1.00069
• celočíselná aritmetika ⇒ škálování
• 1.krok: inkrement 10000
• 2.krok: inkrement ⎡10000(1+x)⎤ = 10007
• 3.krok: inkrement ⎡10000(1+x)2⎤ = 10014
• po dosažení horní meze všechny četnosti /= 2
29
Download

FGK (Dvorak)