miniatura|Arbre de Huffman generat per les freqüències d'aparicions exactes del text "Això és un exemple d'arbre de Huffman". les freqüències i codis de cada caràcter es mostren a sota. codificar aquesta frase fent servir aquest codi requereix 156 bits, sense comptar amb l'espai per a l'arbre.

Caràcter Freqüència CodiEspai800E6100N31100O31110U30100A20101D21010F21011L20110M20111S211010B1110.110H1110.111J1111.100P1111.101R1111.110T1111.111 A ciències de la computació i teoria de la informació, la codificació Huffman és un algorisme utilitzat per compressió de dades. El terme es refereix a l'ús d'una taula de codis de longitud variable per a codificar un determinat símbol (com pot ser un caràcter en un fitxer), on la taula ha estat emplenada d'una manera específica basant-se en la probabilitat estimada d'aparició de cada possible valor d'aquest símbol. Va ser desenvolupat per David A. Huffman mentre era estudiant de doctorat en el MIT, i publicat a "A Method for the Construction of Minimum-Redundancy Codes".

La codificació Huffman fa servir un mètode específic per a triar la representació de cada símbol, que dona lloc a un codi prefix (és a dir, la cadena de bits que representa un símbol en particular mai és prefix de la cadena de bits d'un símbol diferent) que representa els caràcters més comuns utilitzant les cadenes de bits més curtes, i viceversa. Huffman va ser capaç de dissenyar el mètode de compressió més eficient d'aquest tipus: cap representació alternativa d'un conjunt de símbols d'entrada produeix una sortida mitjana més petita quan les freqüències dels símbols coincideixen amb les utilitzades per crear el codi. Posteriorment es va trobar un mètode per dur això a terme en un temps lineal si les probabilitats dels símbols d'entrada (és a dir "pesos") estan ordenades.

Per a un grup de símbols amb una distribució de probabilitat uniforme i un nombre de membres que és potència de dos, la codificació Huffman és equivalent a una codificació en bloc binària, per exemple, la codificació ASCII. La codificació Huffman és un mètode per crear codis prefix tan estès que el terme "codificació Huffman" és àmpliament usat com a sinònim de "codi prefix", fins i tot quan aquest codi no s'ha produït amb l'algorisme de Huffman.

Encara que la codificació de Huffman és òptima per a una codificació símbol a símbol donada una distribució de probabilitat, la seva optimalitat de vegades es pot veure accidentalment exagerada. Per exemple, la codificació aritmètica i la codificació LZW normalment ofereixen major capacitat de compressió. Aquests dos mètodes poden agrupar un nombre arbitrari de símbols per a una codificació més eficient, i, en general, s'adapten a les estadístiques d'entrada reals, i aquest últim és útil quan les probabilitats no es coneixen de manera precisa o varien sinificativamente dins del flux de dades.

Història El 1951, David Huffman i els seus companys de classe de l'assignatura "Teoria de la Informació" se'ls va permetre optar entre la realització d'un examen final o la presentació d'un treball. El professor Robert. M. Fano va assignar les condicions del treball sota la premissa de trobar el codi binari més eficient. Huffman, davant la impossibilitat de demostrar quin codi era més eficient, es va rendir i va començar a estudiar per l'examen final. Mentre estava en aquest procés va venir a la seva ment la idea d'utilitzar arbres binaris de freqüència ordenada i ràpidament va provar que aquest era el mètode més eficient.

Amb aquest estudi, Huffman va superar al seu professor, qui havia treballat amb l'inventor de la teoria de la informació Claude Shannon per tal de desenvolupar un codi similar. Huffman solucionar la major part dels errors en l'algorisme de codificació Shannon-Fano. La solució es basava en el procés de construir l'arbre de baix a dalt en comptes de al contrari.

Definició del problema Descripció informal Donats Un conjunt de símbols i els seus pesos (normalment proporcionals a probabilitats). Trobar Un codi binari prefix (un conjunt d'elements del codi) amb longitud de paraula esperada mínima (de forma equivalent, un arbre amb longitud del camí mínima).

Descripció formalitzada Entrades . L'alfabet , que és l'alfabet de símbols de mida . El conjunt , que és el conjunt de pesos (positius) dels símbols (normalment proporcionals a probabilitats), és a dir .

Sortida . El codi , que és el conjunt d'elements del codi (binari), on és la paraula del codi per .

Objectiu . Sigui la longitud del camí ponderat del codi . Condició: per a qualsevol codi .

Exemple Entrada ( A , W )Símbol ( a )abcdiSumaPes ( w )0,100,150,300,160,29= 1Sortida C Paraules del codi ( c ) 000 001 10 01 11 Longitud de la paraula (en bits) ( l )33222Longitud del camí ponderat ( l w )0,300,450,600,320,58 L ( C ) = 2.25optimalitatProbabilitat (2 - l )1/81/81/41/41/4= 1.00Quantitat d'informació (en bits) (- log w ) ≈3.322.741.742.641.79Entropia (- w log w )0.3320.4110.5210.4230.518 H ( A ) = 2205

Per a qualsevol codi biunívoc , aquell codi descodificar de forma única , la suma de les probabilitats de tots els símbols és sempre menor o igual que un. En aquest exemple, és exactament igual a un, pel que diem que és un codi complet . Si no és el cas sempre es pot derivar un codi equivalent afegint símbols extra (amb probabilitats nul associades), per fer el codi complet al mateix temps que es manté biunívoc .

Tal com va definir Shannon (1948), la quantitat d'informació h (en bits) de cada símbol a i amb probabilitat no nul és

L'entropia V (en bits) és la suma ponderada, de tots els símbols a amb probabilitat no nul w , de la quantitat d'informació de cada símbol:

(Nota: un símbol amb probabilitat zero té una contribució nul a l'entropia. Quan w = 0, és una indeterminació; aplicant la regla de L'Hôpital:

.

Per simplicitat, els símbols amb probabilitat nul han estat deixats fora de la fórmula anterior).

Com a conseqüència de teorema de codificació de font de Shannon, l'entropia és una mesura de la longitud de paraula més petita del codi que és teòricament possible per a un alfabet donat amb uns pesos associats. En aquest exemple, la longitud mitjana de la paraula és 2,25 bits per símbol, lleugerament més gran que l'entropia calculada de 2,205 bits per símbol. Així que no només aquest codi és òptim en el sentit que cap altre codi possible funciona millor, sinó que a més està molt a prop del límit teòric establert per Shannon.

Noteu que, en general, un codi Huffman no necessita ser únic, però si ho és sempre és un dels codis que minimitza .

Tècnica bàsica La tècnica utilitzada és el mateix algorisme de Huffman. Consisteix en la creació d'un arbre binari en què s'etiqueten els nodes fulla amb els caràcters, amb les seves freqüències, i de forma consecutiva es van unint cada parella de nodes que menys freqüència sumin, passant a crear un nou node intermedi etiquetatge amb aquesta suma. Es procedeix a realitzar aquesta acció fins que no queden nodes fulla per unir a cap node superior, i s'ha format l'arbre binari.

Posteriorment s'etiqueten les arestes que uneixen cada un dels nodes amb zeros i uns (fill dret i esquerre, respectivament, per exemple. El codi resultant per a cada caràcter és la lectura, seguint la branca, des de l'arrel cap a cada caràcter (o viceversa) de cadascuna de les etiquetes de les arestes.

Propietats principals Les probabilitats utilitzades poden ser genèriques per al domini de l'aplicació, que estan basades en el cas mitjana, o poden ser les freqüències reals trobades en el text que s'està comprimint. (Aquesta variació requereix que la taula de freqüències o una altra estructura utilitzada per a la codificació han de ser emmagatzemades amb el text comprimit, les implementacions fan servir diversos mecanismes per emmagatzemar taules de manera eficient).

La codificació Huffman és òptima quan la probabilitat de cada símbol d'entrada és una potència negativa de dos. Els codis prefixos tendeixen a ser lleugerament ineficients en alfabets petits, on les probabilitats normalment es troben entre aquests punts òptims. El "empaquetat", o expansió de la grandària de l'alfabet concatenant múltiples símbols a "paraules" de mida fixa o variable abans de la codificació Huffman, normalment ajuda, especialment quan símbols adjacents estan correlacionats (com en el cas d'un text en llenguatge natural). El pitjor cas per a una codificació Huffman pot donar-se quan la probabilitat d'un símbol excedeix 2 -1 = 0.5, fent el límit superior d'ineficiència il limitat. Aquestes situacions sovint responen bé a una forma de paquet anomenada codificació run-length.

La codificació aritmètica produeix una lleugera guany sobre la codificació Huffman, però en la pràctica aquest guany rarament ha estat prou gran com per utilitzar la codificació aritmètica que té una complexitat computacional més elevada i a més requereix el pagament de royalties. (A juliol de 2006, IBM té patents de molts mètodes de codificació aritmètica en diverses jurisdiccions).

Variacions Hi ha moltes variacions del codi de Huffman, alguns que utilitzen Huffman com algorisme, i altres que troba el codi prefix òptim. Tingueu en compte que en aquest últim cas el mètode no és necessàriament similar al de Huffmans i no té per què acabar en temps polinòmic.

Codi Huffman n-ari L'algorisme n-ari de Huffman fa servir l'alfabet{0,1, ...., N-1 'per codificar el missatge i construir un arbre n-ari. Aquest enfocament va ser considerat per Huffman en el seu enfocament originari.

Codi Huffman adaptable La variació anomenada codi de Huffman adaptable calcula dinàmicament la probabilitat de la freqüència de la cadena d'origen basada en antigues aparicions. Està relacionat amb la família d'algorismes LZ.

Algorisme de Huffman de plantilla La majoria de les vegades, la mida de les implementacions del codi de Huffman estan representades per probabilitats numèriques, però l'algorisme no ho exigeix, cal només una manera d'ordenar la mida i afegir. L'algorisme de plantilla de Huffman permet utilitzar qualsevol tipus de mida (costos, freqüències, els parells de la mida, mides no numèrics) i un dels molts que combina mètodes (no només l'addició). Aquests algorismes poden resoldre problemes de minimització, com la minimització de Max [Wi+C (i)], un problema que es va aplicar per primera vegada en el disseny de circuits.

Codi de Huffman de mida limitat El Codi de Huffman de mida de limitat és una variant on l'objectiu és aconseguir que el camí de cost mínim amb la restricció que la longitud de cada paraula sigui menor que una constant. L'algorisme de package-merge ho soluciona amb un algorisme voraç, molt similar a l'usat per l'algorisme de Huffman. La seva complexitat és de l'ordre de O (nL), sent L la mida de la paraula més llarga. No es coneix algorisme per resoldre aquest problema en temps lineal, a diferència dels problemes convencionals de Huffman.

Codificació Huffman amb costos desiguals En el problema estàndard de la codificació Huffman, s'assumeix que cada símbol de l'alfabet amb el qual es construeix cada paraula del codi té igual cost de transmissió: una paraula del codi la longitud sigui N dígits sempre tindrà un cost de N , sense importar quants d'aquests dígits siguin zeros, quants uns, etc. Quan es treballa sota aquesta suposició, minimitzar el cost total del missatge i minimitzar el nombre total de dígits és el mateix.