Torna alla pagina di Algoritmi e strutture dati
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)
:: Algoritmi e strutture dati - Glossario Huffman ::
Vengono ampiamente usati nella compressione dei dati. Permettendo un risparmio compreso tra il 20% e 90% secondo il tipo di file. Sulla base delle frequenze con cui ogni carattere appare nel file, l'algoritmo greedy di Huffman trova un codice ottimo. Associa ad ogni carattere una sequenza di bit detta parola codice.
Un codice prefisso è un codice in cui nessuna parola è prefisso da una ulteriore parola. Per la sua decodifica si procede come segue:
Per facilitare la suddivisione del file codificato in parole codice è comodo rappresentare il codice con un albero binario.
Codice ottimo: Dato un file F, un codiceC è ottimo per F se non esiste un altro codice tramite il quale F possa essere compresso impiegando un numero inferiore di bit.
Nota: Il codice ottimo dipende dal particolare file e possono esistere più soluzioni ottime.
Teorema: I codici a prefisso ottimi sono rappresentati da un albero in cui tutti i nodi interni hanno due figli.
Principio del codice di Huffman:
Un codice è progettato per un file specifico:
Esempio:
La complessità è pari a O(n log n)
L'algoritmo di Huffman è greedy perchè ad ogni passo costruisce il nodo interno avente frequenza minima possibile.