¿Cuál es el concepto detrás de la compresión zip?

Question

¿Cuál es el concepto detrás de la compresión zip? Puedo entender el concepto de eliminar espacio vacío, etc., pero presumiblemente se debe agregar algo para decir cuánto/dónde ese espacio libre necesita ser agregado nuevamente durante la descompresión.

¿Cuál es el proceso básico para comprimir una secuencia de bytes?

Answer 1

Un buen lugar para comenzar sería buscar el esquema de compresión Huffman. La idea básica detrás de huffman es que en un archivo dado, algunos bytes aparecen con más frecuencia que otros (en un archivo de texto sin formato, muchos bytes no aparecerán en absoluto). En lugar de gastar 8 bits para codificar cada byte, ¿por qué no utilizar una secuencia de bits más corta para codificar los caracteres más comunes, y una secuencia más larga para codificar los caracteres menos comunes (estas secuencias se determinan creando un árbol huffman).

Una vez que tenga control sobre el uso de estos árboles para codificar/decodificar archivos basados ​​en la frecuencia de caracteres, imagine que luego comienza a trabajar en la frecuencia de las palabras; en lugar de codificar "ellos" como una secuencia de 4 caracteres, ¿por qué no considerarlo? ser un personaje único debido a su frecuencia, lo que permite que se le asigne su propia hoja en el árbol huffman. Esta es más o menos la base de la compresión ZIP y de otros tipos sin pérdida: buscan "palabras" comunes (secuencias de bytes) en un archivo (incluidas las secuencias de solo 1 byte si son lo suficientemente comunes) y usan un árbol para codificarlas. El archivo zip solo necesita incluir la información del árbol (una copia de cada secuencia y la cantidad de veces que aparece) para permitir que el árbol sea reconstruido y el resto del archivo que se decodificará.

seguimiento:

Para responder mejor a la pregunta original, la idea detrás de compresión sin pérdida no es tanto para eliminar el espacio vacío, pero para eliminar redundent información.

Si creó una base de datos para almacenar letras de canciones, encontraría que se estaba usando mucho espacio para almacenar el coro que se repite varias veces. En lugar de usar todo ese espacio, simplemente podría colocar la palabra CHORUS antes de la primera instancia de las líneas del coro, y luego cada vez que se repita el coro, simplemente use CHORUS como marcador de posición (de hecho, esta es más o menos la idea detrás de la compresión LZW - en LZW cada línea de la canción tendría un número antes. Si una línea se repite más tarde en la canción, en lugar de escribir toda la línea solo se muestra el número)

Answer 2

El concepto entre compresión es básicamente estadístico. Si tiene una serie de bytes, la probabilidad de que el byte N sea X en la práctica depende de la distribución del valor de los bytes anteriores 0..N-1. Sin compresión, se asignan 8 bits para cada valor posible X. Con la compresión, las cantidades de bytes asignadas para cada valor X dependen de la probabilidad estimada p (N, X).

Por ejemplo, dada una secuencia "aaaa", un algoritmo de compresión puede asignar un valor alto a p (5, a) y valores inferiores a p (5, b). Cuando p (X) es alto, la cadena de bits asignada a X será corta, cuando p (X) es baja, se utiliza una cadena de bits larga. De esta forma, si p (N, X) es una buena estimación, la cadena de bits promedio será más corta que 8 bits.

Answer 3

El concepto básico es que en lugar de usar ocho bits para representar cada byte, utiliza representaciones más cortas para bytes o secuencias de bytes que se producen con mayor frecuencia.

Por ejemplo, si el archivo de consiste únicamente en el 0x41 byte (A) repetidas dieciséis veces, a continuación, en lugar de representar como la secuencia de 8 bits 01000001 acortarlo a la secuencia de 1-bit 0. Entonces el archivo se puede representar por 0000000000000000 (dieciséis 0 s).Entonces, el archivo del byte 0x41 repetido dieciséis veces puede ser representado por el archivo que consiste en el byte 0x00 repetido dos veces.

Así que lo que tenemos aquí es que para este archivo (0x41 repite dieciséis veces) los bits 01000001 no transmiten ninguna información adicional sobre el bit 0. Entonces, en este caso, tiramos los bits extraños para obtener una representación más corta.

Esa es la idea central detrás de la compresión.

Como otro ejemplo, considere el patrón de ocho bytes

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

y ahora lo repiten 2048 veces. Una forma de seguir el enfoque anterior es representar bytes utilizando tres bits.

000 0x41 
001 0x42 
010 0x43 
011 0x44 
100 0x45 
101 0x46 
110 0x47 
111 0x48 

Ahora podemos representar el patrón de bytes por encima de 00000101 00111001 01110111 (éste es el patrón de tres bytes 0x05 0x39 0x77) repite 2048 veces.

Pero un enfoque aún mejor es para representar el patrón de bytes

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

por el solo bit 0. Entonces podemos representar el patrón de byte anterior por 0 repetido 2048 veces que se convierte en el byte 0x00 repetido 256 veces. Ahora sólo tenemos que almacenar el diccionario

0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

y el patrón de bytes 0x00 repitió 256 veces y comprimimos el archivo de 16.384 bytes a (módulo el diccionario) de 256 bytes.

Eso, en pocas palabras, es cómo funciona la compresión. Todo el asunto se reduce a encontrar representaciones cortas y eficientes de los bytes y secuencias de bytes en un archivo dado. Esa es la idea simple, pero los detalles (encontrar la representación) pueden ser bastante desafiantes.

Véase, por ejemplo:

1. Data compression
2. Run length encoding
3. Huffman compression
4. Shannon-Fano coding
5. LZW