Codificació de Huffman

Caràcter	Freqüència	Codi
Espai	8	00
E	6	100
N	3	1100
O	3	1110
U	3	0100
A	2	0101
D	2	1010
F	2	1011
L	2	0110
M	2	0111
S	2	11010
B	1	110.110
H	1	110.111
J	1	111.100
P	1	111.101
R	1	111.110
T	1	111.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 $A=\left\{a_{1},a_{2},\cdots ,a_{n}\right\}$ , que és l'alfabet de símbols de mida $n$ .
El conjunt $W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}$ , que és el conjunt de pesos (positius) dels símbols (normalment proporcionals a probabilitats), és a dir $w_{i}=\mathrm {pes} \left(a_{i}\right),1\leq i\leq n$ .

Sortida .
El codi $C\left(A,W\right)=\left\{C_{1},C_{2},\cdots ,C_{n}\right\}$ , que és el conjunt d'elements del codi (binari), on $C_{i}$ és la paraula del codi per $a_{i},1\leq i\leq n$ .

Objectiu .
Sigui $L\left(C\right)=\sum _{i=1}^{num}{w_{i}\times \mathrm {longitud} \left(C_{i}\right)}$ la longitud del camí ponderat del codi $C$ . Condició: $L\left(C\right)\leq l\left(T\right)$ per a qualsevol codi $T\left(A,W\right)$ .

Exemple

Entrada ( A , W )	Símbol ( a _i)	a	b	c	d	i	Suma
Entrada ( A , W )	Pes ( w _i)	0,10	0,15	0,30	0,16	0,29	= 1
Sortida C	Paraules del codi ( c _i)	`000`	`001`	`10`	`01`	`11`
	Longitud de la paraula (en bits) ( l _i)	3	3	2	2	2
	Longitud del camí ponderat ( l _i w _i)	0,30	0,45	0,60	0,32	0,58	L ( C ) = 2.25
optimalitat	Probabilitat (2 ^{- l _i})	1/8	1/8	1/4	1/4	1/4	= 1.00
	Quantitat d'informació (en bits) (- log ₂ w _i) ≈	3.32	2.74	1.74	2.64	1.79
	Entropia (- w _i log ₂ w _i)	0.332	0.411	0.521	0.423	0.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

H(a_{i})=\log _{2}{1 \over w_{i}}.

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

H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}{w_{i}}.

