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

Question

Me encontré con esta pregunta;

"Un algoritmo de compresión sin pérdida de reclamaciones para garantizar que hacer algunos archivos más pequeños y no hay archivos de más
es la siguiente:.

a) Imposible

b) Posible pero puede correr por una cantidad indeterminada de tiempo,

c) Posible para el factor de compresión de 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é. (Voy a enumerar los pensamientos de un amigo y se me ocurrió como una posible respuesta)

Answer 1

Por el principio del casillero, dado una cadena de 10 bits, tiene 1024 entradas posibles, y necesita asignar a 9 bits o menos, entonces 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 este ú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

Sólo una ligera clarificación del puesto de RJFalconer ...

es suficiente con tener algunos archivos cada vez 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 Muy bien. En particular, si alguien propuso un mecanismo de compresión de este tipo, podría asignar todas las cadenas de 10 bits o menos exactamente al mismo resultado (es decir, una transformación de identidad).

Sin embargo, nos dicen que hay al menos un archivo que se vuelve más pequeño. Sin pérdida de generalidad, considere que comience con x bits y termine como bits y, donde y es estrictamente menor que x.

Considere ahora el dominio de "archivos con y bits o menos", que tiene 2 ^{y + 1} -1 cadenas de bits (incluida la cadena vacía). Para que ninguno de estos genere un archivo más grande, cada uno debe asignar a 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.

En este punto, el principio del palomar viene en - que claramente no puede asignar 2 ^{y + 1} -1 entradas a 2 ^{+ 1} -2 salidas Y sin repetir una salida, lo que viola la reversibilidad de compresión

Answer 3

a) imposible

Si usted tiene un archivo que no se pueden comprimir más, usted todavía tiene que agregar la información de si se ha comprimido o no, por lo que en caso de que el archivo tendría que crecer.

Answer 4

Sé que estoy un poco tarde, pero encontré esto a través de google y alguien más podría hacer lo mismo, así que voy a publicar mi respuesta: la solución obvia es a) impossible, como señaló 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 subyace y, si me preguntas, confío en las matemáticas. : D

Pero, si se nos permite think laterally, 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 del propiedades que debería tener (pero para reducir algunos archivos sin expandir a nadie más).

Además, no se pone ninguna condición en los archivos para comprimir, lo único que le interesa es "para hacer algunos archivos más pequeños y sin archivos más grandes".

Dicho esto, tenemos ahora por lo menos dos maneras de mostrar que, de hecho, no existe tal algoritmo:

1. Podemos explotar el nombre del archivo para almacenar parte de la información de el archivo (o incluso todo el archivo, si el sistema de archivos lo permite, reduciendo así cada archivo a 0 bits). Trivialmente, podríamos simplemente decidir dejar intactos todos los archivos menos uno, reduciéndolo a 0 bits y cambiarle el nombre con un nombre predefinido. Acepto que esto podría considerarse una trampa, pero una vez más, no hay restricciones en la pregunta inicial y este algoritmo lograría efectivamente el objetivo (siempre y cuando nadie cambie el nombre del archivo, es por eso que esta sería una opción de diseño muy pobre además de ser inútil).

2. Podemos limitar el número de archivos a comprimir, 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 excepto uno, que podamos reducir haciendo coincidir con un archivo más pequeño que X bits. Ahora tenemos tenemos un algoritmo que, citando textualmente, hace que algunos archivos sean más pequeños y que no haya archivos más grandes; sin embargo, realiza una restricción en todas sus posibles entradas (es decir, no puede procesar todos los archivos).

Para quienes sostienen que esto no tendría ningún uso práctico, digo que estoy de acuerdo con usted ... pero bueno, esto es la teoría, y esto fue sólo una disertación teórica. ;)

Obviamente, si tuviera que hacer una prueba y enfrentar esta pregunta, pondría una X en negrita en el a), y luego continuaba sin pensar demasiado en ello.

Sin embargo, es perfectamente posible mostrar 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: colocando las condiciones adecuadas y especificando más claramente qué es significados por ciertos conceptos, legalmente podemos cumplir con el objetivo de cualquiera de las otras opciones enumeradas, haciendo algún tipo de engaño y forzando al programa a lograr el comportamiento deseado.

Answer 5

e) Posible

... con algunas restricciones.

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

... el más notable propiedad de shoco es que el tamaño comprimido nunca excederá el tamaño de la cadena de entrada, siempre y cuando sea en ASCII.

Si está seguro de que los datos de entrada es en ASCII, el búfer fuera por sólo tiene que ser tan grande como la cadena de entrada

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