Unless you're really, really good with information theory, I doubt you could come up with something better than a general-purpose compression algorithm. Take a look at the Compress:: modules, particularly Compress::Zlib and Compress::Bzip2. These will probably reduce the space by a lot more than most customized solutions, and will probably be easier to code.

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

Note: All code is untested, unless otherwise stated