> And there are theoretical limits to what you can do with lossless compression and I suspect that the algorithm in the show breaks those.
Compression schemes achieve better results the more they're tailored to the data you're compressing. The theoretical limits are not the issue.
For example, here's my compression algorithm for popular movies: You take the most popular 255 movies of all time as of a particular date and include an uncompressed copy of all of them within the compression algorithm itself. Then the compression scheme works as follows: If the first byte is not a zero, the decompression code will emit one of the 255 most popular movies, and the 255 possible non-zero values for the first byte identify which one. If the first byte is a zero, what follows is an uncompressed copy of a movie that is not one of the 255 most popular movies, and the decompression code merely strips the first byte.
Using that algorithm I can compress each of the 255 most popular movies into a single byte. That's basically the theoretical limit. You could create a compression algorithm that could compress every film ever released into maybe three or four bytes. The problem is naturally that such an algorithm is a) completely useless for all the films that haven't been released before the algorithm is created, and b) completely impractical because the compression algorithm itself is far too large to be distributed or stored efficiently. Because it's a trade off, and achieving the theoretical limit for data size takes the trade off too far in the direction of specializing the algorithm to the data.
But that doesn't mean there can't exist algorithms that make a more interesting trade-off than the existing ones do. Suppose you specifically design a compression algorithm for music. It's pre-programmed with the sounds made by common musical instruments and that are common in human singing. If the recording contains a guitar playing a G#, the algorithm identifies it as a guitar playing a G# and calculates the difference in pitch, volume, tempo, etc. between the recording and the idealized note built into the algorithm. That would be a significantly more complicated compression algorithm than most of those currently used, and it probably wouldn't get very good compression ratios for recordings of things other than music, but you would have something that could conceivably compress most music better than existing compression algorithms.
1. I think that's why they generally include the size of the decompressor in compression contests.
2. Great points re domain, but on the show they specifically say that the algorithm is general purpose, and the talk about using it for compressing images, documents, etc. I don't know about you, but I don't have any G#s in my excel spreadsheets. ;-)
So maybe it's meta. Instead of being a compression algorithm, how about a machine learning algorithm that takes a corpus of data and generates a compression algorithm specialized to compress that type of data. You train it against music and get an algorithm suited for compressing music, you train it against spreadsheets and you get an algorithm suited for compressing spreadsheets, etc.
Compression schemes achieve better results the more they're tailored to the data you're compressing. The theoretical limits are not the issue.
For example, here's my compression algorithm for popular movies: You take the most popular 255 movies of all time as of a particular date and include an uncompressed copy of all of them within the compression algorithm itself. Then the compression scheme works as follows: If the first byte is not a zero, the decompression code will emit one of the 255 most popular movies, and the 255 possible non-zero values for the first byte identify which one. If the first byte is a zero, what follows is an uncompressed copy of a movie that is not one of the 255 most popular movies, and the decompression code merely strips the first byte.
Using that algorithm I can compress each of the 255 most popular movies into a single byte. That's basically the theoretical limit. You could create a compression algorithm that could compress every film ever released into maybe three or four bytes. The problem is naturally that such an algorithm is a) completely useless for all the films that haven't been released before the algorithm is created, and b) completely impractical because the compression algorithm itself is far too large to be distributed or stored efficiently. Because it's a trade off, and achieving the theoretical limit for data size takes the trade off too far in the direction of specializing the algorithm to the data.
But that doesn't mean there can't exist algorithms that make a more interesting trade-off than the existing ones do. Suppose you specifically design a compression algorithm for music. It's pre-programmed with the sounds made by common musical instruments and that are common in human singing. If the recording contains a guitar playing a G#, the algorithm identifies it as a guitar playing a G# and calculates the difference in pitch, volume, tempo, etc. between the recording and the idealized note built into the algorithm. That would be a significantly more complicated compression algorithm than most of those currently used, and it probably wouldn't get very good compression ratios for recordings of things other than music, but you would have something that could conceivably compress most music better than existing compression algorithms.