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 ::
Codici di 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.
Codici prefissi
Un codice prefisso è un codice in cui nessuna parola è prefisso da una ulteriore parola. Per la sua decodifica si procede come segue:
- Individuare la prima parola codice del file codificato.
- Tradurla nel carattere originale e aggiungere tale carattere al file decodificato.
- Rimuovere la parola codice dal file codificato.
- Ripetere l'operazione per i successivi caratteri.
Per facilitare la suddivisione del file codificato in parole codice è comodo rappresentare il codice con un albero binario.
Definizione formale del problema
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.
Algoritmo greedy di Huffman
Principio del codice di Huffman:
- Minimizzare la lunghezza dei caratteri che compaiono più frequentemente.
- Assegnare ai caratteri con la frequenza minore i codici corrispondenti ai percorsi più lunghi all'interno dell'albero.
Un codice è progettato per un file specifico:
- Si ottiene la frequenza di tutti i caratteri.
- Si costruisce il codice.
- Si rappresenta il file tramite il codice.
- Si aggiunge al file una rappresentazione del codice.
Esempio:
Complessità algoritmo di Huffman
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.
Torna alla pagina di Algoritmi e strutture dati
