Cómo funcionan los archivos comprimidos
Compresión con pérdida y compresión sin pérdida. Si descarga muchos programas y archivos de Internet, es posible que encuentre muchos archivos ZIP. Este mecanismo de compresión es un invento conveniente, especialmente para los usuarios de Internet, porque reduce la cantidad total de bits y bytes en un archivo, lo que permite que el archivo se transfiera más rápido a través de conexiones a Internet más lentas, además de reducir el espacio en disco del archivo. Después de descargar el archivo, su computadora puede usar un programa como WinZip o Stuffit para expandir el archivo y restaurarlo a su tamaño original. Si todo va bien, el archivo expandido será exactamente igual que el archivo original antes de la compresión.
Al principio suena misterioso: ¿cómo se reduce el número de bits y bytes y se restauran intactos? Una vez que todo salga a la luz, descubrirá que la idea básica detrás de este proceso es bastante simple y directa. En este artículo, analizaremos este método para reducir significativamente el tamaño del archivo mediante una simple compresión.
La mayoría de los tipos de archivos informáticos contienen bastante redundancia: enumeran la misma información una y otra vez. Los programas de compresión de archivos están diseñados para eliminar esta redundancia. En lugar de enumerar una información repetidamente, un programa de compresión de archivos enumera la información solo una vez y luego vuelve a hacer referencia a ella cuando aparece en el programa original.
Tomemos como ejemplo un tipo de información familiar: las palabras.
John F. Kennedy dijo una vez las siguientes palabras famosas en su discurso inaugural de 1961:
No preguntes qué puede hacer tu país por ti; pregunta qué puedes hacer tú por tu país. (No preguntes qué puede hacer el país por ti, sino qué puedes hacer tú por el país).
Este pasaje tiene 17 palabras, incluidas 61 letras, 16 espacios, 1 guión y 1 punto. Si cada letra, espacio o signo de puntuación ocupa 1 unidad de memoria, el tamaño total del archivo es 79 unidades. Para reducir el tamaño del archivo, necesitamos encontrar partes redundantes.
Nos damos cuenta inmediatamente:
Si ignoras la diferencia entre letras mayúsculas y minúsculas, casi la mitad de esta oración es redundante. Nueve palabras (pregunte, no, qué, su, país, puede, hacer, para usted) proporcionan casi todo lo que necesita para formar una oración completa. Para construir la otra mitad de la oración, solo necesitamos tomar las palabras de la primera mitad de la oración y agregarles espacios y puntuación.
La mayoría de los programas de compresión utilizan el algoritmo LZ basado en diccionario adaptativo para reducir archivos. "LZ" se refiere a los inventores de este algoritmo, Lempel y Ziv, y "diccionario" se refiere al método de clasificación de bloques de datos.
Existen muchos mecanismos para organizar un diccionario y puede ser tan simple como una lista numerada. Al examinar el famoso discurso de Kennedy, podemos seleccionar palabras repetidas y colocarlas en un índice numerado. Luego, escribimos el número directamente en lugar de escribir la palabra completa.
Entonces si nuestro diccionario es:
pregunta
cuál
tu
país
can
hacer
por
usted
Nuestra oración ahora debería verse así:
1 no 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4
Si comprendes el mecanismo, puedes reconstruirlo fácilmente usando solo este diccionario y el patrón de numeración. Produce la oración original. Esto es lo que hace el programa de descompresión de su computadora cuando expande un archivo descargado. También puedes encontrarte con archivos comprimidos que pueden descomprimirse solos. Para crear dichos archivos, los programadores deben configurar un programa de descompresión simple en el archivo comprimido. Después de la descarga, puede reconstruir automáticamente el archivo original.
Pero ¿cuánto espacio se puede ahorrar utilizando este mecanismo? "1 no 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4" es ciertamente más corto que "No preguntes qué puede hacer tu país por ti; pregunta qué puedes hacer tú por tu país", pero Cabe señalar que la cuestión es que necesitamos guardar este diccionario con el archivo.
En un esquema de compresión práctico, calcular los distintos requisitos de archivos es un proceso bastante complejo. Volvamos atrás y consideremos el ejemplo anterior. Cada carácter y espacio ocupa 1 unidad de memoria y la oración original completa ocupa 79 unidades. La oración comprimida (incluidos los espacios) ocupa 37 unidades y el diccionario (palabras y números) también ocupa 37 unidades. Dicho esto, el tamaño del archivo es 74 unidades, por lo que no reducimos mucho el tamaño del archivo.
¡Pero este es sólo el caso de una frase! Es concebible que si el resto del discurso de Kennedy fuera procesado a través de este compresor, encontraríamos estas palabras y otras repetidas muchas más veces. Además, como muestra la siguiente sección, el diccionario se puede reescribir para lograr la mayor eficiencia organizacional posible.
En el ejemplo anterior, seleccionamos todas las palabras repetidas y las pusimos en un diccionario. Para nosotros, esta es la forma más obvia de escribir un diccionario. Pero el compresor no lo cree así: no tiene ni idea de las palabras, sólo busca patrones individuales. Para reducir el tamaño del archivo tanto como sea posible, selecciona cuidadosamente el modo óptimo.
Si abordamos la frase desde esta perspectiva, terminamos con un diccionario completamente diferente.
Si un compresor escanea esta frase de Kennedy, la primera parte redundante que encuentra tiene sólo unas pocas letras. En no preguntes cuál es, aparece un patrón repetido, es decir, la letra t seguida de un espacio - en no y qué. Si el compresor escribe este patrón en un diccionario, escribirá un "1" cada vez que una "t" vaya seguida de un espacio. Pero en esta breve oración, este patrón no ocurre con suficiente frecuencia como para mantenerlo como una entrada en el diccionario, por lo que el programa finalmente lo sobrescribe.
Lo siguiente que nota el programa es ou, que aparece tanto en tu como en tu país. Si se trata de un documento más largo, escribir este patrón en el diccionario ahorrará mucho espacio; ou es una combinación de letras muy común en inglés. Pero después de que el compresor miró la oración completa, inmediatamente descubrió una mejor opción de entrada en el diccionario: no solo se repitió ou, sino que se repitieron las palabras completas your y country, y de hecho se juntaron como una frase que ocurre la duplicación de tu país. En este ejemplo, el programa sobrescribirá la entrada ou en el diccionario con la entrada de su país.
La frase puedo hacer por también se repite, una vez seguida por tu y otra vez por ti, por lo que encontramos que puedo hacer por ti también es un patrón repetido. De esta manera, podemos reemplazar 15 caracteres (incluidos espacios) con un número, mientras que su país solo nos permite reemplazar 13 caracteres (incluidos espacios) con un número, por lo que el programa sobrescribirá la entrada de su país con la entrada de r país y luego escribirá Ingrese una entrada separada que puede hacer por usted. El programa continúa trabajando de esta manera, seleccionando cualquier información duplicada y luego calculando qué patrón debe escribirse en el diccionario. La parte "adaptativa" del algoritmo LZ basado en diccionario adaptativo se refiere a la capacidad de reescribir el diccionario. El proceso mediante el cual un programa hace esto es bastante complejo.
Independientemente del método utilizado, este mecanismo de búsqueda profunda comprime archivos de manera más eficiente que simplemente seleccionar palabras.
Si usamos el patrón que extrajimos anteriormente y luego reemplazamos los espacios con "__", terminaremos con el siguiente diccionario más grande:
ask__
what__amp;
ask__
what__amp; p>
tú
r__país
__puede__hacer__por__ti
Y la frase es más corta:
"1not__2345__--__12354"
Las oraciones ahora ocupan 18 unidades de memoria y los diccionarios ocupan 41 unidades. Entonces, ¡redujimos el tamaño total del archivo de 79 unidades a 59 unidades! Esta es sólo una forma de comprimir oraciones y no es necesariamente la más eficiente. (¿Puedes encontrar una manera mejor?)
Las tasas de compresión de archivos dependen de una variedad de factores, incluido el tipo de archivo, el tamaño del archivo 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. Precisamente debido a esta alta redundancia, la tasa de compresión de archivos de texto será muy alta. Normalmente, un archivo de texto de tamaño razonable puede alcanzar una relación de compresión de 50 o superior. La mayoría de los lenguajes de programación también tienen un alto grado de redundancia porque tienen relativamente pocos comandos y los comandos suelen seguir un patrón establecido. Para archivos que contienen mucha información que no se repite (como imágenes o archivos MP3), no puede utilizar este mecanismo para lograr tasas de compresión altas porque no contienen patrones que se repitan varias veces.
Si el archivo tiene una gran cantidad de patrones repetidos, la relación de compresión generalmente aumentará a medida que aumenta el tamaño del archivo. Esto se puede ver en nuestro ejemplo: si nuestro extracto del discurso de JFK fuera más largo, vería que el patrón de nuestro diccionario aparece varias veces más, ahorrando así más espacio de archivo con cada entrada del diccionario. Además, con archivos más grandes, pueden surgir patrones con mayor generalidad, lo que permite la creación de diccionarios más eficientes.
Además, la eficiencia de la compresión de archivos también depende del algoritmo específico utilizado por el programa de compresión. Algunos programas son mejores para encontrar patrones en ciertos tipos de archivos y, por lo tanto, pueden comprimir esos tipos de archivos de manera más eficiente. Algunos otros programas de compresión utilizan diccionarios dentro de diccionarios, lo que los hace buenos para comprimir archivos grandes pero no tan eficientes para comprimir archivos más pequeños. Aunque todos los compresores de esta categoría se basan en la misma idea básica, difieren en su funcionamiento. Los desarrolladores de programas siempre están intentando crear mejores mecanismos de compresión. El tipo de compresión que analizamos anteriormente se llama compresión sin pérdidas porque el archivo que se recrea es exactamente igual al archivo original. Toda compresión sin pérdidas se basa en la idea de cambiar un archivo a un formato "más pequeño" para su transmisión o almacenamiento, y luego restaurarlo para que pueda reutilizarse después de que la otra parte lo reciba.
La compresión con pérdida es bastante diferente. Estos programas simplemente eliminan información "innecesaria", recortando el archivo para hacerlo más pequeño. Este tipo de compresión se utiliza ampliamente para reducir el tamaño del archivo de imágenes de mapa de bits, ya que las imágenes de mapa de bits suelen tener un tamaño muy grande. Para comprender cómo funciona la compresión con pérdida, veamos cómo su computadora comprime una foto escaneada.
Para este tipo de archivos, los programas de compresión sin pérdidas normalmente no ofrecen relaciones de compresión altas. Aunque la mayor parte de la imagen parece igual (por ejemplo, todo el cielo es azul), existen pequeñas diferencias entre la mayoría de los píxeles. Para reducir el tamaño de una imagen sin reducir su resolución, es necesario cambiar los valores de color de ciertos píxeles. Si la imagen contiene mucho cielo azul, el programa elegirá un color azul que pueda usarse para todos los píxeles. Luego, el programa reescribe este archivo y utiliza esta información para todos los valores de píxeles del cielo. Si el esquema de compresión se elige correctamente, no notará ningún cambio, pero el tamaño del archivo se reducirá significativamente.
Por supuesto, con la compresión con pérdida, no se puede restaurar un archivo a su apariencia original después de comprimirlo. Debe aceptar la reinterpretación del archivo original por parte del programa de compresión. Por lo tanto, esta forma de compresión no debe utilizarse si se requiere la reproducción completa del contenido original (como aplicaciones de software, bases de datos y discursos inaugurales presidenciales).