(Nota: un símbol amb probabilitat zero té una contribució nul a l'entropia. Quan w = 0, $w\log _{2}(1/w)=0\cdot \infty$ és una indeterminació; aplicant la regla de L'Hôpital:

\lim _{w\to 0^{+}}{\frac {\log _{2}{\frac {1}{w}}}{\frac {1}{w}}}=\lim _{w\to 0^{+}}{\frac {-{\frac {1}{w\ln 2}}}{-{\frac {1}{w^{2}}}}}=\lim _{w\to 0^{+}}{\frac {w}{\ln 2}}=0

.

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 $L(C)$ .

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, es requereix 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.

A la codificació Huffman amb costos desiguals la suposició anterior ja no és veritable: els símbols de l'alfabet poden tenir longituds no uniformes, a causa de característiques del medi de transmissió. Un exemple és l'alfabet de l'codi Morse, on una 'ratlla' requereix més temps per ser enviada que un 'punt', i per tant el cost del temps de transmissió d'una ratlla és més gran. L'objectiu segueix sent minimitzar la longitud mitjana de la paraula de codi, però no n'hi ha prou amb minimitzar el nombre de símbols utilitzat en el missatge. No es coneix un algorisme per solucionar això de la mateixa manera o amb la mateixa eficiència que la codificació Huffman convencional.

Arbres binaris alfabètics òptims (Codificació Hu-Tucker)

En una situació de codificació Huffman estàndard, s'assumeix que qualsevol codi pot correspondre amb qualsevol símbol d'entrada. En la versió alfabètica , l'ordre alfabètic de les entrades i sortides ha de ser idèntic. Així, per exemple, a l'entrada $A=\left\{a,b,c\right\}$ no se li pot assignar $H\left(A,C\right)=\left\{00,1,01\right\}$ , sinó que li correspondria $H\left(A,C\right)=\left\{00,01,1\right\}$ o $H\left(A,C\right)=\left\{0,10,11\right\}$ . Això també es coneix com el problema de Hu-Tucker , pels autors de la publicació que conté la primera solució linearítmica al problema amb optimalitat binària alfabètica, que és similar a l'algorisme de Huffman, però no és una variació del mateix. Aquests arbres binaris alfabètics òptims són usats sovint com aboleix binaris de cerca.

Codi canònic de Huffman

Si els pesos corresponents a les entrades (ordenades alfabèticament) estan en ordre numèric, els codis de Huffman tenen la mateixa longitud que els codis alfabètic òptims, així que poden calcular com aquestes últimes, fent que la codificació Hu-Tucker sigui innecessària. El codi resultant de les entrades (re) ordenades numèricament es coneix com a codi canònic de Huffman i és el codi que normalment es fa servir en la pràctica, donada la seva facilitat per a codificar i descodificar. La tècnica per trobar aquest codi es coneix com a codificació de Huffman-Shannon-Fano , ja que és òptima com la codificació de Huffman, i alfabètica segons la probabilitat dels pesos, com la codificació de Shannon-Fano.

Aplicacions

La Codificació Aritmètica es pot considerar com una generalització de la codificació de Huffman, de fet, en la pràctica la codificació Aritmètica ve precedida per la codificació de Huffman, ja que és més fàcil trobar una aritmètica per a una entrada binària que per a una no binària. D'altra banda tot i que la codificació de compressió ofereix millor rendiment que la codificació de Huffman, la codificació de Huffman es troba encara en ús generalitzat per la seva simplicitat, alta velocitat, i manca de problemes de patents.

La codificació de Huffman s'utilitza sovint en algun altre mètode de compressió, com la deflació i còdec multimèdia com JPEG i MP3 que tenen una quantificació digital basada en la codificació de Huffman.

Exemple

Una sonda espacial ha estat llançada a l'espai per explicar cert tipus de pertorbacions estel·lars. Ha de comptar quantes es produeixen en cada minut, i té cada dia una estona bastant reduïda per enviar les dades a Terra, per tant, interessa escurçar al màxim el temps de transmissió, i per això es recorre a codificar les mostres mitjançant un codi de Huffman.

En la següent taula es mostren els valors a transmetre, juntament amb les seves freqüències relatives, el seu codi en una codificació binària de 3 bits, i el seu codi en un possible codi Huffman per a aquests valors.

Valor	Freqüència	Codi binari	Codi Huffman
0	10%	000	010
1	20%	001	10
2	30%	010	00
3	25%	011	11
4	10%	100	0110
5 o més	5%	101	0111

Es pot observar que, en la codificació binària, tots els possibles valors reben codis del mateix nombre de bits, mentre que en la codificació Huffman, cada valor té un nombre diferent de bits: els codis més freqüents tenen dos bits, mentre que els menys freqüents tenen quatre bits.

A continuació s'observa el codi necessari per transmetre la següent sèrie de valors:

5,4,2,3,2,2,1,0,1,3,2,4,3,4,3,2,3,4,2,4

Utilitzant la codificació binària, seria una sèrie de 60 bits, és a dir, 3 bits per símbol.

101100010011010010001000001011010100011100011010011100010100

nota: s'ha afegit la mateixa sèrie separada en blocs amb l'única raó de facilitar una transcripció manual lliure d'errors per a un estudi per part del lector interessat.

101.100.010.011.010.010.001.000.001.011.010.100.011.100.011.010.011.100.010.100

Utilitzant, en canvi, la codificació Huffman, s'hauria d'enviar una seqüència de 53 bits, és a dir, 2,65 bits per símbol.

01110110001100001001010110001101101101100110110000110

nota: la mateixa sèrie dividida en blocs de 4 bits per a la mateixa observació anterior.

0111.0110.0011.0000.1001.0101.1000.1101.1011.0110.0110.1100.0011.0

En aquest exemple, la mitjana de bits per símbol que es podria esperar d'aquesta codificació, en cadenes de valors més llargues, és de 2,4.

Per a la seva comparació, l'entropia del conjunt de símbols és de 2,366, és a dir, el millor mètode de compressió seria capaç de codificar aquests valors utilitzant 2,366 bits per símbol.

És possible, també, apreciar com es poden extreure sense cap ambigüitat els valors originals a partir de la cadena codificada mitjançant Huffman.

Cal afegir que la codificació de Huffman no pot ser aplicada a imatges en blanc i negre perquè és incapaç de produir compressió sobre un alfabet binari.

Vegeu també

Algorisme de Huffman
D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the IRE, setembre 1952, pp 1098-1102
Codi canònic de Huffman
Codificació Aritmètica

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Codificació de Huffman

Huffman en PHP.