Codifica di Huffman: differenze tra le versioni

Versione delle 12:52, 17 ott 2018

Versione delle 19:45, 5 dic 2018

Riga 1:

[[File:Huffman tree.svg|thumb|upright=1.8|Codifica di Huffman della frase "this is an example of a huffman tree" con rappresentazione binaria e indice di frequenza delle lettere.]]

InNella [[informaticateoria dell'informazione]], per '''Codifica di Huffman''' si intende un [[algoritmo]] di codifica dei simboli, tale da massimizzare l'entropia, usato per la [[Compressione dei dati|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 prefisso|codice senza prefissi]] (cioè in cui nessuna stringa binaria di nessun simbolo è il [[sottostringa|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.