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?