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.
