A file compressor is great for shrinking stored files, but it depresses me whenever I see a file grow instead of shrink. So what I am looking for is a file compression algorithm that never inflates any files, although it is allowed that some files (not all of course!) have the same length after "compression". Ideally it should work on files of all sizes, but I would be satisfied with a compressor that operates only on files larger than 1MB. Can you provide such an algorithm? No programming knowledge is required for this problem.

(In reply to re: No impossibility -- doubt it by Federico Kereki)

I took the sentence "I would be satisfied with a compressor that operates only on files larger than 1MB" literally.  Then the compressor would never encounter files under that size.  Admittedly that is only one interpretation of the problem.  The decompressor would then replace any zero-length file with the special fixed file.

I think the problem can be solved only if the file size or the file name is used to transmit additional information.  In order to use the file size, the size of the file to be compressed has to be restricted in some way.  I think otherwise the proofs below (that there is no solution) remain valid.

Posted by vswitchs on 2006-10-22 11:53:14