Algoritmi e strutture dati

Codici di Huffman

Memorizzazione dei dati

• Quando un file viene memorizzato, esso va memorizzato in qualche formato binario

• Modo più semplice: memorizzare il codice ASCII per ogni carattere• Ogni codice ASCII è lungo 1 byte (8 bits)• Se il nostro file contiene n caratteru, la dimensione

del file memorizzato sarà n bytes, o 8n bits

Compressione dei dati

• Spesso è importante trovare un modo più efficiente per rappresentare i dati – cioè così da impiegare meno bits per la reppresentazione• si risparmia spazio disco• si risparmia tempo per i trasferimenti (ad esempio

in rete)• La conversione però può impiegare più tempo

• In genere è utilizzate solo per la memorizzazione – non quando si lavora effettivamente sul file

• I dettagli della compressione possono essere nascosti all’utente – non è necessario che sappia se sta leggendo un file compresso o meno

Rappresentazione della compressione

Un semplice schema di compressione è costituito tramite l’applicazione di funzioni.• Ogni carattere ha un valore ASCII tra 0 e 255• Ogni carattere necessita di essere rappresentato

come un numero (binario) nel file compresso• Funzione di compressione: f(c)=x

• Il carattere rappresentato dal codice ASCII c viene invece rappresentato nel file compresso da x

Semplice Compressione

• Un esempio di funzione di codifica:• f(‘t’)=11• f(‘r’)=01• f(‘e’)=10

• Per concatenazione delle stringhe di bits possiamo allora calcolare: f(“tre”)=110110

• Ovviamente, con questa codifica viene richiesto meno spazio per memorizzare ogni lettera rispetto al caso di utilizzo del codice ASCII di 8-bit

Unicità della codifica

• Nella scelta del codice, è importante che ogni carattere venga mappato su di un valore differente• Supponiamo

• f(‘a’) = 110• f(‘%’)= 110

• quando si decomprime, come possiamo sapere quale dei due caratteri è rappresentato da 110?

• In termini matematici, la funzione di codifica deve essere iniettiva• Elementi differenti x y hanno immagini differenti

f(x) f(y)

Una domandaÉ possibile definire uno schema di compressione tale che

ogni possibile carattere (valore ASCII) venga rap-presentato da un numero di bits minore di 8?

• Quanti caratteri ASCII ci sono?• I caratteri ASCII differenti sono 256

• Quanti sono i numero che possiamo rappresentare con al più 7 bits?• 27-1 = 127

• Ci serve un valore diverso per ogni carattere – ma non ci sono abbastanza valori differenti rappresentabili con al più 7 bits

• Almeno un carattere deve essere rappresentato da più di 7 bits• In effetti, 128 caratteri verranno rappresentati con 8 o

più bits

Tipi di codice• Codici a lunghezza fissa: tutti caratteri sono codifi-

cati da stringhe di bits della stessa lunghezza.

• Codici a lunghezza variabile: i caratteri sono codifi-cati da stringhe di bits la cui lunghezza può variare da carattere a carattere (ad esempio a seconda della frequenza dei caratteri nel file).

Esempio: a b c d e f frequenze : 45 13 12 16 9 5

lunghezza fissa : 000 001 010 011 100 101

lunghezza variabile : 0 101 100 111 1101 1100

• fisso: per 100.000 caratteri servono 300.000 bits

• variabile: per 100.000 caratteri servono 224.000 bits

Un problema per la decodifica• Supponiamo:

• f(‘a’) = 11• f(‘b’) = 01• f(‘x’) = 1101

• Ora supponiamo che si tenti di decomprimere il file contenente 1101• Questo va tradotto in “ab” o in ‘x’?

• Questo problema di verifica perché questo è un codice a lunghezza variabile• ASCII è un codice a lunghezza fissa ...• … e sappiamo che ogni 8 bits inizia un nuovo

carattere

Codici a prefisso

• Un codice a prefisso è un codice in cui nessuna codifica è prefisso per una qualsiasi altra codifica• Se f(‘a’)=110, allora nessuna altra codifica inizia

con 110

• In questo caso trovare le interruzioni tra caratteri è facile:Si leggono i bits fino a che essi formano una

