You can't patent pure maths. Compression is pure maths, so how can it be patented?

Lossless compression algorithms - things like gzip, and bzip2 - are pure mathematical algorithms. If their mathematical transform is applied, and the inverse transform is applied to the result, you get back exactly to the point at which you started. Although the algorithm used to losslessly compress GIF images was patented in the USA, it appears such a thing should not be patentable in most countries.

Lossy music compression codecs, like MP3, and lossy image compression codecs, like JPEG or MPEG2, are not based on pure maths. They try to eliminate from the signal anything the auditory and visual systems can't pick up. The inverse transform does not get back to the starting point, but to something humans perceive as close to the starting point. Done well, and not too aggressively, this can reduce the amount of data substantially, and be barely perceptible. An MP3 file might sound fine to you, but to an animal with a different auditory system, it might sound like a poor match for the original sound. Speech codecs, like G.729, go further. They try to avoid wasting data encoding things your speech system can't produce. None of this is maths. There may be a lot of maths involved in the codec, but the techniques the maths is implementing are not pure maths at all. Methods of this type can be legitimately patented in pretty much any country with a patent system.