BUG80 schreef:
[..]
Klopt, helemaal mee eens, net als je theorie over WinZip in je andere reactie.
Maar stel nou dat films, net als tekst, geen willekeurige tekenreeksen zijn en daadwerkelijk een bepaalde "magische" redundantie bevatten die toch in één algoritme te vangen is.
Het is allemaal hypothetisch, dat is waar. Nogmaals, het enige dat ik probeer aan te tonen, is dat het in mijn ogen niet *wiskundig* te bewijzen is dat de compressie van Sloot onmogelijk is, ook al is het intuitief nog zo onwaarschijnlijk.
Het is gemakkelijk in te zien dat de verzameling mogelijke films groter is dan de verzameling "sleutels" van 64 kB. Je kunt (in theorie) bijvoorbeeld alle mogelijke reeksen van 65 kB op papier uitschrijven en van iedere reeks een film maken. Of iedere mogelijk plaatje genereren met een resolutie van 1000x1000 en van iedere plaatje een film maken. Met een sleutelgrootte van 64 kB worden verschillende films in deze voorbeelden op dezelfde sleutel afgebeeld.
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.
[...]
Note that no assumption is made about the compression algorithm. The proof applies to
*any* algorithm, including those using an external dictionary, or repeated
application of another algorithm, or combination of different algorithms, or
representation of the data as formulas, etc... All schemes are subject to the
counting argument. There is no need to use information theory to provide a
proof, just very basic mathematics.
(Bron)