2 ms·
You can't compress any arbitrary file, but there are lots of files you can compress. Proof for the first part (aka the Pigeonhole Principle): look at the unive
by dsr_ 14y ago
You can't compress any arbitrary file, but there are lots of files you can compress.
Proof for the first part (aka the Pigeonhole Principle): look at the universe of files that are 100 bits long. Apply your compressor to each one, so that you have reduced the length of each file to 99 bits. But the number of 99-bit long files is half the number of 100-bit long files, which means that for some of your compressed files, you can't tell exactly which 100-bit long file it corresponds to.
Now, you can perform run length encoding on some files. That looks for runs of repeated bits, replaces them with a special marker, and writes a dictionary to translate the marker to the run. You can look for patterns. This will work... on some files. Not on all.
A good compressor will try several different encoding schemes to do its work, and is going to succeed on files with embedded patterns. For instance, if the file is ASCII text, lots of bit patterns will never occur, and lots will occur repeatedly. If the file is English ASCII text, even more redundancy can be exploited. If the file is a structured data set, there's almost certainly a bunch of repeating patterns.
But for purely random data, there won't be enough patterns repeated enough to exploit.