codifica legittima per un carattereTrasformarli nel carattere corrispondente e rico-

minciare a leggere il codice del carattere successivo• I codici a prefisso possono essere rappresentati

come alberi binari

Rappresentazione di codici a prefisso

B

A

C E

0 1

0 1

0 1

0

1

D

0

• Ogni foglia rappresenta un carattere

• Ogni arco sinistro è etichettato con 0, e ogni arco destro è etichettato con 1

• Il codice di ogni foglia è l’etichetta del percorso che la raggiunge a partire dalla radice

Rappresentazione di codici a prefisso

A: 00B: 010C: 011D: 100E: 101

Poiché ogni foglia corrisponde ad una carattere, questo deve essere un codice a prefisso

B

A

C E

0

0 1

0 1

0

1

D

0

1

Rappresentazione di codici a prefisso

Spazio sprecato

Non c’è motivo di avere un nodo non figlia con un solo figlio

B

A

C E

0

0 1

0 1

0

1

D

0

1

Rappresentazione di codici a prefisso

Possiamo quindi assumere che ogni nodo interno abbia due figli.In altre parole, l’albero è completo

B

A

C

E

0

0 1

0 1

1

D

0

1

A: 00B: 010C: 011D: 10E: 11

A: 00B: 010C: 011D: 100E: 101

Codici ottimi

Definizione: Dato un file F, diciamo che un codice C è ottimo per F se non esiste un altro codice tramite il quale F possa essere compresso impiegando un numero inferiore di bits.

• Nota: Esiste in genere più di un codice ottimo per un dato file - cioè il codice ottimo per F non è unico

Teorema: Dato in file F, esiste un codice ottimo C che è un codice a prefisso (che può cioè essere rappresentato come un albero completo)

Dimensione del file compresso

• Supponiamo di avere:• un file composto da caratteri nell’alfabeto • un albero T che rappresenta la codifica

• Quanti bits sono richiesto per codificare il file?• Per ogni c, sia dT(c) la profondità in T della

foglia che rappresenta c

• Il codice per c richiederà allora dT(c) bits

• Se f(c) è il numero di volte che c occorre nel file, allora la dimensione della codifice è

f(c1 ) dT(c1 ) + f(c2 ) dT(c2 ) + …sommatoria su tutti i caratteri c

Esempio

Un file con 7 A, 3 B, 6 C, 2 D e 8 E richiederà 7(2) + 3(3) + 6(3) + 2(2) + 8(2) = 61 bitsNota: Se avessimo scambiato i nodi C and D, avremmo

avuto bisogno di soli 57 bits

B

A

C

E

0

0 1

0 1

1

D

0

1

Progettazione di un codice

• Quando si progetta un codice per un file:• Minimizzare la lunghezza dei caratteri che

compaiono più frequentemente• Assegnare ai caratteri con la frequenza minore i

codici corrispondenti ai percorsi più lunghi all’in-terno dell’albero

• Questo è il principio sottostante i codici di Huffman!!!

Codici di Huffman

• Un codice (generalmente) è progettato per un file specifico• Costruito da un algoritmo specifico

• L’albero binario completo che rappresenta il codice creato dall’algoritmo è chiamato albero di Huffman

Costruzione del codice

f : 5 e : 9 c : 12 b : 13 d : 16 a : 45

Passo 1: Costruire un nodo foglia per ogni lettera, etichettato con la frequenza della lettera nel file

Costruzione del codice

f : 5 e : 9

c : 12 b : 13 d : 16 a : 45

Passo 2: Rimuovere i due nodi “più piccoli” (con frequenze minori)

Costruzione del codice

f : 5 e : 9

Passo 3: Collegarli ad un nodo padre etichettato con la frequenza combinata (sommata)

c : 12 b : 13 d : 16 a : 45

14

Costruzione del codice

f : 5 e : 9

c : 12 b : 13 d : 16 a : 4514

Passo 4: Aggiungere il nodo alla lista.

Costruzione del codice

f : 5 e : 9 c : 12 b : 13

d : 16 a : 45 14 25

