Principios básicos de la compresión
Si descargas muchos programas y archivos de Internet, es posible que te encuentres con muchos archivos ZIP. Este mecanismo de compresión es un invento muy conveniente, especialmente para los usuarios de la web, ya que 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 lentas a Internet y al mismo tiempo reduce el espacio en disco que ocupan los archivos. 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. 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.
Da un ejemplo
Toma un tipo de información familiar: 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 famosos discursos de JFK, podemos seleccionar palabras repetidas y colocarlas en un índice numerado. Luego, escribimos números directamente en lugar de palabras completas.
Conclusión
Entonces, si nuestro diccionario es:
Requisitos
Cuál
Tu
p>
El país
puede
hacer
por ti
Nuestra frase debería ser así:
1 en lugar de 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4
Si entiendes el mecanismo, puedes pasar fácilmente Usa esto diccionario y patrón de numeración para reconstruir la oración original. 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 mantener el tamaño del archivo lo más pequeño 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 finalmente 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 tomamos el patrón extraído arriba y reemplazamos los espacios con "_ _", terminaremos con este diccionario más grande:
Pregunta a __
Qué_ _ & amp Shy;
Tú
r _ _país
_ _puedes hacer_ _cosas por_ _ti_
Actualizaciones de oraciones cortas:
" 1 no _ _ 2345 _ _-_ _ 12354 "
Las oraciones ocupan 18 unidades de almacenamiento y los diccionarios ocupan 41 unidades de almacenamiento. Por lo tanto, comprimimos el tamaño total del archivo de 79 unidades a 59 unidades. Esta es sólo una forma de comprimir oraciones, no necesariamente la más eficiente. ¡Vea si puede encontrar una mejor manera! )