Cómo funcionan los archivos comprimidos
A primera vista, esto puede parecer misterioso: ¿cómo reducir el número de bits y bytes y recuperarlos intactos? Cuando todo salga a la luz, descubrirá que la idea básica detrás de este proceso es en realidad muy simple y directa. En este artículo, analizaremos este método para reducir significativamente los archivos mediante una simple compresión.
La mayoría de los tipos de archivos informáticos contienen bastante redundancia: enumeran parte de 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 hace referencia a ella nuevamente cuando aparece en el programa original.
Tomemos como ejemplo un tipo de información familiar: el texto.
John F. Kennedy dijo lo siguiente 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 tu país por ti, sino qué puedes hacer tú por tu 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 almacenamiento, el tamaño total del archivo es 79 unidades. Para reducir el tamaño del archivo, necesitamos encontrar las partes redundantes.
Inmediatamente descubrimos:
Si ignoras la diferencia entre letras mayúsculas y minúsculas, casi la mitad de esta oración es redundante. Nueve palabras (preguntar, no, qué, tu, país, puede, hacer, para, ti) proporcionan casi todo lo que necesitas para formar una oración completa. Para construir la otra mitad de la oración, solo necesitamos tomar las palabras de la primera mitad y agregarles espacios y puntuación.
La mayoría de los programas de compresión utilizan el algoritmo LZ basado en diccionario adaptativo para comprimir archivos. "LZ" se refiere a Lemper y Ziff, los inventores del algoritmo, y "diccionario" se refiere al método de clasificar fragmentos de datos.
Existen muchos mecanismos para organizar un diccionario, que pueden ser tan simples como una lista numerada. Cuando examinamos los discursos famosos de JFK, podemos seleccionar palabras repetidas y colocarlas en un índice numerado. Luego, escribimos números directamente en lugar de palabras completas.
Entonces si nuestro diccionario es:
Requisitos
Cuál
Tu
País
p>
Puedo
hacer
por
usted
Nuestra oración actual debería ser así:
1 en lugar de 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4
Si comprendes este mecanismo, puedes hacerlo fácilmente usando este diccionario y patrón de numeración Reconstruye el original oración. Esto es lo que hace el programa de descompresión de su computadora cuando expande el archivo descargado. Es posible que también te hayas encontrado con archivos comprimidos que puedes descomprimir tú mismo. Para crear un archivo de este tipo, el programador necesita configurar un descompresor 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 es 2345678-1 2856734" 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 debemos guardar este diccionario junto con el archivo.
En los esquemas de compresión reales, calcular varios requisitos de archivos es un proceso muy complejo. Volvamos atrás y consideremos el ejemplo anterior.
Cada carácter y espacio ocupa 1 unidad de almacenamiento y la oración original completa ocupa 79 unidades. Las oraciones comprimidas (incluidos los espacios) ocupan 37 unidades y los diccionarios (palabras y números) también ocupan 37 unidades. En otras palabras, el tamaño del archivo es 74 unidades, por lo que no reducimos demasiado el tamaño del archivo.
¡Pero es sólo una frase! Como era de esperar, si el resto del discurso de Kennedy se procesara a través de este compresor, encontraríamos que estas y otras palabras se repetirían aún más a menudo. Y, como se menciona en la siguiente sección, el diccionario se puede reescribir para lograr la mayor eficiencia organizacional posible.
En el último ejemplo, seleccionamos todas las palabras repetidas y las colocamos en el diccionario. Para nosotros, esta es la forma más obvia de escribir un diccionario. Pero el compresor no lo cree así: no tiene noción de palabras, sólo busca patrones. Para reducir el tamaño del archivo tanto como sea posible, selecciona cuidadosamente el mejor modo.
Si miras esta frase desde esta perspectiva, terminas con un diccionario completamente diferente.
Si el compresor escanea la frase de Kennedy, la primera parte redundante que encuentra tiene sólo unas pocas letras. En "Don't Ask What You Are", hay un patrón recurrente de la letra T seguida de un espacio en "no es" y "es qué". Si el compresor escribe este patrón en el diccionario, escribirá un "1" siempre que una "t" vaya seguida de un espacio. Sin embargo, en esta breve oración, este patrón no ocurre suficientes veces para calificarlo como una entrada en el diccionario, por lo que el programa eventualmente lo sobrescribe.
Lo siguiente que nota el programa es ou, que aparece tanto en el tuyo como en tu país. Si se trata de un documento extenso, escribir este patrón en un diccionario ahorrará mucho espacio; ou es una combinación de letras muy común en inglés. Pero después de que Compressor miró la oración completa, inmediatamente encontró una mejor opción para la entrada del diccionario: no solo se repitió ou, sino que también se repitieron las palabras completas your y country, y en realidad se repitieron juntas como una frase your country. 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 contigo y otra contigo, por lo que encontramos que puedo hacer por ti también es un patrón repetido. De esta manera, podemos usar un número para reemplazar los caracteres de 15 (espacios incluidos), y su país solo nos permite usar un número para reemplazar los caracteres de 13 (espacios incluidos), por lo que el programa sobrescribirá la entrada de su país con la entrada del país r, luego escriba una entrada separada que pueda 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 esta capacidad de reescribir el diccionario. El proceso mediante el cual un programa realiza este trabajo 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 extraído arriba y luego reemplazamos los espacios con "_ _", terminaremos con un diccionario más grande como este:
Pregunta a __
Qué_ _ amp shy ;
Tú
r _ _país
_ _puedes hacer_ _cosas por_ _ti_
Oraciones más cortas:
" 1 no _ _ 2345 _ _-_ _ 12354 "
La oración ahora ocupa 18 unidades de almacenamiento y el diccionario ocupa 41 unidades. Por lo tanto, comprimimos el tamaño total del archivo de 79 unidades a 59 unidades. Esta es sólo una forma de comprimir una oración, no necesariamente la más eficiente. ¿Puedes encontrar una mejor manera? )
Las tasas de compresión de archivos dependen de muchos 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, algunas 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 es alta.
Normalmente, un archivo de texto del tamaño adecuado puede alcanzar una relación de compresión de 50 o superior. La mayoría de los lenguajes de programación también son muy redundantes porque tienen relativamente pocos comandos y los comandos suelen seguir un patrón fijo. Para archivos que contienen mucha información no repetitiva (como imágenes o archivos MP3), este mecanismo no se puede utilizar para obtener relaciones de compresión altas porque no contienen patrones repetidos.
Si un 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 extraemos el discurso de JFK para que sea más largo, encontrará que el patrón en nuestro diccionario aparece muchas veces, por lo que puede guardar más archivos con cada espacio de entrada del diccionario. Además, para archivos más grandes puede haber un patrón más general que crea un diccionario más eficiente.
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. Otros programas de compresión utilizan diccionarios en su diccionario, lo que hace que funcionen bien al comprimir archivos grandes pero menos eficientes al comprimir archivos más pequeños. Aunque todos estos programas de compresión se basan en la misma idea básica, los realizan de diferentes maneras. Los programadores siempre están intentando crear un mejor mecanismo 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 después de que la otra parte lo reciba para su reutilización.
La compresión con pérdida es completamente diferente. Estos programas simplemente eliminan información "innecesaria" y cortan archivos para hacerlos más pequeños. Este tipo de compresión se usa 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 ser de tamaño muy grande. Para comprender cómo funciona la compresión con pérdida, veamos cómo su computadora comprime las fotografías escaneadas.
Para este tipo de archivos, la relación de compresión de los programas de compresión sin pérdidas no suele ser alta. Si bien la mayoría de las imágenes tienen el mismo aspecto (por ejemplo, todo el cielo es azul), existen diferencias sutiles entre la mayoría de los píxeles. Para reducir una imagen sin reducir la 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 todos los valores de los píxeles del cielo utilizan esta información. 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 el archivo original después de la compresión. Debe aceptar la reinterpretación del archivo original por parte del programa de compresión. Por lo tanto, si necesita reproducir completamente el contenido original (como aplicaciones de software, bases de datos y discursos inaugurales presidenciales), no debe utilizar esta forma de compresión.