Passo 5: Ripetere i passi 2-4 finché resta un solo nodo nella lista

Costruzione del codice

c : 12 b : 13 d : 16

a : 45 25

Paso 3: Continua finché resta un solo nodo nella lista

30

f : 5 e : 9

14

Costruzione del codice

a : 45 55

c : 12 b : 13 d : 16

25 30

f : 5 e : 9

14

Paso 3: Continua finché resta un solo nodo nella lista

Costruzione del codice

a : 45

100

55

c : 12 b : 13 d : 16

25 30

f : 5 e : 9

14

Paso 3: Continua finché resta un solo nodo nella lista

Costruzione del codice

a

100

55

c b d

25 30

f e

14

0

0

0 0

0

1

1

1 1

1

Gli archi dei percorsi dalla radice alle foglie presi in sequenza ci danno i codici associati ai caratteri

Algoritmo di Huffman

Huffman(A: array; n: intero)Q: Priority_Queue;for i = 1 to n

Insert(Q,A[i])for i = 1 to n - 1

x = Extract-Min(Q)y = Extract-Min(Q)

“crea un nuovo albero con radice z e valore Freq[x] + Freq[y] e figli

x e y” Insert(Q,z)return Extract-Min(Q)

Tempo di esecuzione

• Con una coda a priorità basata su lista:• Primo ciclo:

• Esegue una operazione di accodamento per ognuna delle n iterazioni – n O(1)

• Secondo ciclo:• Esegue due operazione di estrazione dalla coda e

una di accodamento per ognuna delle n-1 itera-zioni – (n-1) O(n)

• Totale: O(n2)• Con una coda a priorità basata su heap:

• Totale: O(n log n). Perché?

Codici di Huffman: correttezza

Teorema: Il codice di Huffman per in dato file è un codice a prefisso ottimo

• Schema della dimostrazione:• Sia C un qualsiasi codice a prefisso ottimo per il

file• Mostriamo che vale la proprietà di sottostruttura

ottima• Mostriamo che che vale la proprietà della scelta

greedy

• Cioè il codice di Huffman prodotto dall’algoritmo comprime il file tanto quanto un codice ottimo C

Codici di Huffman: correttezza

Lemma 1: Sia T un albero binario completo che rappresenta un codice a prefisso ottimo su un alfabeto , con frequenza f(c) per ogni c . Siano x, y le due foglie figlie di z in T.

Se eliminiamo x e y da T e consideriamo z un carattere con frequenza f(z)= f(x) + f(y), otteniamo un nuovo albero T’ = T - {x,y}.

T’ rappresenta un codice a prefisso ottimo per l’alfabeto ’= - {x,y} {z}.

Proprietà di sottostruttura ottima

Codici di Huffman: correttezza

Dimostrazione L1: Per ogni carattere c -{x,y} sappiamo che dT(c)=dT’(c), quindi anche che f(c)dT(c) = f(c)dT ’(c) .

Inoltre dT(x) = dT(y) = dT ’(z)+1.

Quindi f(x)dT(x) + f(y)dT(y) = [f(x) + f(y)](dT ’(z)+1) =

= f(z)dT ’(z) + [f(x) + f(y)]

Segue che B(T)=B(T’)+ [f(x) + f(y)]

Ora se T’ non è ottimo, esiste T’’ migliore di T’ per ’= - {x,y} {z} (cioè tale che B(T’’)<B(T’)).

Codici di Huffman: correttezza

Dimostrazione L1: Ora se T’ non è ottimo, esiste T’’ migliore di T’ per ’= - {x,y} {z} (cioè tale che B(T’’)<B(T’)).

Poiché z è un carattere per ’ sarà una foglia di T’’.

Ma aggiungendo x e y a T’’ come figli di z…

…quello che otteniamo è un codice a prefisso per .

Il costo del nuovo codice sarebbe

B(T’’)+[f(x)+f(y)] < B(T)

che contraddice l’ottimalità di T!

B(T)=B(T’)+ [f(x) + f(y)]

Codici di Huffman: correttezza

Lemma 2: Sia un alfabeto ai cui caratteri c sia asociata la frequenza f(c). Siano x e y due caratteri di con le frequenze minori.

