Muchas veces al descargar cosas de Internet, nos encontramos con archivos .zip y .rar. Estos formatos de compresión son una herramienta bastante útil, sobre todo para aquellos que navegamos bajando cosas por aquí y por allá. Principalmente debido a que nos ayudan a disminuir los tiempos de descarga y además nos ayudan a ocupar menos espacio en nuestros discos duros.
PUBLICIDAD
La idea básicamente es comprimir un archivo con un programa (Winzip o Winrar, que son los más comunes) para así disminuir su tamaño, y luego cuando queremos acceder a la información utilizamos el mismo programa para volver al tamaño original.
A primera vista este proceso parece bastante misterioso. ¿Cómo uno puede reducir una cantidad de bits y bites, y luego agregarlos de vuelta como si nada? Es por esto que en este capítulo de CHWonders veremos el concepto básico detrás de la compresión de los archivos, para que así puedan entender de qué trata.
Concepto
Por lo general, la mayoría de los archivos de nuestro computador son redundantes, ¿Qué quiere decir esto?, pues contienen paquetes en los cuales la información se repite una y otra vez en otro paquete. Es por esto que los programas de compresión de archivos, simplemente se deshacen de esta redundancia, y lo único que hacen es guardar una sola copia de la información, y luego dejar registrada la referencia de las ubicaciones en donde ésta información aparece nuevamente dentro del archivo.
Para dar un ejemplo utilizare un conocido trabalenguas:
“Pablito clavo un clavito – que clavito clavo Pablito”
Dentro de esta frase, hay 8 palabras, compuestas de 43 letras, 8 espacios y 1 guion. Si tomamos a cada letra, espacio y símbolo como unidad de memoria, entonces tendríamos un total de 52 unidades. Para disminuir el tamaño del archivo, necesitamos ver las redundancias presentes.
Entonces nos damos cuenta que:
“Pablito” aparece dos veces
“clavo” aparece dos veces
“un” aparece una vez
“clavito” aparece dos veces
“que” aparece una vez
Por lo cual 3 de las 8 palabras que hay en la frase son en verdad redundantes, y con tan solo 5 palabras podemos construir la totalidad de la frase. Solo basta indicar la ubicación en la cual estas palabras van para poder construir la frase. A continuación veremos cómo los sistemas de compresión trabajan con estas redundancias.
Redundancia y Algoritmos
La mayoría de los programas de compresión que utilizamos usan una variación del algoritmo LZ adaptivo basado en diccionario para comprimir archivos. “LZ” se refiere a Lempel y Ziv, los creadores de este algoritmo para catalogar piezas de información.
Abraham Lempel, contribuyo a la creación del algoritmo del formato .gif
El sistema para ordenar las variantes por diccionario puede variar, pero puede ser tan simple como usar una lista enumerada. Entonces cuando utilizamos el trabalenguas y ordenamos numéricamente las redundancias obtenemos lo siguiente:
1.- Pablito
2.- clavo
3.- clavito
Y al leerlo lo haríamos así:
1 2 un 3 – que 3 2 1
Entonces con tan solo el orden y 5 palabras, obtenemos una frase compuesta de 8 palabras. Esto es lo que hacen básicamente los programas al descomprimir los archivos que tenemos en nuestro computador, leer la información redundante y la ubicación de estos, para reintegrarlos al archivo original.
Por lo tanto, de las 52 unidades de la frase original, pasamos a tan solo 39 unidades (que es la suma de la cantidad de caracteres de nuestras palabras redundantes, más la cantidad de caracteres en nuestra frase codificada numéricamente), lo cual equivale a un 25% menos de la información original que teníamos.
Si este mismo proceso lo aplicáramos a un largo archivo de texto, la compresión seria cada vez mayor aun. Pero como nuestra computadora no ve los archivos que tenemos como palabras, lo que hace es buscar patrones dentro de los archivos, y será lo que explicare a continuación.
La compresión de datos en imágenes
En búsqueda de patrones
Debido a que el computador no es capaz de identificar inmediatamente un patrón por completo, lo que hace es ir paso por paso descubriendo las redundancias presentes.
Si un programa de compresión leyera nuestro texto, la primera redundancia que encontraría seria de tan solo unas letras. En “Pablito clavo un clavito” hay un patrón que se repite de la letra “o” seguida de un espacio. Si el programa agregara este patrón al diccionario, agregaría un 1 por cada “o” que existiera antes de un espacio, pero debido a que dentro de esta corta frase, el patrón no ocurre la cantidad de veces suficiente, no se justifica este diccionario.
Por lo cual luego el programa pasaría al siguiente patrón, el cual es “ito”, que aparece en “Pablito” y en “clavito”, logrando de esta manera omitir 3 unidades (ito) en vez de los 2 de la “o” y el espacio.
Pero luego el programa analizaría en busca de otro patrón existente y se encontraría con “clavito” repetido dos veces, si es que fuese leído secuencialmente, y así encontraría además, “clavo” y “Pablito”. Pero eso no es todo, luego el computador vera que las palabras “clavito” y “clavo” en cada parte que se repiten van acompañados de un espacio, por lo cual finalmente el diccionario lo almacenaría así, si es que consideramos al _ como el espacio:
1.- clavito_
2.- clavo_
3.- Pablito
Dándonos finalmente esta sentencia:
3_2un1-_que_123
Si el computador después de analizar no encontrara más patrones y se quedara con este, la cantidad de unidades que obtenemos entre la sentencia y el diccionario es de tan solo 36 unidades (3 menos que la anterior que utilizamos). Aun así esta es una de las tantas maneras que existen de comprimir la frase, y no necesariamente la más eficiente (a ver si a ustedes se les ocurre una mejor).
Conclusión
En la mayoría de los lenguajes del mundo, ciertas letras y palabras aparecen juntas dentro de un mismo patrón. Y debido a esta alta cantidad de redundancia, los archivos de textos se comprimen muy bien, logrando una reducción de incluso un 50% del tamaño original del texto. Muchos lenguajes de programación también son redundantes debido a que los archivos creados, utilizan comandos que se van repitiendo a través del programa, generando de esta manera patrones.
Pero archivos que incluyen mucha información única, como los gráficos o archivos MP3, no pueden comprimirse mucho con este sistema debido a que dentro de estos archivos no se repiten muchos patrones.
Por lo tanto la capacidad de compresión de un archivo, depende de la cantidad de información existente, las redundancias que haya y de los patrones que se puedan ir obteniendo a través del análisis. Y principalmente dependen del algoritmo utilizado por el programa. Algunos programas están hechos para elegir una serie de patrones de ciertos tipos de archivos, por lo cual comprimen esos archivos de mejor manera. En cambio otros trabajan con diccionarios por lo cual comprimirán una mayor proporción si el archivo es grande, y comprimirán poco si el archivo es chico.
Cada vez los programadores van descubriendo nuevos algoritmos, y gracias a la inteligencia artificial es que veremos a futuro programas más eficientes al momento de comprimir nuestros archivos. Si les interesa el tema, los dejo con un video muy educativo desde el punto de vista de la programación.