¿Cuántas veces se puede comprimir un archivo?

Estaba pensando en la compresión, y parece que debería haber algún tipo de límite para la compresión que podría aplicarse a ella, de lo contrario sería un byte único.

Entonces mi pregunta es, ¿cuántas veces puedo comprimir un archivo antes de:

  • No se pone más pequeño?
  • El archivo se corrompe?

¿Son estos dos puntos iguales o diferentes?

¿Dónde aparece el punto de rendimientos decrecientes?

¿Cómo se pueden encontrar estos puntos?

No estoy hablando de ningún algoritmo específico o archivo particular, solo en general.

Para la compresión sin pérdida, la única manera en que puede saber cuántas veces puede ganar volviendo a comprimir un archivo es intentarlo. Va a depender del algoritmo de compresión y del archivo que está comprimiendo.

Dos archivos nunca se pueden comprimir en la misma salida, por lo que no puede bajar a un byte. ¿Cómo podría un byte representar todos los archivos a los que podrías descomprimir?

La razón por la que la segunda compresión a veces funciona es que un algoritmo de compresión no puede hacer una compresión perfecta omnisciente. Hay una compensación entre el trabajo que tiene que hacer y el tiempo que lleva hacerlo. Su archivo se está cambiando de todos los datos a una combinación de datos sobre sus datos y los datos en sí.

Ejemplo

Tome la encoding de longitud de ejecución (probablemente la compresión útil más simple) como ejemplo.

04 04 04 04 43 43 43 43 51 52 11 bytes

Esa serie de bytes se puede comprimir como:

[4] 04 [4] 43 [-2] 51 52 7 bytes (pongo los metadatos entre paréntesis)

Donde el número positivo entre paréntesis es un conteo repetido y el número negativo entre paréntesis es un comando para emitir los siguientes n caracteres a medida que se encuentran.

En este caso, podríamos intentar una compresión más:

[3] 04 [-4] 43 fe 51 52 7 bytes (fe es su -2 visto como complemento de dos datos)

No ganamos nada, y comenzaremos a crecer en la próxima iteración:

[-7] 03 04 fc 43 fe 51 52 8 bytes

Vamos a crecer en un byte por iteración por un tiempo, pero en realidad empeorará. Un byte solo puede contener números negativos a -128. Empezaremos a crecer en dos bytes cuando el archivo supere los 128 bytes de longitud. El crecimiento empeorará a medida que el archivo se agrande.

Hay un viento en contra del progtwig de compresión: los metadatos. Y también, para los compresores reales , el encabezado conectado al comienzo del archivo. Eso significa que, finalmente, el archivo comenzará a crecer con cada compresión adicional.


RLE es un punto de partida. Si desea obtener más información, mire LZ77 (que mira hacia atrás en el archivo para encontrar patrones) y LZ78 (que construye un diccionario). Compresores como zip a menudo prueban múltiples algoritmos y usan el mejor.

Aquí hay algunos casos en los que se me ocurre dónde ha funcionado la compresión múltiple.

  1. Trabajé en una revista de Amiga que se envió con un disco. Naturalmente, empaquetamos el disco en las agallas. Una de las herramientas que utilizamos le permite empaquetar un ejecutable para que, cuando se ejecutara, se descomprima y se ejecute solo. Debido a que el algoritmo de descompresión tenía que estar en cada ejecutable, tenía que ser pequeño y simple. A menudo obtuvimos ganancias adicionales al comprimir dos veces. La descompresión se realizó en RAM. Como leer un disquete era lento, ¡a menudo también aumentamos la velocidad!
  2. Microsoft admite la compresión RLE en archivos bmp. Además, muchos procesadores de texto hicieron la encoding RLE. Los archivos RLE son casi siempre significativamente compresibles por un mejor compresor.
  3. Muchos de los juegos en los que trabajé usaban un pequeño y rápido descompresor LZ77. Si comprime un gran rectángulo de píxeles (especialmente si tiene mucho color de fondo, o si se trata de una animación), con frecuencia puede comprimir dos veces con buenos resultados. (La razón: solo tienes tantos bits para especificar la distancia de retroceso y la longitud, por lo que un solo patrón repetido grande está codificado en varias piezas, y esas piezas son muy compresibles).

En general, el límite es una compresión. Algunos algoritmos dan como resultado una relación de compresión más alta, y el uso de un algoritmo pobre seguido de un buen algoritmo a menudo dará como resultado mejoras. Pero usar el buen algoritmo en primer lugar es lo correcto.

Existe un límite teórico sobre cuánto se puede comprimir un determinado conjunto de datos. Para aprender más sobre esto, deberá estudiar teoría de la información .

En general, para la mayoría de los algoritmos, comprimir más de una vez no es útil. Sin embargo, hay un caso especial.

Si tiene una gran cantidad de archivos duplicados, el formato zip se comprimirán de forma independiente, y luego podrá comprimir el primer archivo zip para eliminar la información duplicada. Específicamente, para 7 archivos Excel idénticos con un tamaño de 108kb, comprimirlos con 7-zip resulta en un archivo de 120kb. Zipping nuevamente da como resultado un archivo de 18 kb. Al pasar, obtienes rendimientos decrecientes.

