compression - que - ¿Cuántas veces se puede comprimir un archivo?
programa para comprimir archivos al maximo (14)
¿Cuántas veces puedo comprimir un archivo antes de que no se haga más pequeño?
En general, ni siquiera uno . Independientemente del algoritmo de compresión que utilice, siempre debe existir un archivo que no se comprima en absoluto, de lo contrario, siempre podría comprimir repetidamente hasta que alcance 1 byte, según su mismo argumento.
¿Cuántas veces puedo comprimir un archivo antes de que se corrompa?
Si el programa que usa para comprimir el archivo hace su trabajo, el archivo nunca se corromperá (por supuesto, estoy pensando en una compresión sin pérdida).
Estaba pensando en la compresión, y parece que tendría que haber algún tipo de límite para la compresión que podría aplicarse, de lo contrario sería un solo byte.
Así que mi pregunta es, ¿cuántas veces puedo comprimir un archivo antes:
- ¿No se hace más pequeño?
- El archivo se corrompe?
¿Son estos dos puntos iguales o diferentes?
¿Dónde aparece el punto de los rendimientos decrecientes?
¿Cómo se pueden encontrar estos puntos?
No estoy hablando de ningún algoritmo específico o archivo en particular, solo en general.
Aquí está el último algoritmo de compresión (en Python) que, al usarlo repetidamente, 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)
Las salidas del programa 12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 luego cadena vacía. No comprime la cadena en cada paso, pero con suficientes pases comprimirá 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 algoritmos extrenusales en algoritmos
[EJEMPLO ANTERIOR] Tome la codificación 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 podría ser comprimida como:
[4] 04 [4] 43 [-2] 51 52 7 bytes (pongo los metadatos entre paréntesis)
[SE ACUERDA] 04.43.51.52 VALORES 4.4. ** - 2 COMPRESIÓN
Compresión adicional usando símbolos adicionales como valores sustitutos
04. VALORES ABC 4.4. ** - 2 COMPRESIÓN
En general, para la mayoría de los algoritmos, comprimir más de una vez no es útil. Aunque hay un caso especial.
Si tiene una gran cantidad de archivos duplicados, el formato zip comprimirá cada uno 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 108 kb, comprimirlos con resultados de 7 zip en un archivo de 120 kb. Al volver a cerrar, se obtiene un archivo de 18kb. Yendo más allá, obtienes rendimientos decrecientes.
En teoría, nunca lo sabremos, es una cosa interminable:
En ciencias de la computación y matemáticas, el término teorema de empleo total se ha utilizado para referirse a un teorema que muestra que ningún algoritmo puede realizar de manera óptima una tarea particular realizada por alguna clase de profesionales. El nombre surge debido a que dicho teorema garantiza que hay un alcance infinito para seguir descubriendo nuevas técnicas para mejorar la forma en que se realiza al menos alguna tarea específica. Por ejemplo, el teorema de empleo completo para los compiladores de compiladores establece que no existe tal cosa como un compilador de tamaño optimizado, como tal, una prueba para el compilador tendría que detectar cálculos no terminados y reducirlos a un infinito de una sola instrucción. lazo. Por lo tanto, la existencia de un compilador de optimización de tamaño que sea probadamente perfecto implicaría una solución al problema de detención, que no puede existir , haciendo de la prueba en sí un problema indecidible.
Es una muy buena pregunta. Se puede ver a archivo desde diferentes puntos de vista. Tal vez usted sepa 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 proporcionarle "teoría de la información" y "estadísticas matemáticas". Verifique la monografía de los investigadores para una comprensión más profunda:
Uno de los conceptos principales en la teoría de la información es la entropy . Si tiene un flujo de "bytes" ... La entropía de esos bytes no depende de los valores de sus "bytes" o "muestras" ... Si se definió solo por las frecuencias con las cuales los bytes recuperan valores diferentes. 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 hace 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 tan
El archivo se corrompe?
No entiendo el sentido de la pregunta. No puede escribir bits en el disco y escribirá un archivo dañado en el disco con un tamaño igual a 0 bits. Por supuesto que está corrompido, pero su tamaño es de cero bits.
Generalmente 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 deficiente seguido de un buen algoritmo a menudo resultará en mejoras. Pero usar el buen algoritmo en primer lugar es lo correcto.
Existe un límite teórico en cuanto a la cantidad de datos que se pueden comprimir. Para aprender más sobre esto tendrás que estudiar la teoría de la información .
La compresión (estoy pensando sin pérdida) básicamente significa expresar algo de manera más concisa. Por ejemplo
111111111111111
podría ser expresado más consisamente como
15 X ''1''
Esto se llama codificación de longitud de ejecución. Otro método que puede usar una computadora es encontrar un patrón que se repita regularmente en un archivo.
Claramente hay un límite en cuanto a la cantidad de estas técnicas que se pueden usar, por ejemplo, la codificación de longitud de ejecución no tendrá efecto en
15 X ''1''
Ya que no hay patrones repetitivos. De manera similar, si los métodos de reemplazo de patrones convierten los patrones largos en 3 caracteres, volver a aplicarlos tendrá poco efecto, porque los únicos patrones de repetición restantes serán de 3 longitud o más cortos. En general, la aplicación de 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 mal comprimido suele ser menos efectivo que aplicar solo la buena compresión.
Para la compresión sin pérdida, la única manera de saber cuántas veces puede ganar al recomprimir un archivo es probándolo. 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ía descomprimir?
La razón por la que la segunda compresión a veces funciona es que un algoritmo de compresión no puede realizar una compresión omnisciente perfecta. Hay una compensación entre el trabajo que tiene que hacer y el tiempo que se tarda en hacerlo. Se está cambiando su archivo de todos los datos a una combinación de datos sobre sus datos y los datos en sí.
Ejemplo
Tome la codificación 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 podría ser comprimida 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 de repetición y el número negativo entre paréntesis es un comando para emitir los siguientes caracteres -n como se encuentran.
En este caso podríamos probar una compresión más:
[3] 04 [-4] 43 fe 51 52 7 bytes (fe es su -2 visto como datos de complemento de dos)
No ganamos nada, y comenzaremos a crecer en la siguiente iteración:
[-7] 03 04 fc 43 fe 51 52 8 bytes
Creceremos un byte por iteración por un tiempo, pero en realidad empeorará. Un byte solo puede contener números negativos hasta -128. Comenzaremos a crecer por dos bytes cuando el archivo supere los 128 bytes de longitud. El crecimiento empeorará a medida que el archivo crezca.
Hay un viento de frente en contra del programa de compresión: los metadatos. Y también, para compresores reales , el encabezado se agregó al principio del archivo. Eso significa que eventualmente el archivo comenzará a crecer con cada compresión adicional.
RLE es un punto de partida. Si desea obtener más información, consulte LZ77 (que busca en el archivo para encontrar patrones) y LZ77 (que crea un diccionario). Compresores como zip a menudo prueban múltiples algoritmos y usan el mejor.
Aquí hay algunos casos en los que puedo pensar en dónde ha funcionado la compresión múltiple.
- Trabajé en una revista Amiga que se envió con un disco. Naturalmente, empacamos el disco a las agallas. Una de las herramientas que usamos le permitió empaquetar un ejecutable para que cuando se ejecutó, se descomprimió y se ejecutó 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 obteníamos ganancias adicionales al comprimir dos veces. La descompresión se realizó en la memoria RAM. Como la lectura de un disquete era lenta, a menudo también obteníamos un aumento de velocidad.
- Microsoft admitió la compresión RLE en archivos bmp. Además, muchos procesadores de texto hicieron codificación RLE. Los archivos RLE casi siempre se pueden comprimir significativamente con un mejor compresor.
- Muchos de los juegos en los que trabajé utilizaban un descompresor LZ77 pequeño y rápido. Si comprime un gran rectángulo de píxeles (especialmente si tiene mucho color de fondo o si es una animación), muy a menudo puede comprimir dos veces con buenos resultados. (¿El motivo? Solo tiene tantos bits para especificar la distancia y la longitud del lookback, por lo que un solo patrón repetido grande se codifica en varias piezas, y esas piezas son altamente compresibles).
Por lo general, comprimir una vez es suficiente si el algoritmo es bueno.
De hecho, comprimir varias veces podría llevar a un aumento en el tamaño
Tus dos puntos son diferentes.
- Compresión realizada repetidamente y sin lograr mejoras en la reducción de tamaño.
es una condición teórica esperada - Compresión repetida causando corrupción
es probable que sea un error en la implementación (o quizás el algoritmo mismo)
Ahora veamos algunas excepciones o variaciones,
- El cifrado se puede aplicar repetidamente sin reducción de tamaño
(de hecho, a veces aumenta de tamaño) con el propósito de aumentar la seguridad - Archivos de imagen, video o audio cada vez más comprimidos.
perderá datos (efectivamente se ''corromperá'' en cierto sentido)
Puedes comprimir los tiempos infinitos. Sin embargo, las compresiones segunda y posteriores generalmente solo producirán un archivo más grande que el anterior. Así que no tiene sentido comprimir más de una vez.
Puedes comprimir un archivo tantas veces como quieras. Pero para la mayoría de los algoritmos de compresión, la compresión resultante a partir de la segunda vez será despreciable.
Supongamos que tenemos un archivo de N bits de largo, y queremos comprimirlo sin pérdidas, para que podamos recuperar el archivo original. Hay 2 ^ N de archivos posibles de N bits de longitud, por lo que nuestro algoritmo de compresión tiene que cambiar uno de estos archivos a uno de los 2 ^ N posibles. Sin embargo, no podemos expresar 2 ^ N archivos diferentes en menos de N bits.
Por lo tanto, si podemos tomar algunos archivos y comprimirlos, tenemos que tener algunos archivos con una longitud inferior a la compresión, para equilibrar los que 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 podría alargarlo.
Los algoritmos prácticos de compresión funcionan porque generalmente no usamos archivos aleatorios. La mayoría de los archivos que utilizamos tienen algún tipo de estructura u otras propiedades, ya sean ejecutables de texto o programa o imágenes significativas. Al usar un buen algoritmo de compresión, podemos acortar dramáticamente 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 efectivamente un archivo aleatorio, y eso también se aplica a un archivo de apariencia aleatoria. Por lo tanto, tratar de volver a comprimir un archivo comprimido no lo acortará significativamente, y podría alargarlo un poco.
Por lo tanto, el número normal de veces que un algoritmo de compresión puede ejecutarse de manera rentable es uno.
La corrupción solo ocurre cuando estamos hablando de compresión con pérdida. Por ejemplo, no necesariamente puede recuperar una imagen precisamente de un archivo JPEG. Esto significa que un compresor JPEG puede acortar de manera confiable un archivo de imagen, pero solo al costo de no poder recuperarlo exactamente. A menudo estamos dispuestos a hacer esto para las imágenes, pero no para el texto, y especialmente los archivos no ejecutables.
En este caso, no hay una etapa en la que comience la corrupción. Comienza cuando empiezas a comprimirlo, y empeora a medida que lo compres más. Es por eso que los buenos programas de procesamiento de imágenes le permiten especificar cuánta compresión desea cuando crea un JPEG: para que pueda equilibrar la calidad de la imagen con el tamaño del archivo. Encontrará el punto de parada considerando el costo del tamaño del archivo (que es más importante para las conexiones de red que para el almacenamiento, en general) en comparación con el costo de la calidad reducida. No hay una respuesta correcta obvia.
Todo depende del algoritmo. En otras palabras, la pregunta puede ser cuántas veces se puede comprimir un archivo utilizando primero este algoritmo, luego este siguiente ...