Codificació Huffman

Arbre de Huffman generat per a les freqüències d'aparicions exactes del text "ESTO ES UN EJEMPLO DE UN ARBOL DE HUFFMAN". Les freqüències i còdics de cada caràcter es mostren avall. Codificar esta frase de 41 caràcters usant este còdic requerix 156 bits (sense contar en l'espai per a l'arbre) quan en bytes de 8 bits requerix 328 bits.

Caràcter	Freqüència	Còdic
Espai	8	00
I	6	100
N	3	1100
O	3	1110
O	3	0100
A	2	0101
D	2	1010
F	2	1011
L	2	0110
M	2	0111
S	2	11010
B	1	110110
H	1	110111
J	1	111100
P	1	111101
R	1	111110
T	1	111111

En ciències de la computació i teoria de l'informació, la codificació Huffman és un algoritme usat para compressió de senyes. El terme es referix a l'us d'una taula de còdics de llongitut variable per a codificar un determinat símbol (com pot ser un caràcter en un archiu), a on la taula ha segut reblida d'una manera específica basant-se en la provabilitat estimada d'aparició de cada possible valor de dit símbol. Va ser desenrollat per David A. Huffman mentres era estudiant de doctorat en el MIT, i publicat en "A Method for the Construction of Minimum-Redundancy Codes".

