Theorem:
No program can compress without loss *all* files of size >= N bits, for any given integer N >= 0.
Proof:
Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
Aus dem comp.compression FAQ.
No program can compress without loss *all* files of size >= N bits, for any given integer N >= 0.
Proof:
Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
Aus dem comp.compression FAQ.
integrator - am Freitag, 28. Februar 2003, 14:15 - Rubrik: Beweise
