Teoría: ¿Algoritmo de compresión que hace que algunos archivos sean más pequeños pero ninguno más grande?

Question

Encontré esta pregunta;

"Un algoritmo de compresión sin pérdidas afirma garantizar que algunos archivos sean más pequeños y no hay archivos más grandes.
Es esto;

a) imposible

b) posible pero puede funcionar por una cantidad de tiempo indeterminada,

c) posible para el factor de compresión 2 o menos,

d) ¿Posible para cualquier factor de compresión? "

Me estoy inclinando hacia (a), pero no pude dar una explicación sólida de por qué. (Enumeré los pensamientos que un amigo y se me ocurrió como una posible respuesta)

Answer 1

Según el principio de agujero de paloma, dada una cadena de 10 bits, tiene 1024 entradas posibles y necesita asignar a 9 bits o menos, por lo que hay <1024 salidas.

Esto garantiza que el algoritmo tiene colisiones (compresión con pérdida) o en algún momento elige devolver la entrada no modificada como salida.

En el último caso, no puede determinar cómo descomprimir una cadena arbitraria de bits. (Podría ser una entrada no modificada o una salida comprimida de una cadena de bits más grande).

-> imposible.

Answer 2

Solo una ligera aclaración de la publicación de Rjfalconer ...

Solo tienes que tener alguno Los archivos se vuelven más pequeños, por lo que la afirmación de que una cadena de 10 bits tiene que asignar a 9 bits o menos no es del todo correcto. En particular, si alguien propuso tal mecanismo de compresión, pudo Mapee todas las cadenas de 10 bits o menos a exactamente la misma salida (es decir, una transformación de identidad).

Sin embargo, se nos dice que hay al menos un archivo que se vuelve más pequeño. Sin pérdida de generalidad, considere eso para comenzar con X bits y terminar como y bits, donde Y es estrictamente menor que x.

Ahora considere el dominio de "archivos con y bits o menos", que tiene 2^y+1-1 cadenas de bits (incluida la vacía). Para que ninguno de ellos resulte en un archivo más grande, cada uno tiene que mapear una cadena de bits en el mismo dominio, es decir, 2^y+1-1 Archivos comprimidos. Sin embargo, ya sabemos que la cadena inicial de longitud x bits se comprime a uno de esos valores, dejando solo 2^y+1-2 valores posibles.

A este Punta el principio del hoyo de la paloma: claramente no puedes mapear 2^y+1-1 entradas a 2^y+1-2 salidas sin repetir una salida, que viola la reversibilidad de la compresión.

Answer 3

a) imposible

Si tiene un archivo que no se puede comprimir más, aún debe agregar la información si se ha comprimido o no, por lo que en ese caso el archivo tendría que crecer.

Answer 4

Sé que llego un poco tarde, pero encontré esto a través de Google y alguien más podría hacer lo mismo, así que publicaré mi respuesta: la solución obvia es a) impossible, así como Jon Skeet (y por cierto, hay muchas pruebas en Internet). No estoy cuestionando la imposibilidad de comprimir datos aleatorios, solo para ser claros desde el principio; Entendí la teoría que queda detrás de esto, y -Se me preguntas, confío en las matemáticas. : D

Pero, si se nos permite Piense lateralmente, definitivamente podríamos aprovechar el hecho de que la pregunta no está bien definida, lo que significa que no da una definición estricta de "algoritmo de compresión" y de las propiedades que debería tener (sino para reducir alguno archivos sin expandir a nadie más).

Además, no pone en absoluto condición en los archivos para comprimirse, lo único que le interesa es "Para hacer que algunos archivos sean más pequeños y no hay archivos más grandes".

Dicho esto, ahora tenemos al menos dos formas de demostrar que, de hecho, existe un algoritmo así:

1. Podemos explotar el nombre del archivo para almacenar parte de la información del archivo (o incluso el archivo completo, si el sistema de archivos lo permite, reduciendo así cada archivo a 0 bits). Trivialmente, podríamos simplemente decidir dejar no tocarse cada archivo, excepto uno, reducirlo a 0 bits y renombrarlo con un nombre predefinido. Estoy de acuerdo en que esto podría considerarse trampa, pero de nuevo, no hay restricciones en la pregunta inicial y este algoritmo alcanzaría efectivamente el propósito (siempre que nadie cambie el archivo, por eso esta sería una opción de diseño muy pobre además de siendo inútil).

2. Podemos limitar el número de archivos que se comprimirán, por ejemplo, a los que al menos X bits de largo. Una vez más, una solución trivial sería dejar cada archivo intacto pero uno, para que podamos reducir hacer que coincida con un archivo más pequeño que X bits. Ahora hacemos Tener un algoritmo que, citando textualmente, hace que algunos archivos sean más pequeños y no hay archivos más grandes; Sin embargo, realiza una restricción en todas sus entradas posibles (es decir, no puede procesar todos los archivos).

Para aquellos que argumentan que esto no tendría ningún uso práctico, digo que estoy de acuerdo contigo ... pero bueno, esto es teoría, y esto fue solo una disertación teórica. ;)

Obviamente, si tuviera que hacer una prueba y enfrentar esta pregunta, pondría una X audaz en el a), y luego continúa sin pensar demasiado en eso.

Sin embargo, es perfectamente posible demostrar que, dado que el lenguaje natural es intrínsecamente ambiguo y la pregunta no se expresa formalmente, cada una de las otras respuestas posibles no es necesariamente incorrecta: colocar las condiciones correctas y eventualmente especificando más claramente lo que se entiende por ciertos conceptos , legalmente, podemos cumplir con el objetivo de cualquiera de las otras opciones enumeradas, haciendo algún tipo de truco y obligando al programa a lograr el comportamiento deseado.

Answer 5

e) posible

... con algunas restricciones.

Recientemente me encontré Shoco, una biblioteca de compresión de cadena para pequeñas cadenas. Recordé esta pregunta al leer esta afirmación:

... La propiedad más notable de Shoco es que el tamaño comprimido nunca excederá el tamaño de su cadena de entrada, siempre que sea ASCII simple.

Si está seguro de que los datos de entrada son simples ASCII, su búfer de salida solo debe ser tan grande como la cadena de entrada

http://ed-von-schleck.github.io/shoco/#how-it-works

Answer 6

posible

to make some files smaller and no files larger

Si dicho algoritmo de compresión hace que el archivo sea más grande, solo haga que devuelva el archivo original.