La codificació Huffman usa un método específic per a elegir la representació de cada símbol, que dona lloc a un còdic prefixe (és dir, la cadena de bits que representa a un símbol en particular mai és prefix de la cadena de bits d'un símbol distint) que representa els caràcters més comuns usant les cadenes de bits més curtes, i viceversa. Huffman va ser capaç de dissenyar el método de compressió més eficient d'este tipo: cap representació alternativa d'un conjunt de símbols d'entrada produïx una eixida mija més chicoteta quan les freqüències dels símbols coincidixen en les usades per a crear el còdic. Posteriorment es va trobar un método per a dur açò a veta en un temps llineal si les provabilitats dels símbols d'entrada (també conegudes com "pesos") estan ordenades.

Per a un grup de símbols en una distribució de provabilitat uniforme i un número de membres que és potència de dos, la codificació Huffman és equivalent a una codificació en bloc binaria, per eixemple, la codificació ASCII. La codificació Huffman és un método per a crear còdics prefixe tan estés que el terme "codificació Huffman" és àmpliament usat com a sinònim de "còdic prefixe", inclús quan dit còdic no s'ha produït en l'algoritme de Huffman.

Encara que la codificació de Huffman és òptima per a una codificació símbol a símbol donada una distribució de provabilitat, la seua optimalidad a voltes pot vore's accidentalment exagerada. Per eixemple, la codificació aritmètica i la codificació LZW normalment oferixen major capacitat de compressió. Estos dos métodos poden agrupar un número arbitrari de símbols per a una codificació més eficient, i en general s'adapten a les estadístiques d'entrada reals. Este últim és útil quan les provabilitats no es coneixen de forma precisa o varien significativament dins del fluix de senyes.

Història

En 1951, a David Huffman i als seus companyers de classe de l'assignatura “Teoria de l'Informació” se'ls va permetre optar entre la realisació d'un examen final o la presentació d'un treball. El professor Robert. M. Fano va assignar les condicions del treball baix la premissa de trobar el còdic binario més eficient. Huffman, davant l'impossibilitat de demostrar qué còdic era més eficient, es va rendir i va escomençar a estudiar per a l'examen final. Mentres estava en este procés va vindre a la seua ment l'idea d'usar arbres binarios de freqüència ordenada i ràpidament va provar que este era el método més eficient.

En este estudi, Huffman va superar al seu professor, qui havia treballat en l'inventor de la teoria de l'informació Claude Shannon en la finalitat de desenrollar un còdic similar. Huffman va solucionar la major part dels errors en l'algoritme de codificació Shannon-Fano. La solució es basava en el procés de construir l'arbre d'avall a dalt en lloc del contrari.

Definició del problema

Descripció informal

Daus: Un conjunt de símbols i els seus pesos (normalment proporcionals a provabilitats).
Trobar: Un còdic binario prefix (un conjunt d'elements del còdic) en llongitut de paraula esperada mínima (de forma equivalent, un arbre en llongitut del camí mínima).

Descripció formal

Entrades

L'alfabet $A = {a_{1}, a_{2}, \dots, a_{n}}$ , que és l'alfabet de símbols de tamany $n$ .
El conjunt $W = {w_{1}, w_{2}, \dots, w_{n}}$ , que és el conjunt de pesos (positius) dels símbols (normalment proporcionals a provabilitats), és dir $w_{i} = p e s o (a_{i}), 1 \leq i \leq n$ .

Eixida

El còdic $C (A, W) = {c_{1}, c_{2}, \dots, c_{n}}$ , que és el conjunt d'elements del còdic (binario), a on $c_{i}$ és la paraula del còdic per a $a_{i}, 1 \leq i \leq n$ .

Objectiu

Siga $L (C) = \sum_{i = 1}^{n} w_{i} \times l o n g i t u d (c_{i})$ la llongitut del camí ponderat del còdic $C$ . Condició: $L (C) \leq L (T)$ per a qualsevol còdic $T (A, W)$ .

Eixemple

Entrada (A, W)	Símbol (a_i)	a \|align="center" style="background:#"\| b	c	d	i	Suma
Entrada (A, W)	Pes (w_i)	0.10	0.15	0.30	0.16	0.29	= 1
Eixida C	Paraules del còdic (c_i)	`010`	`011`	`11`	`00`	`10`
	Llongitut de la paraula (en bits) (l_i)	3	3	2	2	2
	Llongitut del camí ponderat (l_i w_i )	0.30	0.45	0.60	0.32	0.58	L(C) = 2.25
Optimalidad	Provabilitat (2^-l_i)	1/8	1/8	1/4	1/4	1/4	= 1.00
	Cantitat d'informació (en bits) (−log₂ w_i) ≈	3.32	2.74	1.74	2.64	1.79
	Entropía (−w_i log₂ w_i)	0.332	0.411	0.521	0.423	0.518	H(A) = 2.205

Per a qualsevol còdic biunívoco, aquell còdic decodificable de forma única, la suma de les provabilitats de tots els símbols és sempre menor o igual que un. En este eixemple, és exactament igual a un; per lo que diem que és un còdic complet. Si no és el cas, sempre es pot derivar un còdic equivalent afegint símbols extra (en provabilitats nules associades), per a fer el còdic complet al mateix temps que es manté biunívoco.

Tal com va definir Shannon (1948), la cantitat d'informació h (en bits) de cada símbol a_i en provabilitat no nula w_i és

h (a_{i}) = \log_{2} \frac{1}{w_{i}} .

l'entropía H (en bits) és la suma ponderada, de tots els símbols a_i en provabilitat no nula w_i, de la cantitat 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} \frac{1}{w_{i}} = - \sum_{w_{i} > 0} w_{i} \log_{2} w_{i} .

(Nota: un símbol en provabilitat zero té una contribució nula a la entropía. Quan w = 0, $w \log_{2} (1 / w) = 0 \cdot \infty$ és una indeterminación; 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 en provabilitat nula han segut deixats fòra de la fòrmula anterior).

Com a conseqüència del teorema de codificació de font de Shannon, la entropía és una mida de la llongitut de paraula més chicoteta del còdic que és teòricament possible per a un alfabet donat en uns pesos associats. En este eixemple, la llongitut mija de la paraula és 2,25 bits per símbol, llaugerament major que la entropía calculada de 2,205 bits per símbol. Aixina que no solament este còdic és òptim en el sentit de que cap atre còdic possible funciona millor, sino que ademés està molt propenc al llímit teòric establit per Shannon.

Note's que, en general, un còdic Huffman no necessita ser únic, pero si ho és sempre és un dels còdics que minimisa $L (C)$ .

Bibliografia

D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., sept 1952, pp 1098-1102

Vore també

Este artícul conté una traducció derivada de «Codificación Huffman» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.