cerca
Algoritmi e strutture dati - Glossario Huffman
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Algoritmi e strutture dati - Glossario Huffman

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:

  1. Individuare la prima parola codice del file codificato.
  2. Tradurla nel carattere originale e aggiungere tale carattere al file decodificato.
  3. Rimuovere la parola codice dal file codificato.
  4. 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:

  1. Minimizzare la lunghezza dei caratteri che compaiono pi¨ frequentemente.
  2. 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:

  1. Si ottiene la frequenza di tutti i caratteri.
  2. Si costruisce il codice.
  3. Si rappresenta il file tramite il codice.
  4. 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