Codificación de Huffman

La codificación de Huffman es un algoritmo clásico de compresión de datos sin pérdida (lossless): reconstruye el original bit a bit, sin degradar nada. No es una técnica propia de la inteligencia artificial, sino un resultado de la teoría de la información. Lo formuló David A. Huffman en 1952, siendo estudiante en el MIT, en el artículo «A Method for the Construction of Minimum-Redundancy Codes», publicado en los Proceedings of the IRE.

Su idea es asignar códigos binarios más cortos a los símbolos más frecuentes y más largos a los raros. El resultado es un código prefijo óptimo: ningún código es prefijo de otro, de modo que la secuencia comprimida se decodifica sin ambigüedad y sin separadores.

Cómo se construye el árbol y por qué el código es prefijo

El algoritmo parte de las frecuencias de los símbolos y construye un árbol binario de abajo arriba. Cada símbolo empieza como una hoja con su frecuencia; el método combina repetidamente los dos nodos de menor frecuencia en un nodo padre cuya frecuencia es la suma de ambos, y repite hasta que queda una sola raíz. El código de cada símbolo es el camino desde la raíz hasta su hoja: 0 a la izquierda, 1 a la derecha.

Como cada símbolo vive en una hoja, y nunca en un nodo interno, ningún código puede ser el comienzo de otro: esa es precisamente la propiedad de prefijo, la que permite decodificar sin ambigüedad. Huffman demostró que, símbolo a símbolo y dada la distribución de frecuencias, este código es óptimo: ningún otro código prefijo logra una longitud media menor.

Dónde se usa de verdad

La codificación de Huffman está en formatos que usamos a diario, no en la IA. Es el corazón de la etapa de entropía de DEFLATE, el algoritmo detrás de gzip, de la biblioteca zlib y del formato de imagen PNG, todos ellos sin pérdida. También aparece en JPEG, y aquí conviene un matiz: JPEG en conjunto sí pierde información —por la transformación y la cuantización previas—, pero el paso final de Huffman que codifica esos datos es en sí mismo sin pérdida. De ahí un punto importante: Huffman nunca «comprime imágenes sin afectar su calidad» dentro de un formato con pérdida; la pérdida, cuando existe, la introducen otras etapas.

Su relación honesta con la IA

Huffman comparte raíces con la entropía de Claude Shannon, la misma noción que sustenta muchas medidas usadas en aprendizaje automático. Y aparece de forma puntual: el softmax jerárquico de word2vec (Mikolov et al., 2013) organiza el vocabulario en un árbol de Huffman para dar caminos más cortos a las palabras frecuentes y acelerar el entrenamiento. Pero eso es un uso concreto, no una regla: no es una técnica «ampliamente usada en IA». Es, ante todo, un clásico de la compresión que conviene entender por lo que es.