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
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
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.
A(1), N(1), D(1), R(1), E(1), S(1)
(AN:2), D(1), R(1), E(1), S(1)
(AN:2), (DR:2), E(1), S(1)
(AN:2), (DR:2), (ES:2)
((AN)(DR):4), (ES:2)
(((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.
En cuanto a las posibles aplicaciones del Código Huffman, ya hemos adelantado algunas, pero hay más:
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.
Aunque el algoritmo original es robusto, se han desarrollado variaciones para adaptarlo a diferentes requisitos. Entre las variantes más conocidas se puede destacar:
Deja tus comentarios con las dudas o cualquier otra cosa que te apetezca compartir sobre el tema…
Elegir entre los AirPods Pro 2 y los AirPods 4 puede ser un desafío. De…
Sharkoon VK2 RGB es el tercer chasis lanzado recientemente por la marca, que se une…
Los controladores Game Ready 566.45 llegaron para solucionar problemas con el “micro-stuttering” y la estabilidad…