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

2

u/TwirlySocrates Jun 18 '12

Why would a compression algorithm neccessarily be able to compress anything to one bit? A compression algorithm recognizes repetition and patterns, but if you compress something into a stream of bits that is otherwise indistinguisheable from noise, it shouldn't be compressible anymore, no?

1

u/arienh4 Jun 18 '12

The premise of the proof is that there is an algorithm that compresses any input, making the input at least one bit smaller while being reversible, no matter what that input may be.

If that premise is true, then it also applies to the output of the algorithm, so you can apply the algorithm recursively to compress any data down to one bit.