Compresión de bits sin pérdida

Las computadoras representan todos los datos en binario, de manera que todos los tipos de archivos, desde texto hasta imágenes y videos, son en última instancia secuencias de bits. Independientemente de si los bits representan un documento o un GIF, las computadoras pueden usar una técnica de compresión de bits llamada codificación de Huffman.

Veamos cómo funciona con un ejemplo textual simple. Este lenguaje de ejemplo utiliza solo 4 caracteres diferentes, y aún así es increíblemente importante para nosotros: es el lenguaje utilizado para representar ADN y se compone de secuencias de cuatro caracteres A, C, G y T.

Por ejemplo, los 4.6 millones de caracteres que representan una secuencia de ADN de E.coli empiezan con:

Como necesitamos representar cuatro caracteres, una computadora normalmente representa cada carácter con 2 bits, así:

Los 13 caracteres anteriores pueden escribirse con 26 bits como sigue. Observa que no necesitamos huecos entre los códigos de bits.

Pero podemos hacerlo mejor. En el ejemplo de texto de muestra anterior, la letra "t" es más común que las otras letras ("t" aparece 7 veces, "c" 3 veces, "a" dos veces, y "g" una vez). Si asignamos un código más corto a "t", entonces usaremos menos espacio el 54% de las veces (7 de 13 caracteres). Por ejemplo, podríamos usar los códigos:

Entonces nuestros 13 caracteres se codifican así:

Esos son solo 22 bits, cuatro menos bits que en nuestra codificación original. Esto puede no parecer mucho, pero ¡imagina si usamos una optimización como esta para los 4.6 millones de caracteres del ADN completo!

Puede ser que estés rascándote la cabeza con los nuevos códigos binarios y las diferentes longitudes que usamos. ¿Es posible decodificarlos de manera confiable? Sí, con el conjunto correcto de códigos.

Esa es la belleza de la codificación de Huffman: el algoritmo nos da una manera de crear un conjunto de códigos binarios, para una secuencia determinada, que garantice que los datos puedan reconstruirse inequívoca y confiablemente.

Muchos formatos de archivos utilizan alguna clase de codificación de Huffman para reducir el tamaño del archivo. Las máquinas de FAX también la utilizan después de RLE en las secuencias de blanco y de negro. Las imágenes PNG se comprimen con LZ77, un algoritmo similar a la técnica de compresión de texto que aprendimos, en combinación con codificación de Huffman de los resultados.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el area de preguntas abajo!