Cómo funciona la compresión de archivos

Publicidad

Si el programa de compresión escaneara la frase de Kennedy, la primera redundancia con la que se encontraría sería de sólo un par de letras. En «ask not what your», hay un patrón repetido de la letra «t» seguida de un espacio — en «not» y «what». Si el programa de compresión escribiera esto en el diccionario, podría escribir un «1» cada vez que una «t» fuera seguida de un espacio. Pero en esta frase corta, este patrón no se produce lo suficiente como para que sea una entrada que merezca la pena, por lo que el programa acabaría por sobrescribirlo.

La siguiente cosa que el programa podría notar es «ou», que aparece tanto en «tu» como en «país». Si se tratara de un documento más largo, escribir este patrón en el diccionario podría ahorrar mucho espacio: «ou» es una combinación bastante común en el idioma inglés. Pero a medida que el programa de compresión trabajara con esta frase, descubriría rápidamente una mejor opción para una entrada en el diccionario: No sólo se repite «ou», sino que también se repiten las palabras «your» y «country», y de hecho se repiten juntas, como la frase «your country». En este caso, el programa sobrescribiría la entrada del diccionario para «ou» con la entrada para «tu país».

La frase «puede hacer por» también se repite, una vez seguida de «tu» y otra vez seguida de «tú», lo que nos da un patrón repetido de «puede hacer por ti». Esto nos permite escribir 15 caracteres (incluyendo espacios) con un valor numérico, mientras que «su país» sólo nos permite escribir 13 caracteres (con espacios) con un valor numérico, por lo que el programa sobrescribiría la entrada «su país» como sólo «r país», y luego escribiría una entrada separada para «puede hacer por usted». El programa procede de esta manera, recogiendo todos los trozos de información repetidos y luego calculando qué patrones debe escribir en el diccionario. Esta capacidad de reescribir el diccionario es la parte «adaptativa» del algoritmo basado en el diccionario adaptativo LZ. La forma en que un programa hace esto es bastante complicada, como se puede ver en las discusiones en Data-Compression.com.

Independientemente del método específico que utilice, este sistema de búsqueda en profundidad le permite comprimir el archivo de forma mucho más eficiente de lo que podría hacerlo simplemente eligiendo palabras. Utilizando los patrones que hemos escogido arriba, y añadiendo «__» para los espacios, llegamos a este diccionario más grande:

Y esta frase más pequeña: «1not__2345__–__12354»

La frase ocupa ahora 18 unidades de memoria, y nuestro diccionario ocupa 41 unidades. ¡Así que hemos comprimido el tamaño total del archivo de 79 unidades a 59 unidades! Esta es sólo una forma de comprimir la frase, y no necesariamente la más eficiente. (¡A ver si encuentras una forma mejor!)

¿Qué tan bueno es este sistema? El ratio de reducción de archivos depende de una serie de factores, como el tipo de archivo, el tamaño del mismo y el esquema de compresión.

En la mayoría de los idiomas del mundo, ciertas letras y palabras suelen aparecer juntas en el mismo patrón. Debido a este alto índice de redundancia, los archivos de texto se comprimen muy bien. Una reducción del 50 por ciento o más es típica para un archivo de texto de buen tamaño. La mayoría de los lenguajes de programación también son muy redundantes porque utilizan una colección relativamente pequeña de comandos, que con frecuencia van juntos en un patrón establecido. Los archivos que incluyen mucha información única, como los gráficos o los archivos MP3, no pueden comprimirse mucho con este sistema porque no repiten muchos patrones (más sobre esto en la siguiente sección).

Si un archivo tiene muchos patrones repetidos, la tasa de reducción suele aumentar con el tamaño del archivo. Se puede ver esto simplemente mirando nuestro ejemplo – si tuviéramos más del discurso de Kennedy, podríamos referirnos a los patrones en nuestro diccionario más a menudo, y así obtener más del espacio de archivo de cada entrada. Además, podrían surgir patrones más dominantes en el trabajo más largo, lo que nos permitiría crear un diccionario más eficiente.

Esta eficiencia también depende del algoritmo específico utilizado por el programa de compresión. Algunos programas son especialmente adecuados para captar patrones en determinados tipos de archivos, por lo que pueden comprimirlos de forma más sucinta. Otros tienen diccionarios dentro de diccionarios, que pueden comprimir eficazmente los archivos más grandes pero no los más pequeños. Aunque todos los programas de compresión de este tipo funcionan con la misma idea básica, en realidad hay una gran variación en la forma de ejecución. Los programadores siempre intentan construir un sistema mejor.