Cómo funciona la compresión de datos sin pérdidas | Revista Cuanta

Con más de 9 mil millones de gigabytes de información viajando por Internet todos los días, los investigadores buscan constantemente nuevas formas de comprimir los datos en paquetes más pequeños. Las técnicas de vanguardia se enfocan en enfoques con pérdidas, que logran la compresión al “perder” intencionalmente información de una transmisión. Google, por ejemplo, reveló recientemente una estrategia con pérdida en la que la computadora que envía elimina los detalles de una imagen y la computadora que recibe usa inteligencia artificial para adivinar las partes que faltan. Incluso Netflix utiliza un enfoque con pérdidas, degradando la calidad del video cada vez que la empresa detecta que un usuario está mirando en un dispositivo de baja resolución.

Por el contrario, actualmente se está investigando muy poco sobre las estrategias sin pérdidas, en las que las transmisiones se hacen más pequeñas, pero no se sacrifica ninguna sustancia. ¿La razón? Los enfoques sin pérdidas ya son notablemente eficientes. Impulsan todo, desde el estándar de imagen JPEG hasta la omnipresente utilidad de software PKZip. Y todo se debe a un estudiante de posgrado que simplemente buscaba una forma de salir de un difícil examen final.

Hace setenta años, un profesor del Instituto de Tecnología de Massachusetts llamado Robert Fano ofreció a los estudiantes de su clase de teoría de la información una opción: tomar un examen final tradicional o mejorar un algoritmo líder para la compresión de datos. Fano puede o no haber informado a sus alumnos que él era el autor de ese algoritmo existente, o que había estado buscando una mejora durante años. Lo que sí sabemos es que Fano planteó a sus alumnos el siguiente reto.

Considere un mensaje compuesto de letras, números y puntuación. Una forma sencilla de codificar un mensaje de este tipo sería asignar a cada carácter un número binario único. Por ejemplo, una computadora podría representar la letra A como 01000001 y un signo de exclamación como 00100001. Esto da como resultado códigos que son fáciles de analizar (cada ocho dígitos, o bits, corresponden a un carácter único) pero terriblemente ineficientes, porque el mismo número de dígitos binarios se utiliza para entradas comunes y no comunes. Un mejor enfoque sería algo así como el código Morse, donde la letra E frecuente está representada por un solo punto, mientras que la Q menos común requiere el guión-guión-punto-guión más largo y laborioso.

Sin embargo, el código Morse también es ineficiente. Claro, algunos códigos son cortos y otros son largos. Pero debido a que las longitudes de los códigos varían, los mensajes en código Morse no se pueden entender a menos que incluyan breves períodos de silencio entre la transmisión de cada carácter. De hecho, sin esas costosas pausas, los destinatarios no tendrían forma de distinguir el mensaje Morse guión punto-guión-punto punto-punto guión punto ("trivial") del guión punto-guión-punto punto-punto-guión punto ("verdadero" ).

Fano había resuelto esta parte del problema. Se dio cuenta de que podía usar códigos de diferentes longitudes sin necesidad de costosos espacios, siempre y cuando nunca usara el mismo patrón de dígitos como código completo y como comienzo de otro código. Por ejemplo, si la letra S era tan común en un mensaje en particular que Fano le asignó el código extremadamente corto 01, entonces ninguna otra letra en ese mensaje se codificaría con algo que comenzara con 01; códigos como 010, 011 o 0101 estarían prohibidos. Como resultado, el mensaje codificado podía leerse de izquierda a derecha, sin ninguna ambigüedad. Por ejemplo, con la letra S asignada 01, la letra A asignada 000, la letra M asignada 001 y la letra L asignada 1, de repente el mensaje 0100100011 se puede traducir inmediatamente a la palabra "pequeño" aunque L esté representado por uno dígito, S por dos dígitos, y las otras letras por tres cada uno.

