> huffman | codificación | óptima <
// Codificación Huffman - algoritmo de compresión óptima sin prefijos
>> características
Códigos óptimos
Genera la menor longitud media de código para las frecuencias dadas.
Sin prefijos
Ningún código es prefijo de otro, lo que permite una decodificación inequívoca.
Basado en frecuencias
Los caracteres más frecuentes reciben automáticamente códigos más cortos.
>> información técnica
Cómo funciona la codificación Huffman
La codificación Huffman construye un árbol binario de abajo hacia arriba. A partir de las frecuencias de los caracteres, combina repetidamente los dos nodos de menor frecuencia en un nodo padre hasta que solo queda la raíz. Las ramas izquierdas representan '0' y las derechas '1'. Los caracteres más frecuentes obtienen códigos más cortos, logrando una compresión óptima para la distribución dada.
Ejemplo de codificación Huffman
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Por qué usar codificación Huffman
- Relación de compresión casi óptima
- Implementación sencilla
- Base de ZIP/JPEG
- Sin pérdida de datos
- Eficiencia demostrada en la práctica
>> preguntas frecuentes
¿Qué es la codificación Huffman?
La codificación Huffman es un algoritmo de compresión óptimo y sin prefijos desarrollado por David A. Huffman en 1952. Asigna códigos de longitud variable a los caracteres según su frecuencia; los más frecuentes reciben códigos más cortos y se consigue la mínima longitud media posible.
¿Por qué se considera sin prefijos?
Un código es sin prefijos cuando ningún código es prefijo de otro. Por ejemplo, si 'A' se codifica como '01', ningún otro carácter puede tener un código que empiece por '01'. Esta propiedad garantiza una decodificación inequívoca: siempre puedes saber dónde termina un código y empieza el siguiente sin separadores adicionales.
¿Qué tan eficiente es la codificación Huffman?
La codificación Huffman logra la compresión óptima para una distribución de frecuencias dada y suele quedar a menos de 1 bit del límite teórico de entropía. Para texto en inglés suele alcanzar un 60–70 % de compresión y resulta especialmente eficaz cuando las frecuencias de los caracteres son muy desiguales.
¿Dónde se utiliza la codificación Huffman?
La codificación Huffman se utiliza en la compresión de imágenes JPEG, en archivos ZIP (junto con LZ77 en DEFLATE), en audio MP3 y en muchos otros formatos. A menudo se combina con otros algoritmos: por ejemplo, JPEG usa Huffman después de DCT y la cuantización, mientras que ZIP lo usa después de LZ77.