La compresión sin pérdida permite reducir tamaños sin eliminar información: al descomprimir, el archivo es idéntico. Con un árbol binario que asigna rutas de bits más cortas a los símbolos más frecuentes, se logra un ahorro notable. Ejemplo real: de 22 bytes (176 bits) a 88 bits (11 bytes) en el contenido, más metadatos del árbol.
¿Qué es la compresión sin pérdida y por qué importa?
La idea central es codificar el contenido para que ocupe menos bits sin alterar su significado. Así operan PNG, FLAC y .zip. La clave es aprovechar repeticiones y frecuencias: lo que aparece más veces debe costar menos bits.
¿Qué ejemplos confirman la compresión sin pérdida?
- Imágenes con PNG: no pierden calidad al reabrirlas.
- Audio con FLAC: conserva cada muestra original.
- Archivos .zip: reagrupan datos repetidos con rutas de bits.
¿Qué datos básicos debes dominar?
- Un byte son 8 bits. Una letra típica ocupa un byte; con UTF-16, puede ser 16 bits.
- Mensaje base: «Amo leer Panamá Papers». Tamaño original: 22 bytes = 176 bits.
- Objetivo: reducir bits mediante rutas en un árbol binario.
¿Cómo se construye el árbol binario para asignar bits por frecuencia?
Primero se cuentan frecuencias símbolo por símbolo, como lo haría un programa. No “a ojo”. Para ordenar por frecuencia se pueden usar algoritmos de ordenamiento como quick sort. Luego se construye el árbol binario: izquierda es 0, derecha es 1; moverse por el árbol son ceros y llegar a una letra se marca con un uno.
¿Cómo se calculan las frecuencias y pesos?
- Se recorre el texto y se cuenta cada símbolo.
- Ejemplo de conteo: la a aparece cinco veces; la m, dos veces.
- El peso es la cantidad de apariciones: más peso, ruta más corta.
¿Cómo se recorren las rutas de bits en el árbol?
- Regla de movimiento: 0 a la izquierda, 1 a la derecha.
- Convención de fin: “cuando llego al 1, ya representé una letra” y regreso a la raíz para la siguiente.
- Ejemplos de codificación del caso:
- A = 1.
- espacio = 01.
- E = 001.
- M = 00001.
- O = 0000001.
- L = 00000001.
¿Cómo se codifica el mensaje y qué ahorro se obtiene?
Se concatena la ruta de cada letra. Al decodificar, cada 1 indica “fin de símbolo” y se vuelve a la raíz. Así, «Amo leer Panamá Papers» se interpreta correctamente con menos bits, porque los símbolos frecuentes usan rutas cortas y los menos frecuentes, rutas largas.
¿Qué tamaño final y metadatos se guardan?
- Contenido comprimido: 88 bits = 11 bytes.
- Hay que guardar el árbol binario: para cada símbolo, su byte y su ruta (que “para” en 1).
- Sobrecarga estimada del ejemplo: 10 bytes.
- Total aproximado: 21 bytes frente a 22 originales.
- Nota práctica: en .zip, archivos pequeños cambian poco; en archivos grandes el ahorro crece porque muchos bytes se repiten.
¿Dónde más se aplica esta idea de repetición?
- Texto: letras y espacios con frecuencias distintas.
- Imágenes: píxeles con colores que se repiten más que otros.
- Audio: segmentos de la onda con patrones recurrentes.
- Existen algoritmos especializados para ciertos medios, como H264 o JPG.
¿Qué habilidades técnicas necesitas?
- Entender bits y bytes; operaciones de corrimiento de bits para leer bit a bit.
- Manejar una tabla de frecuencias y un árbol binario con rutas 0/1.
- Conocer lo básico de matemática binaria.
- Implementar la codificación/decodificación en cualquier lenguaje.
¿Te gustaría comentar qué archivo tuyo ganó más ahorro con .zip o qué reto tuviste al trabajar con bits y rutas 0/1?
