Huffman Coding
La codificación Huffman, publicada por David Huffman en 1952, es un algoritmo de construcción de códigos de prefijo que asigna códigos cortos a los símbolos frecuentes y largos a los raros, alcanzando el límite inferior de entropía.
Propósito
Construye códigos de prefijo óptimos para compresión sin pérdida cuando se conocen las frecuencias de símbolos, y es el back end de DEFLATE, JPEG y MP3.
Mecanismo
Se cuentan las frecuencias de símbolos y se construye un árbol Huffman: se fusionan repetidamente los dos nodos de menor frecuencia en un nuevo padre hasta que solo queda la raíz; el camino raíz-a-hoja (izquierda 0, derecha 1) da el código de cada símbolo. Los símbolos frecuentes obtienen caminos cortos.
Casos de uso
- Etapa de codificación entrópica en DEFLATE
- Etapa de codificación entrópica en JPEG/MP3
- Back end de compresión de texto