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:
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).
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.
Esto es sólo especulación. Apenas soy un experto en esto, solo quería ver lo que otros pensaban de mi respuesta. ¡Gracias! – RJFalconer
@BlueNovember: no se preocupe: * cada * usuario que se encuentra con un archivador eventualmente se pregunta si es posible hacer tal compresión :-) –
Hmm. No lo hice, Pavel. – spender