Codificación Huffman
Keywords: Codificación Huffman, 1952, Algoritmo de Huffman, Ciencias de la computación, Codificación, Compresión de datos, Entropía, Sonda espacial, Tierra
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.
Se ha demostrado que la codificación Huffman es el método de compresión más efectivo de entre los de su clase; cuando los símbolos aparecen en el texto con las mismas frecuencias que las que se utilizaron para construir el código.
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.
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.