How would the use of an external lookup table affect file compression?

Question

It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My understanding of the way compression algorithms work, is that they create this mapping dynamically, with things like huffman coding being used to create the lookup table.

And so I wonder: if a general lookup table was pre-built, and not derived in any way from the input file, how would this affect the compression? My guess would be that if would make the compression slightly less effective (because the ordering of the mappings would not be optimized for the specific case), but would make it much faster to run, since it doesn't need to build the table as it goes.

Answer 1

There are compression programs such as zstd which explicitly allow a separate dictionary text, and stream-based compressors such as LZW can be easily converted to use a dictionary by prepending it on the input. The dictionary appears as a fixed prefix on the output and can be removed, ie $C(xy)=C(x)C(y|x)$.

The benefit of using one text as a dictionary for another is a function of their mutual information, which is based on Kolmogorov Complexity (an incomputable minimum). However a compression algorithm turns out to be a good way to approximate it, using a technique known as Normalized Compression Distance. The texts are compressed separately and together as above, and the difference between $C(y|x)$ and $C(y)$ measures similarity. So, while it's difficult to predict the benefit, measuring it empirically has some uses.

Answer 2

It depends on the algorithm being used. Something like Huffman coding works by assigning variable length codes to the different symbols, so you could absolutely do what you suggest. The effect would be exactly as you say: compression would be a bit faster, but the compressed file would be larger because the code lengths wouldn't be optimized to that specific file.

However, for dictionary-based compression algorithms such as LZW, this approach doesn't really make sense. These work, essentially, by having a list of known sequences, which may as well start as the empty list. Now, start reading the file. Each time you see a sequence that is a known sequence plus one more character, that becomes a new known sequence and is entered into the dictionary. You then compress the file by writing out the indices of the known sequences it contains. This is tied very closely to the actual data that you're trying to compress and it barely makes sense to try to come up with a global dictionary.