Compresión de Datos: De los Códigos Huffman al Límite de Shannon

La codificación Huffman asigna códigos binarios más cortos a los símbolos más frecuentes y códigos más largos a los símbolos raros. El algoritmo construye un árbol binario de abajo hacia arriba: fusiona repetidamente los dos nodos de menor frecuencia hasta que queda un solo árbol. Los símbolos en hojas poco profundas reciben códigos cortos; las hojas profundas reciben códigos largos. El resultado es un código libre de prefijos —ninguna palabra código es prefijo de otra— que minimiza la longitud esperada del código para la distribución de frecuencias dada.

El teorema de codificación de fuente de Shannon (teorema de codificación sin ruido) establece que una fuente con entropía H bits por símbolo no puede comprimirse sin pérdida por debajo de H bits por símbolo en promedio. Recíprocamente, puede comprimirse a una tasa arbitrariamente cercana a H usando códigos de bloques suficientemente largos. Esto establece la entropía como el límite fundamental de la compresión sin pérdida.

Los datos verdaderamente aleatorios tienen entropía máxima: cada símbolo es igualmente probable y no hay patrones. Como la entropía es igual a log₂(N) para N símbolos igualmente probables, el tamaño comprimido iguala al original. Por el principio del palomar, cualquier esquema de compresión que acorte algunas entradas debe alargar otras. Para datos aleatorios uniformes, ninguna entrada es más probable que otra, por lo que no es posible una compresión sistemática.

La compresión sin pérdida (Huffman, LZ77, DEFLATE) preserva cada bit de los datos originales: la salida descomprimida es idéntica a la entrada. La compresión con pérdida (JPEG, MP3, H.264) descarta información considerada perceptualmente poco importante, logrando razones de compresión mucho mayores a costa de la fidelidad. El teorema de codificación de fuente de Shannon gobierna la compresión sin pérdida; la teoría de tasa-distorsión gobierna la compresión con pérdida.