Nuestros mejores investigadores agotaron sus reservas de café, en su búsqueda noche y día por la respuesta, hasta que Liliana encontró la contestación en Beanstalk así que ahora la compartimos aquí.
Solución:
Basado en la idea de que un archivo comprimido es un nuevo archivo binario, ¿por qué no puedo reducir su tamaño comprimiéndolo nuevamente y sucesivamente hasta un archivo muy pequeño?
Porque la compresión funciona en base a encontrar patrones y reducir datos que son similares.
Por ejemplo, RLE (Codificación de longitud de ejecución) es un método de compresión simple donde los datos se examinan y las series de datos similares se comprimen de la siguiente manera:
AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA
becomes
3ABC3EJ2F10YOO4A5G3A
Como puede ver, al reemplazar los datos repetidos con solo los datos y un recuento de cuántas veces ocurre, puede reducir este ejemplo específico de 35 bytes a 20 bytes. eso no es un enorme reducción, pero sigue siendo un 42% más pequeño. Además, este es un pequeño ejemplo artificial; los ejemplos más grandes de la vida real podrían tener una compresión aún mejor. (Él OO se quedó solo porque reemplazándolo con 2O no ahorraría nada.)
Los archivos de texto a menudo se comprimen muy bien porque tienden a tener muchos patrones que se pueden comprimir. Por ejemplo, la palabra la es muy común en inglés, por lo que puede eliminar cada instancia de la palabra con un identificador que es solo un byte (o incluso menos). También puedes comprimir más con partes de palabras que son similares como cAKE, bAKE, shAKE, undertAKEy así.
Entonces, ¿por qué no puedes comprimir un archivo que ya está comprimido? Porque cuando hiciste la compresión inicial, eliminé los patrones.
Mire el ejemplo de RLE comprimido. ¿Cómo puedes comprimir eso más? No hay ejecuciones de datos idénticos para comprimir. De hecho, a menudo, cuando intenta comprimir un archivo que ya está comprimido, puede terminar con un más grande expediente. Por ejemplo, si forzó la recodificación del ejemplo anterior, podría terminar con algo como esto:
131A1B1C131E1J121F11101Y2O141A151G131A
Ahora, los datos de compresión (los recuentos de ejecución) se tratan como datos, por lo que termina con un archivo más grande que el que tenía al principio.
Lo que tu podría intentar es usar un algoritmo de compresión diferente porque es posible que la salida de un algoritmo de compresión sea la mejor para un algoritmo diferente, sin embargo, eso suele ser bastante improbable.
Por supuesto, se trata de una compresión sin pérdidas en la que los datos descomprimidos deben ser exactamente idénticos a los datos originales. Con la compresión con pérdida, generalmente puede eliminar más datos, pero la calidad disminuye. Además, la compresión con pérdida suele utilizar algún tipo de esquema basado en patrones (no solamente descartar datos), por lo que finalmente llegará a un punto en el que simplemente no hay patrones para encontrar.
Un archivo comprimido de forma óptima no tendrá patrones ni nada que pueda reducirse.
Imaginemos un archivo simple que contenga esto.
AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC
Si lo comprimimos podríamos decir que son 20 A’s, nueva línea, seguidas de 20 B’s, nueva línea, seguidas de 20 C’s. o algo como 20xAn20xBn20xCn. Una vez que hemos hecho la primera compresión, no hay nuevos patrones para comprimir. Cada bit si la información es única.
Si todos los archivos comprimidos después de volver a comprimirlos reducen su tamaño (o tienen tamaños que no son más grandes que sus padres), en algún momento el tamaño se convertirá en 0, lo que no puede ser true. si eso es true casi no necesitamos almacenamiento de archivos en absoluto.
Algoritmos de compresión de datos sin pérdida no puede garantizar la compresión para todos los conjuntos de datos de entrada. En otras palabras, para cualquier algoritmo de compresión de datos sin pérdidas, habrá un conjunto de datos de entrada que no se reducirá cuando el algoritmo los procese, y para cualquier algoritmo de compresión de datos sin pérdidas que reduzca al menos un archivo, habrá al menos un archivo que hace más grande. Esto se demuestra fácilmente con matemáticas elementales usando un argumento de conteo, como sigue:
- Suponga que cada archivo se representa como un string de bits de alguna longitud arbitraria.
- Supongamos que hay un algoritmo de compresión que transforma cada archivo en un archivo de salida que no es más largo que el archivo original y que al menos un archivo se comprimirá en un archivo de salida más corto que el archivo original.
- Sea M el menor número tal que hay un archivo F con una longitud de M bits que se comprime a algo más corto. Sea N la longitud (en bits) de la versión comprimida de F.
- Debido a que N < M, cada archivo de longitud N mantiene su tamaño durante la compresión. Hay 2norte dichos archivos. Junto con F, esto hace 2norte+1 archivos que se comprimen en uno de los 2norte archivos de longitud N.
- pero 2norte es menor que 2norte+1, por lo que, según el principio del casillero, debe haber algún archivo de longitud N que sea simultáneamente la salida de la función de compresión en dos entradas diferentes. Ese archivo no se puede descomprimir de manera confiable (¿cuál de los dos originales debería producir?), lo que contradice la suposición de que el algoritmo no tuvo pérdidas.
- Por lo tanto, debemos concluir que nuestra hipótesis original (que la función de compresión no alarga el archivo) es necesariamente falsa.
https://en.wikipedia.org/wiki/Lossless_compression#Limitaciones
Eres capaz de añadir valor a nuestra información dando tu experiencia en las anotaciones.