Post on 01-May-2015
1
Algoritmi e Strutture Dati
Codici di Huffman
2
Prova del 19 novembre 2004 (4 punti)
Descrivere le caratteristiche dei codici di Huffmann.
Data la seguente sequenza di caratteri con la relativa frequenza:
a:20, g:4, e:12, f:6, k:5, l:8, d:5,
generare la codifica di Huffman ad essa relativa.
Dire qual è la percentuale di risparmio (relativamente alla codifica
della stessa sequenza data sopra) rispetto alla relativa codifica con
lunghezza fissa.
In quale caso la codifica di Huffmann permette di ottenere alte
percentuali di risparmio?
3
procedimento
Si ordinano i caratteri secondo le frequenze non decrescenti (coda con priorità)
g:4, k:5, d:5, f:6, l:8, e:12, a:20
k:5
l:8
9
e:12 a:20
k:5 g:4
9d:5 f:6
g:4
4
…
e:12 a:20
k:5 g:4
d:5 f:6
f:6d:5
9
11
k:5 g:4
9
f:6d:5
11l:8 e:12 a:20
l:8
5
…
k:5 g:4
9
f:6d:5
11l:8 e:12 a:20
17
l:8
k:5 g:4
9f:6d:5
11 e:12 a:20
23
f:6d:5
11 e:12
6
…
17
l:8
k:5 g:4
9
a:20 23
f:6d:5
11 e:12
37
17
l:8
k:5 g:4
9
a:20
23
f:6d:5
11 e:12
7
codifica
37
17
l:8
k:5 g:4
9
a:20
23
f:6d:5
11 e:12
600
10
0
0
0
1
1
1
1
10
a = 01d = 100e = 11f = 101g = 0011k = 0010l = 000
codifica
Numero di bit complessivi con Huffman2*20 + 3*5 + 2*12 + 3*6 + 4*4 + 4*5 + 3*8 = 157
Numero di bit complessivi con La codifica a lunghezza fissa: 3*60 =180
Percentuale di risparmio:12,8%
8
Esercizio
Data la seguente sequenza di caratteri con la relativa frequenza:
a:40, b:20, c:5, d:10, e:35,
f:10, g:7, h:3, i:30
generare la codifica di Huffman ad essa relativa e calcolare la percentuale di risparmio rispetto alla codifica a lunghezza fissa.
La codifica di Huffman è unica?