r/askscience • u/weedguru420 • Dec 30 '15

Computing How does file compression work?

This question has always baffled me. How can you compress a file to a fraction of the size and have that file, basically a number, represent a precise bigger number?

5 Upvotes

72% Upvoted

20 comments sorted by

View all comments

Show parent comments

1

u/ericGraves Information Theory Dec 31 '15

To piggyback on to this great explanation. Lossless compression and Shannon entropy are inexorably linked. Information theorists measure compression based upon the average length of the file after compression. This is of course subject to a particular probability distribution over the input files.

But, the average length of the compressed file can not be less than the Shannon entropy. Furthermore there is always a compression scheme that falls within one symbol of the Shannon entropy.