We use the MBTiles format, a simple schema for storing binary tile data within SQLite databases, to package maps in a way that makes them more portable and pluggable. We're now working on compressing MBTiles - and finding that it's possible to reduce file size by up to 60% without a 'decompression' phase and while retaining backward compatibility, which is key for our new MapBox for iPad app.
We found that using a database format as a file format has a fascinating benefit - one can replace the existing data layout with a better one, but keep the same interface. And that's exactly what we're doing with compression - replacing a table called 'tiles' with a view of the same name that returns the same results, therefore maintaining compatibility with MapBox for iPad and Maps on a Stick.
The strategy is a simple version of sliding window compression, the basis of zip, 7zip, and other popular formats. Given an existing tileset, it scans through 2,000 tiles at a time and consolidates repeated tiles, like those representing land and simple terrain. The result is a much-smaller file, especially given vector data like World Light with deep zoom levels.
The compressed MBTiles files are approaching the size of zipped MBTiles files - so it may be possible soon to distribute all tiles in this raw format. For the time being you can expect to see tilesets consume much less space on computers and devices.
The code is BSD-licensed on GitHub and only requires a recent version of Python. It's also a good idea to check out the MBTiles spec itself for working with the format. We'll be transitioning public tilesets and the World Light tiles included with MapBox for iPad and Maps on a Stick to this format.