Codifica di Huffman: differenze tra le versioni

Versione delle 12:29, 12 apr 2007

Versione attuale delle 22:04, 13 mag 2025

(91 versioni intermedie di 74 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.]]

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

== Tecnica base ==

Questa tecnica funziona creando un [[albero binario]] di simboli:

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

# Iniziare con tanti alberi quanti sono i simboli.

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

# Finché c'è più di un albero:

## 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 "genitore"

## Trovare quali sono i due alberi con larghezza totale minore.

## Assegna la somma del conteggio delle frequenze dei figli al genitore e ponilo nella lista in modo da mantenere l'ordine.

## Combinare i due alberi in uno solo, impostandone uno come il ramo di sinistra e l'altro come quello di destra.

## Cancella i figli dalla lista.

# Ora l'albero contiene tutti i simboli. Uno "0" rappresenta il successivo ramo di sinstra, un "1" rappresenta il successivo di destra.

# Assegna una parola codice a 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]].

La [[codifica aritmetica]] produce dei leggeri guadagni su quella di Huffman, ma questi guadagni risultano convenienti solamente se l'algoritmo per la codifica aritmetica è ottimale, in quanto una codifica ''banale'' richiede una maggiore complessità computazionale. Questa versione ''naifnaìf'', è per di più coperta da brevetto [[IBM]] nei suoi concetti centrali. Tali brevetti, però, non sono validi al di fuori degli [[Stati Uniti d'America|USA]], almeno fino all'approvazione definitiva dei [[brevetti software]] in [[Europa]].

== 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 39 ⟶ 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|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., Settembresettembre 1952, pagg. 1098-1102

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

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

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

* [http://mathforum.org/discuss/sci.math/t/207334 La codica di Huffman e la serie di Fibonacci]

* {{cita web|https://rosettacode.org/wiki/Huffman_coding#Python|Codifica di Huffman in Python}}

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

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

* 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|http://mathforum.org/discuss/sci.math/t/207334 |La codica di Huffman e la serie di Fibonacci]}}

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

* {{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.cs.sfu.ca/CC/365/li/squeeze/Huffman.html Dimostrazione del funzionamento di questo algoritmo]

* 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.datastructures.info/huffman-encoding-algorithm/ Spiegazione di cifratura del Huffman e 2 versioni del codice in C++]

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

[[Categoria:CodificaTeoria dell'informazione]]

[[Categoria:Algoritmi di compressione]]

[[Categoria:Compressione dei dati]]

[[Categoria:Alberi binari]]

[[cs:Huffmanovo kódování]]

[[de:Shannon-Fano-Kodierung]]

[[en:Huffman coding]]

[[es:Algoritmo de Huffman]]

[[fi:Huffmanin koodaus]]

[[fr:Codage de Huffman]]

[[he:קוד הופמן]]

[[ja:ハフマン符号]]

[[ko:허프만 코딩]]

[[nl:Huffmancodering]]

[[pl:Kodowanie Huffmana]]

[[pt:Codificação de Huffman]]

[[sv:Huffmankodning]]

[[th:รหัสฮัฟแมน และ รหัสแชนนอน-ฟาโน]]

[[zh:哈夫曼树]]