Supongamos que tenemos un archivo de N bits de longitud, y queremos comprimirlo sin pérdidas para que podamos recuperar el archivo original. Hay 2 ^ N archivos posibles N bits de longitud, por lo que nuestro algoritmo de compresión tiene que cambiar uno de estos archivos a uno de 2 ^ N otros posibles. Sin embargo, no podemos express 2 ^ N archivos diferentes en menos de N bits.

Por lo tanto, si podemos tomar algunos archivos y comprimirlos, tenemos que tener algunos archivos de esa longitud bajo compresión, para equilibrar los que se acortan.

Esto significa que un algoritmo de compresión solo puede comprimir ciertos archivos, y en realidad tiene que alargar algunos. Esto significa que, en promedio, la compresión de un archivo aleatorio no puede acortarlo, pero puede alargarlo.

Los algoritmos de compresión práctica funcionan porque normalmente no usamos archivos aleatorios. La mayoría de los archivos que usamos tienen algún tipo de estructura u otras propiedades, ya sean texto o progtwigs ejecutables o imágenes significativas. Al usar un buen algoritmo de compresión, podemos acortar drásticamente los archivos de los tipos que usamos normalmente.

Sin embargo, el archivo comprimido no es uno de esos tipos. Si el algoritmo de compresión es bueno, la mayor parte de la estructura y la redundancia se han eliminado, y lo que queda se parece bastante a la aleatoriedad.

Ningún algoritmo de compresión, como hemos visto, puede comprimir eficazmente un archivo aleatorio, y eso también se aplica a un archivo de aspecto aleatorio. Por lo tanto, tratar de volver a comprimir un archivo comprimido no lo acortará significativamente, y podría alargarlo un poco.

Por lo tanto, la cantidad normal de veces que un algoritmo de compresión puede ejecutarse de forma rentable es uno.

La corrupción solo ocurre cuando hablamos de compresión con pérdida. Por ejemplo, no puede recuperar una imagen precisamente desde un archivo JPEG. Esto significa que un compresor JPEG puede acortar confiablemente un archivo de imagen, pero solo a costa de no poder recuperarlo exactamente. A menudo estamos dispuestos a hacer esto para imágenes, pero no para texto, y particularmente no archivos ejecutables.

En este caso, no hay una etapa en la que comience la corrupción. Comienza cuando comienzas a comprimirlo, y empeora a medida que lo comprimes más. Es por eso que los buenos progtwigs de procesamiento de imágenes le permiten especificar la cantidad de compresión que desea cuando crea un archivo JPEG: para que pueda equilibrar la calidad de la imagen con el tamaño del archivo. Encuentra el punto de parada al considerar el costo del tamaño del archivo (que es más importante para las conexiones de red que el almacenamiento, en general) versus el costo de la calidad reducida. No hay una respuesta correcta obvia.

Por lo general, comprimir una vez es lo suficientemente bueno si el algoritmo es bueno.
De hecho, la compresión de múltiples veces podría conducir a un aumento en el tamaño

Tus dos puntos son diferentes.

  • Compresión realizada repetidamente y sin lograr ninguna mejora en la reducción de tamaño
    es una condición teórica esperada
  • Compresión repetida que causa corrupción
    es probable que sea un error en la implementación (o tal vez el algoritmo en sí)

Ahora veamos algunas excepciones o variaciones,

  • La encriptación puede aplicarse repetidamente sin reducción de tamaño
    (de hecho, a veces aumentan de tamaño) con el fin de boost la seguridad
  • Imagen, video o archivos de audio cada vez más comprimidos
    perderá datos (efectivamente se ‘corrompe’ en cierto sentido)

Puede comprimir un archivo tantas veces como desee. Pero para la mayoría de los algoritmos de compresión la compresión resultante desde la segunda vez será insignificante.

La compresión (estoy pensando en la pérdida) básicamente significa express algo más concisamente. Por ejemplo

111111111111111 

podría ser expresado más consistentemente como

 15 X '1' 

Esto se llama encoding de longitud de ejecución. Otro método que una computadora puede usar es encontrar un patrón que se repite regularmente en un archivo.

Existe un límite en cuanto a la cantidad de estas técnicas que se pueden utilizar, por ejemplo, la encoding de longitud de ejecución no va a tener efecto en

 15 X '1' 

ya que no hay patrones que se repitan De manera similar, si los métodos de reemplazo de patrones convierten los patrones largos en 3 caracteres, volver a aplicarlo tendrá poco efecto, ya que los únicos patrones de repetición restantes serán de 3 o más. En general, aplicar compresión a un archivo ya comprimido lo hace un poco más grande debido a varios gastos generales. Aplicar una buena compresión a un archivo pobremente comprimido generalmente es menos efectivo que aplicar solo la buena compresión.

¿Cuántas veces puedo comprimir un archivo antes de que no se vuelva más pequeño?

