Codifica di Huffman: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m - categoria |
m wikilink |
||
Riga 1:
In [[informatica]], per '''Codifica di Huffman''' si intende un [[algoritmo]] di codifica dell'[[Entropia (teoria dell'informazione)|entropia]] usato per la [[compressione]] di dati, basato sul principio di trovare il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere. Essa è stata sviluppata nel 1952 da [[David A. Huffman]], uno studente dottorando presso il [[Massachusetts Institute of Technology|MIT]], e pubblicata su ''A Method for the Construction of Minimum-Redundancy Codes'' (''Un Metodo per la Costruzione di Codici a Ridondanza Minima'').
La [[codifica]] di Huffman usa un metodo specifico per scegliere la rappresentazione di ciascun simbolo, risultando in un codice senza prefissi (cioè in cui nessuna stringa binaria di nessun simbolo è il prefisso della stringa binaria di nessun altro simbolo) che esprime il carattere più frequente nella maniera più breve possibile. È stato dimostrato che la codifica di Huffman è il più efficiente sistema di compressione di questo tipo: nessun'altra mappatura di simboli in stringhe binarie può produrre un risultato più breve nel caso in cui le frequenze di simboli effettive corrispondono a quelle usate per creare il codice.
Per un insieme di simboli la cui [[cardinalità]] è una [[potenza di due]] e con una distribuzione probabilistica uniforme, la codifica di Huffman equivale alla semplice codifica a blocchi binari.
| |||