Compression algorithm using key value mapping

Question

Would it be possible to do better than standard compression if you fed a bunch of zipped files through a machine learning algorithm that kept track of the most common bit sequences and produced a lookup map, with a heuristic for giving the longest / most commonly used sequences the shortest key values?

The compression algorithm would then go through a zip file and replace sequences from the map with their lookup key. If the map was big enough (both compress / decompress parties would have access to it) could you reliably get a smaller file than the original?

Some doubts I have about this method:

• Files your learning algorithm had never seen before wouldn't contain many sequences that had been seen before
• The keys would have to be smaller than the sequence of bits it replaces in order to save space, maybe it quickly runs out of keys smaller than common sequences
• Zip files don't repeat bit sequences very often so we wouldn't be able to find large pieces to replace

Answer 1

All of your doubts are correct.

What you're describing is called static-dictionary compression. It works well for short text strings (see smaz, for example, though I doubt that its fixed dictionary was obtained by machine learning).

It would probably not accomplish much when applied to zip files because deflate doesn't tend to produce common bit sequences that are long enough to be further compressed – because eliminating those sorts of sequences is essentially its job.

A weakness of deflate is that its maximum copy length is 258, which means that long repeating sequences of bytes will tend to produce repeating (offset,length) pairs in the output, which can be further compressed by another pass. But the encoding of the repeated (offset,length) pair varies from file to file (even the length part, because the bit pattern used to represent a length of 258 isn't fixed), so you would need a dynamic dictionary to benefit from this.