Wow, really? I always assumed that if I zipped a directory, it would use a shared dictionary to compress all the files. But I guess what you say makes sense, because otherwise it wouldn't be possible to extract just one file.
Are there compression formats that do share an encoding dictionary across multiple files? I guess tar + gzip might do that?
Yeah, if you compress a tar file with gzip (or bzip2 or zstd or whatever) then the compressor doesn't care about the file boundaries, so it will be able to take advantage of redundancies.
However, those compressors generally only have a small context window, so they'll only be able to take advantage of relatively nearby redundancies in the archive. They won't help you if the common substrings are separated by many megabytes of unrelated data. So the order in which you pack the files matters.
In theory, you could do a two-pass approach, where you first scan the entire set of files to create a (relatively small) shared dictionary that's as useful as possible, and then uses that dictionary to compress each file independently. I don't know of any archive format that does that, but you could roll your own using the zstd command line compressor.
Are there compression formats that do share an encoding dictionary across multiple files? I guess tar + gzip might do that?