Para determinar realmente los códigos, Fano construyó árboles binarios, colocando cada letra necesaria al final de una rama visual. El código de cada letra se definió luego por la ruta de arriba a abajo. Si el camino se bifurcaba a la izquierda, Fano añadía un 0; las ramas derechas obtuvieron un 1. La estructura de árbol facilitó a Fano evitar esas superposiciones indeseables: una vez que Fano colocó una letra en el árbol, esa rama terminaría, lo que significa que ningún código futuro podría comenzar de la misma manera.

Para decidir qué letras irían a dónde, Fano podría haber probado exhaustivamente todos los patrones posibles para obtener la máxima eficiencia, pero eso no habría sido práctico. Entonces, en su lugar, desarrolló una aproximación: para cada mensaje, organizaba las letras relevantes por frecuencia y luego asignaba letras a las ramas para que las letras de la izquierda en cualquier par de ramas dado se usaran en el mensaje aproximadamente la misma cantidad de veces que el letras a la derecha. De esta forma, los caracteres de uso frecuente acabarían en ramas más cortas y menos densas. Un pequeño número de letras de alta frecuencia siempre equilibraría un número mayor de letras de baja frecuencia.

El resultado fue una compresión notablemente eficaz. Pero era sólo una aproximación; tenía que existir una mejor estrategia de compresión. Entonces Fano desafió a sus alumnos a encontrarlo.

Fano había construido sus árboles de arriba hacia abajo, manteniendo la mayor simetría posible entre las ramas emparejadas. Su estudiante David Huffman le dio la vuelta al proceso, construyendo los mismos tipos de árboles pero de abajo hacia arriba. La idea de Huffman fue que, pase lo que pase, en un código eficiente los dos caracteres menos comunes deberían tener los dos códigos más largos. Así que Huffman identificó los dos caracteres menos comunes, los agrupó como un par ramificado y luego repitió el proceso, esta vez buscando las dos entradas menos comunes entre los caracteres restantes y el par que acababa de construir.

Considere un mensaje donde el enfoque de Fano falla. En “schoolroom”, O aparece cuatro veces y S/C/H/L/R/M cada uno aparece una vez. El enfoque de equilibrio de Fano comienza asignando la O y otra letra a la rama izquierda, con los cinco usos totales de esas letras equilibrando las cinco apariciones de las letras restantes. El mensaje resultante requiere 27 bits.

Huffman, por el contrario, comienza con dos de las letras poco comunes, digamos, R y M, y las agrupa, tratando el par como una sola letra.

Su tabla de frecuencias actualizada le ofrece cuatro opciones: la O que aparece cuatro veces, el nuevo nodo RM combinado que se usa funcionalmente dos veces y las letras individuales S, C, H y L. Huffman nuevamente elige las dos opciones menos comunes, haciendo coincidir (decir) H con L.

El gráfico se actualiza de nuevo: O todavía tiene un peso de 4, RM y HL ahora tienen cada uno un peso de 2, y las letras S y C están solas. Huffman continúa a partir de ahí, en cada paso agrupa las dos opciones menos frecuentes y luego actualiza tanto el árbol como el gráfico de frecuencia.

En última instancia, "aula de escuela" se convierte en 11101111110000110110000101, eliminando un poco el enfoque de arriba hacia abajo de Fano.

Un bit puede no parecer mucho, pero incluso los pequeños ahorros crecen enormemente cuando se escalan en miles de millones de gigabytes.

De hecho, el enfoque de Huffman ha resultado ser tan poderoso que, hoy en día, casi todas las estrategias de compresión sin pérdidas utilizan la idea de Huffman en su totalidad o en parte. ¿Necesita PKZip para comprimir un documento de Word? El primer paso involucra otra estrategia inteligente para identificar la repetición y, por lo tanto, comprimir el tamaño del mensaje, pero el segundo paso es tomar el mensaje comprimido resultante y ejecutarlo a través del proceso de Huffman. ¿Almacenar una imagen como JPEG? Su computadora primero traduce la imagen a una representación basada en texto y luego, nuevamente, usa la codificación Huffman para comprimir ese texto.

No está mal para un proyecto originalmente motivado por el deseo de un estudiante de posgrado de saltarse un examen final.