Codifica di Huffman: differenze tra le versioni

Versione delle 19:45, 5 dic 2018

Versione attuale delle 22:04, 13 mag 2025

(11 versioni intermedie di 10 utenti non mostrate)

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.]]

Nella [[teoria dell'informazione]], per '''Codificacodifica 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 [[Stringa (informatica)|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'' (''lett. "Un Metodometodo per la Costruzionecostruzione di Codicicodici a Ridondanzaridondanza Minima''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.

Riga 16:

# Ordina i simboli, in una lista, in base al conteggio delle loro occorrenze.

# Ripeti i seguenti passi finché la lista non contiene un unico simbolo:

## Prendi dalla lista i due simboli con la frequenza di conteggio minore. Crea un albero di Huffman che ha come "figli" questi due elementi, e crea un nodo di "genitorigenitore"

## Assegna la somma del conteggio delle frequenze dei figli aial genitorigenitore e li poneponilo nella lista in modo da mantenere l'ordine.

## Cancella ili figliofigli dalla lista.

# Assegna una parola codice a ogni elemento basandosi sul path a partire dalla radice.

Riga 44:

== Applicazioni ==

Oggi la codifica di Huffman è spesso usata come complemento di altri metodi di compressione: sono esempi [[PKZIP]], e dei successori [[ZIP (formato di file)|ZIP]] e [[WinRar]]) e [[codec]] multimediali quali [[Joint Photographic Experts Group|JPEG]] e [[MP3]].

[[Deflate]] (l'algoritmo di [[PKZIP]], e dei successori [[ZIP (formato di file)|ZIP]] e [[WinRar]]) e [[codec]] multimediali quali [[Joint Photographic Experts Group|JPEG]] e [[MP3]].

== Altri progetti ==

{{interprogetto|commons=Category:Huffman coding|preposizione=sulla}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* L'articolo originale di Huffman: D.A. Huffman, "[https://web.archive.org/web/20050530145744/http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf A method for the construction of minimum-redundancy codes]", Proceedings of the I.R.E., settembre 1952, pagg. 1098-1102

* Il background: [http://www.huffmancoding.com/my-uncle/scientific-american Profilo di David A. Huffman], [[Scientific American]], settembre 1991, pagg. 54-58

Riga 58:

* {{cita web|http://mathforum.org/discuss/sci.math/t/207334|La codica di Huffman e la serie di Fibonacci}}

* {{cita web |1=http://semillon.wpi.edu/~aofa/AofA/msg00040.html |2=Calcolare la codifica di Huffman su una Macchina di Turing |accesso=31 luglio 2005 |urlarchivio=https://web.archive.org/web/20050731091059/http://semillon.wpi.edu/~aofa/AofA/msg00040.html |dataarchivio=31 luglio 2005 |urlmorto=sì }}

* Mordecai J. Golin, Claire Kenyon, Neal E. Young "[http://www.cs.ust.hk/faculty/golin/pubs/LOP_PTAS_STOC.pdf Codifica di Huffman con costi per lettera diseguali]", [http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2002.html STOC 2002] {{Webarchive|url=https://web.archive.org/web/20150116064338/http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2002.html |data=16 gennaio 2015 }}: 785-791

* {{cita web|http://www.cbloom.com/algs/statisti.html|Codifiche statistiche}}

* {{cita web|http://www.cs.sfu.ca/CC/365/li/squeeze/Huffman.html|Dimostrazione del funzionamento di questo algoritmo}}