r/askscience • • Jun 17 '12

Computing How does file compression work?

(like with WinRAR)

I don't really understand how a 4GB file can be compressed down into less than a gigabyte. If it could be compressed that small, why do we bother with large file sizes in the first place? Why isn't compression pushed more often?

414 Upvotes

146 comments sorted by

View all comments

Show parent comments

1

u/yatima2975 Jun 18 '12

Slight nitpick: you have to deal with the case that one of the three inputs is the result of doing (possibly repeated) compression on one of the other :)

The proof I've been taught goes as follows: there are 2n inputs of length n, and 20 + 21 + ... + 2n-1 = 2n - 1 messages of length strictly shorter. If a lossless compression algorithm existed, it would compress all 2n messages of length n into something shorter, which is impossible by the pigeonhole principle.

1

u/arienh4 Jun 18 '12

Slight nitpick: you have to deal with the case that one of the three inputs is the result of doing (possibly repeated) compression on one of the other :)

Frankly, that will happen at some point any way, because eventually the input is going to be one or zero. Otherwise, spot on. I think your proof is better, but might be a little harder to understand than ebix's.

1

u/ebix Jun 18 '12

if you make all of the inputs the exact size, then your algorithm strictly compresses, so no input can be the result of compression of any other.

1

u/yatima2975 Jun 18 '12

That works, indeed!

arienh4 left a very slight loophole, which can be fixed by replacing his bullet point 2 by "Take three large different inputs of the same size".