Allora esiste un codice prefisso ottimo per nel quale i codici per x e y hanno la stessa lunghezza e che differiscono solo per l’ultimo bit.

Proprietà della scelta greedy

Codici di Huffman: correttezza

Dimostrazione L2: Partiamo da un qualunque albero T che rappresenta un codice ottimo e ne costruiremo uno diverso che sia ancora ottimo ma in cui i caratteri x e y siano foglie figlie dello stesso padre e a profondità massima in T.

Chiamiamo b e d due foglie di T a profondità massima e con lo stesso padre, mentre x e y saranno due foglie qualsiasi di T. Assumiamo f(b) f(d) e f(x) f(y)

x

y

b d

T

Codici di Huffman: correttezza

Dimostrazione L2: Per le ipotesi del lemma, x e y hanno le frequenze minori in assoluto, mentre b e d sono arbitrarie.

Quindi varranno anche: f(x) f(b) e f(y) f(d). Operiamo la trasformzione in due passi. Scambiamo la posizione di x e b ottenendo il nuovo albero T’ (passo 1). b

y

x d

T’

Codici di Huffman: correttezza

b

d

x y

T’’

Dimostrazione L2: Per le ipotesi del lemma, x e y hanno le frequenze minori in assoluto, mentre b e d sono arbitrarie.

Quindi varranno anche: f(x) f(b) e f(y) f(d). Operiamo la trasformzione in due passi. Poi scambiamo la posizio- ne di y e d ottenendo il nuovo albero T’’ (passo 2).

Dobbiamo ora verificare che T’’ rappresenti ancora un codice ottimo.

Codici di Huffman: correttezza

Dimostrazione L2: Calcoliamo la differenza di costo tra T e T’:

c

Tc

T cdcfcdcfTBTB )()()()()'()( '

)()()()( bdbfxdxf TT

)()()()( '' bdbfxdxf TT

)]()([)]()( xdbdxfbf TT [

)()()()( bdbfxdxf TT

)()()()( xdbfbdxf TT

0

Poiché le posizioni di x e b in T’ sono quelle di b e x rispettivamente in T

Poiché sia f(b) - f(x) che dT(b) - dT(x) sono 0f(x) f(b) e dT(x) dT(b) Cioé: B(T) B(T’)

Codici di Huffman: correttezza

Dimostrazione L2: In modo analogo a quanto appena fatto, si dimostra che passando da T’ a T’’ il costo dell’albero (del codice) non può aumentare (B(T’) - B(T’’) 0, cioè B(T’) B(T’’)).

In conclusuione: B(T) B(T’’).

Ma poiché T era ottimo per ipotesi, allora deve necessariamente valere B(T) = B(T’’).

Ora T’’ è un albero ottimo in cui x e y sono foglie a profondità massima dello stesso padre.

I codici di x e y avranno la stessa lunghezza e dif-feriranno quindi solo per l’ultimo bit.

Codici di Huffman: correttezza

In che senso però l’algoritmo di Huffman è greedy?• Cioè perché scegliere ad ogni passo i caratteri con

la frequenza minore è una scelta greedy?

Il costo di una fusione di due caratteri può essere visto come la somma delle frequenze dei due caratteri fusi assieme.

• Si può dimostrare che il costo totale di un albero (codice) è dato dalla somma dei costi delle operazioni di fusione necessarie.

Huffman ad ogni passo sceglie quindi tra tutte le fusioni quella che costa di meno.

Algoritmi Greedy

• L’algoritmo di Huffman è in esempio di algoritmo greedy:• Fonde ad ogni iterazione i due nodi più piccoli (per

frequenza), senza considerare affatto gli altri• Una volta che la scelta è stata fatta, la mantiene

fino alla fine – l’algoritmo non cambia mai decisione

• Nota: Un altro esempio a voi noto di algoritmo greedy è l’algoritmo di ordinamento Insertion Sort

Concusione

• Alberi binari completi possono rappresentare codici di compressione

• Una albero di Huffman rappresenta un particola-re codice per un dato file:• che è un codice ottimo per il file• che è generato da un algoritmo greedy