2023-11-17 - Huffman

universityin-classsubject-2101

2023-11-17

Algoritmi

Compressione

Algoritmo di Huffman

Serve per effettuare una compressione. Ridurre il numero di bit necessari per rappresentare un’informazione.
Si utilizza una lunghezza variabile di bit a seconda della frequenza del carattere da rappresentare (più il carattere è frequente, meno saranno i bit a rappresentarlo).

Codice Prefisso
La codifica di un carattere non deve mai essere il prefisso della codifica di un altro carattere.
Questo è necessario in quanto, se non rispettato, non si saprebbe come effettuare la decodifica (ci sarebbero delle ambiguità).

Si consideri l’alfabeto.
Indichiamo con la frequenza del carattere all’interno del testo.
Indichiamo con il numero di bit necessari per rappresentare il carattere .

La formula indica il numero di bit necessari per rappresentare il testo di riferimento.
L’obiettivo è cercare di minimizzare questo valore, definendo opportunamente (rispettando sempre il codice prefisso).

La rappresentazione delle codifiche dei caratteri può essere definita da un albero binario (dove a sinistra il prossimo bit è e a destra ). Tutti i caratteri si troveranno nelle foglie (se non sono nelle foglie, la regola del codice prefisso non sarebbe rispettata).

Il livello (“l’altezza”) di un nodo è detto profondità.

è detta valutazione e va minimizzata.

Ricerca della valutazione ottimale

Ogni nodo ha due figli. Se ne avesse uno solo, allora il padre potrebbe essere sostituito con il figlio, riducendo di bit la rappresentazione dei caratteri del sotto-albero.

Per ogni carattere, si prendono i due caratteri più piccoli e si associano come figli di un nuovo nodo che ha come frequenza la somma dei figli (guarda libro pag. 359).

HUFFMAN(C, n):
	Q = BuildMinHeap(C)
	FOR i=1 TO n-1:
		z = new node()
		z.left = x = Q.ExtractMin()
		z.right = y = Q.ExtractMin()
		z.freq = x.freq + y.freq
		Q.Insert(z)
	RETURN Q.ExtractMin()