Codificación Huffman
De Wikipedia, la enciclopedia libre
En las Ciencias de la computación, la Codificación Huffman es una codificación utilizada para compresión de datos, desarrollada por David A. Huffman en 1952, y publicada en A Method for the Construction of Minimum-Redundancy Codes.
Un código de Huffman es un código de longitud variable, en el que la longitud de cada código depende de la frecuencia relativa de aparición de cada símbolo en un texto: cuanto más frecuente sea un símbolo, su código asociado será más corto. Además, un código Huffman es un código libre de prefijos: es decir, ningún código forma la primera parte de otro código; esto permite que los mensajes codificados sean no ambiguos.
Este es el codificador estadístico más popular, y erróneamente se tiende a pensar que su funcionamiento es óptimo. Este algoritmo es capaz de producir un código óptimo en el sentido de Mínima Redundancia para el código de entrada. Esta compresión sólo será óptima si las probabilidades de todos los símbolos de entrada son potencias enteras de 1/2. Y el peor de todos los casos se presentará cuando alguno de los símbolos posean una probabilidad cercana al 100%. (Una foto de un paisaje con la mayor parte con cielo azul, foto de cielo estrellado)
Huffman también describió un algoritmo para obtener un código de Huffman a partir de un conjunto de símbolos y otro con sus frecuencias asociadas.
[editar] Historia
En 1951, a David Huffman y sus compañeros de clase de la asignatura “Teoría de la Información” fue asignada la opción de la presentación de un exáment final o un paper. El profesor Robert. M Fano asignó las condiciones del paper bajo la premisa de encontrar el código binario más eficiente. Huffman ante la imposibilidad de demostrar que código era más eficiente, se rindió e inicio a estudiar para el examen final, mientras estaba en este proceso vino a su mente la idea de usar árboles binarios de frecuencia ordenada y rápidamente probó que este era el método más eficiente.
Con este estudio, Huffman supero a su porfesor, quien había trabajado con el inventor de la teoría de la información Claude Shannon con el fin de desarrollar un código similar. Huffman arreglo la mayor de las fallas del algoritmo de codificación Shannon-Fano. La solución constituía en el proceso de construir el árbol desde el fondo hasta la raíz en vez de la raíz hacia abajo.
[editar] Ejemplo
Una sonda espacial ha sido lanzada al espacio para contar cierto tipo de perturbaciones estelares. Ha de contar cuántas se producen en cada minuto, y tiene cada día una ventana de tiempo bastante reducida para enviar los datos a Tierra; por tanto, interesa reducir al máximo el tiempo de transmisión, y para ello se recurre a codificar las muestras mediante un código de Huffman.
En la siguiente tabla se muestran los valores a transmitir, junto con sus frecuencias relativas, su código en una codificación binaria de 3 bits, y su código en un posible código Huffman para estos valores.
| Valor | Frecuencia | Código binario | Código 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 |
Puede observarse que, en la codificación binaria, todos los posibles valores reciben códigos del mismo número de bits, mientras que en la codificación Huffman, cada valor tiene un número diferente de bits: los códigos más frecuentes poseen dos bits, mientras que los menos frecuentes poseen cuatro bits.
A continuación se observa el código necesario para transmitir la siguiente serie de valores:
5,4,2,3,2,2,1,0,1,3,2,4,3,4,3,2,3,4,2,4
Utilizando la codificación binaria, sería una serie de 60 bits; es decir, 3 bits por símbolo.
101100010011010010001000001011010100011100011010011100010100
Utilizando, en cambio, la codificación Huffman, se tendría que enviar una secuencia de 53 bits; es decir, 2,65 bits por símbolo.
01110110001100001001010110001101101101100110110000110
En este ejemplo, la media de bits por símbolo que cabría esperar de esta codificación, en cadenas de valores más largas, es de 2,4.
Para su comparación, la entropía del conjunto de símbolos es de 2,366; es decir, el mejor método de compresión sería capaz de codificar estos valores utilizando 2,366 bits por símbolo.
Es posible, también, apreciar cómo es posible extraer sin ninguna ambigüedad los valores originales a partir de la cadena codificada mediante Huffman.
Hay que añadir que la codificación de Huffman no puede ser aplicada a imágenes en blanco y negro porque es incapaz de producir compresión sobre un alfabeto binario.
[editar] Véase también
- Algoritmo de Huffman
- D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., sept 1952, pp 1098-1102