En general, ni siquiera uno . Cualquiera que sea el algoritmo de compresión que use, siempre debe existir un archivo que no se comprima del todo, de lo contrario, siempre se puede comprimir varias veces hasta llegar a 1 byte, por el mismo argumento.

¿Cuántas veces puedo comprimir un archivo antes de que se dañe?

Si el progtwig que utiliza para comprimir el archivo hace su trabajo, el archivo nunca se dañará (por supuesto, estoy pensando en la compresión sin pérdida).

Puedes comprimir tiempos infinitos. Sin embargo, la segunda y más compresiones generalmente solo producirán un archivo más grande que el anterior. Entonces no tiene sentido comprimir más de una vez.

Es una muy buena pregunta. Puede ver el archivo desde un punto de vista diferente. Quizás sabes a priori que este archivo contiene series aritméticas. Permite verlo como un flujo de datos de “bytes”, “símbolos” o “muestras”.

Algunas respuestas pueden brindarle “teoría de la información” y “estadísticas matemáticas”. Consulte la monografía de los investigadores para una comprensión completa:

A. Kolmogorov

S. Kullback

С. Shannon

N. Wiener

Uno de los conceptos principales en la teoría de la información es la entropía . Si tiene una secuencia de “bytes” … La entropía de esos bytes no depende de los valores de sus “bytes”, o “muestras” … Si fue definida solo por frecuencias con las cuales los bytes recuperan diferentes valores. La entropía máxima tiene lugar para el flujo de datos aleatorio completo. La entropía mínima, que es igual a cero, tiene lugar para el caso cuando sus “bytes” tienen un valor idéntico.

No se pone más pequeño?

Por lo tanto, la entropía es la cantidad mínima de bits por su “byte”, que debe usar al escribir información en el disco. Por supuesto que es así si usas el algoritmo de Dios. Los algoritmos heurísticos sin pérdida de compresión de la vida real no son así.

El archivo se corrompe?

No entiendo el sentido de la pregunta. No puede escribir ningún bit en el disco y escribirá un archivo dañado en el disco con un tamaño igual a 0 bits. Por supuesto, está dañado, pero su tamaño es de cero bits.

Aquí está el último algoritmo de compresión (en Python) que mediante el uso repetido comprimirá cualquier cadena de dígitos hasta el tamaño 0 (se deja como ejercicio para el lector cómo aplicar esto a una cadena de bytes).

 def compress(digitString): if digitString=="": raise "already as small as possible" currentLen=len(digitString) if digitString=="0"*currentLen: return "9"*(currentLen-1) n=str(long(digitString)-1); #convert to number and decrement newLen=len(n); return ("0"*(currentLen-newLen))+n; # add zeros to keep same length #test it x="12"; while not x=="": print x; x=compress(x) 

El progtwig genera 12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 y luego vacía la secuencia. No comprime la cuerda en cada pasada pero con pases suficientes comprime cualquier cadena de dígitos hasta una cadena de longitud cero. Asegúrese de anotar cuántas veces lo envía a través del compresor, de lo contrario no podrá recuperarlo.

Ejemplo de una técnica de compresión más avanzada que utiliza “una tabla doble o una matriz cruzada”. También elimina los símbolos de extinción no exudados en el algoritmo.

[EJEMPLO ANTERIOR] Tome la encoding de longitud de ejecución (probablemente la compresión útil más simple) como ejemplo.

04 04 04 04 43 43 43 43 51 52 11 bytes

Esa serie de bytes se puede comprimir como:

[4] 04 [4] 43 [-2] 51 52 7 bytes (pongo los metadatos entre paréntesis)

[SE CONVIERTE] 04.43.51.52 VALORES 4.4. ** – 2 COMPRESIÓN

Mayor compresión usando símbolos adicionales como valores sustitutos

04.ABC VALUES 4.4. ** – 2 COMPRESIÓN

En teoría, nunca lo sabremos, es algo que nunca termina:

En informática y matemáticas, el término teorema de pleno empleo se ha utilizado para referirse a un teorema que muestra que ningún algoritmo puede realizar de manera óptima una tarea particular realizada por una clase de profesionales. El nombre surge porque tal teorema asegura que hay un scope infinito para seguir descubriendo nuevas técnicas para mejorar la forma en que se realiza al menos una tarea específica. Por ejemplo, el teorema del pleno empleo para los escritores de comstackdores afirma que no existe un comstackdor de optimización de tamaño que se pueda demostrar de manera demostrable, ya que tal prueba para el comstackdor tendría que detectar los cálculos no terminales y reducirlos a un infinito de instrucción única. lazo. Por lo tanto, la existencia de un comstackdor de optimización de tamaño probadamente perfecto implicaría una solución al problema de detención, que no puede existir , haciendo que la prueba en sí misma sea un problema indecidible.

(fuente)

Todo depende del algoritmo. En otras palabras, la pregunta puede ser cuántas veces se puede comprimir un archivo usando este algoritmo primero, y luego este …