¿Cómo funciona la compresión de archivos?

Entonces, me di cuenta hoy que doy por sentado la compresión de archivos. La posibilidad de agrupar algunos archivos en uno y hacer que sea más pequeña que cualquiera de ellos es algo que acepto como un hecho, pero ¿cómo funciona realmente?

Tengo un conocimiento limitado de eso que incluye algo que ver con reemplazar todas las entradas duplicadas con punteros, para reducirlo de esa manera, pero más allá de eso, ¡no tengo ni idea!

Como siempre estoy abierto a nuevos conocimientos, como imagino que la mayoría de nosotros estamos aquí, pensé en preguntar. Entonces, Superusuario, ¿cómo funciona realmente la compresión ?

Compresión sin perdidas

La compresión sin pérdida es donde no se pierden datos. Todo lo que se ingresa se puede recuperar perfectamente. Esto funciona bien para archivos de texto o binarios donde se notará el error más pequeño.

La compresión de archivos funciona tomando el archivo y escaneando patrones, y traduciendo esos patrones a otra cosa que ocupe menos espacio.

Por ejemplo, "AAAAAAAA" podría convertirse en "8A".

Es cierto que no es así exactamente porque entonces tienes el problema, ¿qué pasaría si "8A" estuviera en texto plano? Descomprimiría el archivo y estaría mal. Un buen lugar para comenzar es Wikipedia o el algoritmo de compresión de datos LZW .

Hay un simple código psuedo para esto copiado a continuación:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

Toda compresión utiliza un diccionario de búsqueda que se utiliza para comprimir y descomprimir el archivo. Cuanto más grande sea el diccionario, más podrá comprimirlo, aunque se tope con la Ley de rendimientos decrecientes .

También vale la pena señalar que la compresión no siempre produce un archivo más pequeño. Hay situaciones (con archivos pequeños o al comprimir datos aleatorios ) en las que no obtendrá un archivo más pequeño después de la compresión. Ha habido algunos desafíos divertidos relacionados con la capacidad de comprimir datos aleatorios.

Compresión "con pérdida"

Lo anterior se refiere principalmente a la compresión sin pérdidas . Otros tipos de compresión utilizados en aplicaciones de video / audio como MP3, JPG y h.264 son ejemplos de compresión con pérdida .

La compresión con pérdida funciona al descartar los datos que es menos probable que se noten. En audio, esto suena alrededor de 30,000 Hrz y menos de 100 Hrz, junto con otras cosas diferentes. En la imagen (estática), elimina varias cosas y fusiona píxeles juntos, junto con el descarte de datos.

La compresión con pérdida es una forma de codificación de transformación . Promedia los datos para reducir el tamaño general. Por ejemplo, un bloque de 10 píxeles en una imagen, todos los colores ligeramente diferentes se pueden combinar en un solo color y, por lo tanto, comprimirse.

En la compresión de video, a menudo las instrucciones se colocarán para volver a dibujar los píxeles que han cambiado desde el último fotograma o fotograma clave .

La compresión funciona al encontrar patrones en los datos y luego reemplazar estos patrones con patrones especiales más pequeños. La descompresión es la inversa: encuentre los patrones especiales y reemplácelos con los patrones más grandes que representan. Saber qué patrones son probables es importante; por ejemplo, los patrones que se encuentran en el texto pueden ser bastante diferentes a los que se encuentran en las imágenes. Algunas técnicas de compresión son con pérdida; no garantizan que la expansión recuperará la entrada exactamente. Esto generalmente está bien para datos analógicos, como música e imágenes, si la pérdida es lo suficientemente pequeña. Pero datos como el texto deben comprimirse con técnicas sin pérdidas.

Es importante darse cuenta de que es imposible comprimir, sin pérdida, datos aleatorios ni un solo bit. Considere un archivo con N bits de datos binarios. Hay 2 ^ N archivos posibles. Si comprime alguno de estos archivos en un solo bit, por lo que el archivo comprimido tiene un tamaño de N-1 bits, solo hay 2 ^ (N-1) representaciones comprimidas posibles. En otras palabras, cada posible archivo comprimido debe representar más de un posible archivo sin comprimir. Sin una representación comprimida única, el algoritmo de descompresión no puede garantizar una descompresión sin pérdidas.