They don't necessarily use the same budget. The compressor can come prepackaged or be downloaded from a fast connection, and then be used when you have poor mobile internet.
They don't necessarily have to, that's true. But if there was any appetite to have gargantuan 500MB+ decompression libraries to save 20 or 30% on downloaded bytes while browsing, we would have seen much more uptake of existing simpler compression schemes like SDCH which takes a tiny step in that direction with a relatively large (but still tiny) pre-built dictionary for the WWW.