Codifica di Huffman: differenze tra le versioni

Versione delle 18:46, 9 mar 2014

Versione attuale delle 22:04, 13 mag 2025

(44 versioni intermedie di 34 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 binariebinaria e indice di frequenza delle lettere.]]

InNella [[informaticateoria dell'informazione]], per '''Codificacodifica di Huffman''' si intende un [[algoritmo]] di codifica dell'[[Entropiadei (teoria dell'informazione)|entropia]]simboli 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.

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.

== Storia ==

Nel [[1951]] a [[David A. Huffman]] e ada un suo collega al corso del MIT di Teoria dell'Informazione venne data la scelta tra una tesi scritta o un esame. Il docente, [[Robert M. Fano]], assegnò una tesi sul problema di trovare il codice binario più efficiente. Huffman, incapace di dimostrare un qualsiasi codice che fosse il più efficiente, si stava rassegnando all'idea di dover studiare per l'esame, quando gli venne l'idea di usare un [[albero binario]] ordinato in base alla frequenza, e così dimostrò velocemente che questo metodo era il più efficiente.

Un'idea simile era stata usata in precedenza nella [[Codifica di Shannon-Fano]] (creata da [[Claude Shannon]], inventore della [[teoria dell'informazione]], e Fano, il docente di Huffman), ma Huffman sistemò la sua più grande lacuna costruendo un albero ascendente anziché uno discendente.

Riga 15:

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

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

## PrendePrendi 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 ada ogni elemento basandosi sul path a partire dalla radice.

== Caratteristiche principali ==

Le frequenze usate possono essere quelle generiche nel dominio dell'applicazione basate su medie precalcolate, o possono essere le frequenze trovate nel testo che deve essere compresso (questa variante richiede che la [[tabella di frequenza]] sia registrata insieme alcon il testo compresso; vi sono diverse implementazioni che adottano dei trucchi per registrare queste tabelle efficientemente).

La codifica di Huffman è ottimale quando la probabilità di ciascun simbolo in input è una potenza negativa di due. Le codifiche senza prefissi tendono ada essere inefficienti sui piccoli alfabeti, quando le probabilità spesso cadono tra potenze di due. L'espansione di simboli adiacenti in "parole" prima della codifica di Huffman può essere di aiuto.

Casi limite della codifica di Huffman sono collegati alla [[Sequenza di Fibonacci]].

Riga 30:

== Variazioni ==

=== Codifica Adattivaadattiva di Huffman ===

Una variazione detta ''adattiva'' calcola le frequenze dinamicamente in base alle frequenze effettive più recenti nella stringa sorgente, in maniera analoga alla famiglia di algoritmi [[LZ77|LZ]].

Riga 40:

=== Codifica di Huffman con costi per lettera diseguali ===

Nel problema standard della codifica di Huffman, è dato un insieme di parole e per ciascuna paroleparola una frequenza positiva. Lo scopo è di codificacodificare ogni parola "p" con una parola-codice "c" in un dato alfabeto.

La ''Codifica di Huffman con costi per lettera diseguali'' è una generalizzazione in cui le lettere dell'alfabeto di codifica possono avere lunghezze non uniformi. L'obiettivo è di minimizzare la media pesata della lunghezza delle parole-codice.

== 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]] ed [[MP3]].

== Altri progetti ==

{{interprogetto|commonspreposizione=Category:Huffman codingsulla}}

== 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/davidmy-uncle/scientific.html-american Profilo di David A. Huffman], [[Scientific American]], settembre 1991, pagg. 54-58

* [{{cita web|http://huffman.ooz.ie/ |Generatore di grafici visuali dell'Albero di Huffman]}}

* [http://alexvn.freeservers.com/s1/huffman_template_algorithm.html Codifica a base-n a Template]

* [http{{cita web|https://mathforumrosettacode.org/discusswiki/sci.math/t/207334 La codicaHuffman_coding#Python|Codifica di Huffman e la serie diin Fibonacci]Python}}

* {{cita web |1=http://alexvn.freeservers.com/s1/huffman_template_algorithm.html |2=Codifica a base-n a Template |accesso=18 giugno 2005 |urlarchivio=https://web.archive.org/web/20050618085402/http://alexvn.freeservers.com/s1/huffman_template_algorithm.html |dataarchivio=18 giugno 2005 |urlmorto=sì }}

* [http://semillon.wpi.edu/~aofa/AofA/msg00040.html Calcolare la codifica di Huffman su una Macchina di Turing]

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

* 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]: 785-791

* {{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ì }}

* [http://www.cbloom.com/algs/statisti.html Codifiche statistiche]

* 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

* [http://www.cs.sfu.ca/CC/365/li/squeeze/Huffman.html Dimostrazione del funzionamento di questo algoritmo]

* [{{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]}}

{{Portale|ingegneria}}

Riga 65 ⟶ 66:

[[Categoria:Algoritmi di compressione]]

[[Categoria:Compressione dei dati]]

[[Categoria:Alberi binari]]