r/askscience • u/[deleted] • 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
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 lengthninto something shorter, which is impossible by the pigeonhole principle.