Here's a silly trick we used for a similar problem: use zlib with a custom compression dictionary. Our application had tons of interlinks (think linked data) that we wanted to expose to the end user, but putting urls in urls is kinda ugly. So we ended up with our own custom compression dictionary and pushing them through zlib. Works like a charm.