Existen muchos métodos de compresión y códigos en el mundo de la informática. Con ellos se consigue reducir los datos para poder almacenarlos con menos exigencias de capacidad o transmitirlos a mayor velocidad. Aquí nos adentraremos en el código Huffman, que tal vez desconozcas.
Índice de contenidos
¿Qué es el código Huffman?
El código Huffman es una técnica de codificación utilizada en compresión de datos sin pérdida, desarrollada por David A. Huffman en 1952 como parte de un trabajo académico. Este método se fundamenta en la teoría de la información y busca minimizar el tamaño medio de los códigos asignados a un conjunto de símbolos en función de sus frecuencias o probabilidades de aparición. Es ampliamente usado en sistemas de compresión como ZIP, JPEG y MP3 debido a su simplicidad y eficiencia.
Pertenece a la clase de codificaciones de prefijo, lo que significa que ningún código asignado a un símbolo puede ser prefijo del código de otro símbolo. Esto garantiza la decodificación única y eficiente, ya que el código puede ser procesado símbolo por símbolo sin ambigüedad.
También te puede interesar conocer más sobre la compresión de archivos
Ejemplo
Si nos fijamos en la imagen anterior, en la que se muestra el ejemplo de la palabra ANDRES (en código ASCII), el árbol Huffman se realizaría de esta forma:
1. Calcular las frecuencias de los caracteres
Primero, contamos las veces que aparece cada carácter en la palabra «ANDRES»:
| Carácter | Frecuencia (veces que se repite) |
|---|---|
| A | 1 |
| N | 1 |
| D | 1 |
| R | 1 |
| E | 1 |
| S | 1 |
Dado que cada carácter aparece una vez, todas las frecuencias son iguales (1/6=0.1667). Sin embargo, los valores exactos de las frecuencias no afectan la construcción del árbol en este caso porque todas son iguales.
2. Construir el árbol de Huffman
Creamos un árbol binario combinando los nodos de menor frecuencia hasta formar un único árbol.
- Paso inicial: representamos cada carácter como un nodo con su frecuencia:
A(1), N(1), D(1), R(1), E(1), S(1)
- Primera combinación: tomamos los dos nodos de menor frecuencia (en este caso, cualquier par porque todas son iguales). Supongamos que combinamos AA y NN:
(AN:2), D(1), R(1), E(1), S(1)
- Segunda combinación: combinamos otros dos nodos, por ejemplo, DD y RR:
(AN:2), (DR:2), E(1), S(1)
- Tercera combinación: después se combina EE y SS:
(AN:2), (DR:2), (ES:2)
- Cuarta combinación: es el momento de combinar dos nodos de frecuencia 22, por ejemplo, ANAN y DRDR:
((AN)(DR):4), (ES:2)
- Última combinación: ahora combinamos los nodos restantes:
(((AN)(DR))(ES):6)
El árbol final se ve así para esta palabra «ANDRES» que hemos usado como ejemplo:
Si asignamos los códigos binarios a cada carácter, el árbol quedaría de la siguiente manera según esta asignación:
| Carácter | Código |
|---|---|
| A | 000 |
| N | 001 |
| D | 010 |
| R | 011 |
| E | 100 |
| S | 101 |
En definitiva, la palabra «ANDRES» se representa como:
000 001 010 011 100 101
Como puedes ver, ANDRES son 6 caracteres en ASCII, y cada carácter ASCII se representa con 8 bits. Por tanto, esta palabra ocuparía en memoria 48 bits. En cambio, tras la codificación en Huffman, es decir, tras la compresión, se usan solo 18 bits, ya que los 6 caracteres han pasado a usar solo 3 bits.
Esto significa que ha pasado a comprimirse en torno al 62.5% menos, es decir, se ha quedado en un 37.5% de la longitud inicial, si hacemos una simple regla de tres (Si 48 son 100, 18 serán x –> 18×100/48=37.5) se puede ver esto…
En este caso ha dado una buena compresión, sin embargo, hay que decir que el código Huffman tiene sus ventajas y desventajas, como es lógico. Entre las ventajas tenemos que es fácil de implementar y versátil, además de no tener pérdida. En cambio, también tiene algunos problemas, como su dependencia de las frecuencias de repetición, y eso hace que mientras más uniformes sean las frecuencias, menos se comprima el resultado.
Aplicaciones del código Huffman
En cuanto a las posibles aplicaciones del Código Huffman, ya hemos adelantado algunas, pero hay más:
- Compresión de archivos: herramientas como ZIP y RAR usan Huffman como una etapa de compresión. Es fundamental en el estándar DEFLATE, que combina Huffman con el algoritmo LZ77.
- Codificación de imágenes y vídeo: también se utiliza en estándares como JPEG y MPEG para comprimir datos visuales y de audio. También se puede usar para comprimir texto en los procesadores de texto, como has podido ver con el ejemplo que puse de ANDRES…
- Protocolos de comunicación: en sistemas de transmisión como HTTP/2, Huffman optimiza la representación de encabezados.
DEFLATE fue desarrollado por Phil Katz en 1993 y se convirtió en la base del formato ZIP y otros estándares de compresión, como gzip y PNG. La idea era conseguir un buen equilibrio entre la velocidad de compresión y descompresión de datos.
Variaciones del Código Huffman
Aunque el algoritmo original es robusto, se han desarrollado variaciones para adaptarlo a diferentes requisitos. Entre las variantes más conocidas se puede destacar:
- Codificación adaptativa de Huffman: diseñada para flujos de datos dinámicos o desconocidos, ajusta los códigos en tiempo real a medida que procesa los datos. Se utiliza en aplicaciones de transmisión en tiempo real y sistemas de compresión incremental.
- Huffman modificado: introduce restricciones en la longitud máxima de los códigos, usado en sistemas con hardware limitado, como compresión de audio en MP3.
- Huffman para fuentes no memorables: para datos que tienen dependencias entre símbolos, combinando Huffman con técnicas como cadenas de Markov.
- Huffman Canónico: simplifica el almacenamiento de códigos, representando el árbol de Huffman de manera más compacta. Es común en implementaciones prácticas, como DEFLATE.
- Huffman en bloques: en este caso divide los datos en bloques y genera códigos Huffman específicos para cada bloque, mejorando la eficiencia en fuentes heterogéneas.
Deja tus comentarios con las dudas o cualquier otra cosa que te apetezca compartir sobre el tema…
