3 ms·
There's a great big unexplored area: Optimising the expression. I had a hack back in the previous millenium that improved on .tar.gz, compatibly. I think it us
by Arnt 11y ago
There's a great big unexplored area: Optimising the expression.
I had a hack back in the previous millenium that improved on .tar.gz, compatibly. I think it used find, but the current expression would be:
tar zcf $(file **/*(.) | sort -T: -k2 | cut -d: -f1)
The use of file is a bit of a hack, but the idea is good: let the compressor compress all of the source code together, without being distracted by dissimilar files. Ditto for other types.
Compressing a byte stream is not the same as compressing the data. Reordering a tar file doesn't change the meaning, and IMO the big, big gap in compression research is to identify such expression transformations.
Compression algorithms regard the input as god-given, but in reality much input can be reordered or otherwise transformed. The order of the files in a .tar could be reordered if the compressor could say anything about what's beneficial; the order of glyphs in a font could be reordered too. That sort of communication between the compression subsystem and the data source could be a very fruitful area of research.
- andrewflnr 11y agoThat's sort of what he was going on about with the Burrows-Wheeler transform, right?
- jacquesm 11y agoNow that's a clever trick. I just tried it on a random subdirectory here (a website source) and it actually made the resulting file larger so it may not always work but the idea makes sense. Wonder why it does not work in this case.
- Arnt 11y agoZlib and most others use dictionaries; the dictionary is adjusted as compression (and decompression) proceeds. When the input data type changes drastically, continuing with the formerly well-adjusted dictionary can actually be worse than issuing a flush and starting from scratch. I saw the same thing happen during the work on RFC 4978 (IMAP compression), which is why that RFC recommends issuing a flush before and after large attachments. A compression state based on typical IMAP chatter isn't good for compressing a random attachment, and one based on the attachment isn't good for compressing the IMAP chatter.
- baruch 11y agoCheck if the original was compressed with a higher level than you just did. Decompress the file and recompress and you should get the same file size.
- xamuel 11y agoWow, I've been thinking the exact same thing for a long time. In principle there's no need to limit it to file-level granularity. Take for example a JS minifier-compressor where human-readability isn't a goal. If you're compressing a javascript file with a bunch of top-level functions, it shouldn't matter which order the functions are expressed, thanks to hoisting. Once you make that jump, it's not even limited to re-ordering things. The minifier-compressor could also consider all possible results of swapping singlequote and doublequote, x['this'] vs. x.this when appropriate, and so on.
- gwern 11y ago> I had a hack back in the previous millenium that improved on .tar.gz, compatibly. FWIW, this is known as the 'sort key trick'. It's been in the folklore, as you say, for quite a while. I give some examples in http://www.gwern.net/Archiving%20URLs#sort---key-compression-trick http://www.gwern.net/Archiving%20URLs#sort---key-compression... for WWW archives. > Reordering a tar file doesn't change the meaning, and IMO the big, big gap in compression research is to identify such expression transformations. This hasn't been totally ignored. The problem is that you need to know and be able to specify in advance a useful ordering of input files to make up a better stream or a tool (like 'lrzip', designed to look for long-range correlations) must infer it which seems hard to do without requiring multiple passes; and what's the incentive? In a world in which RAR and ZIP and Gzip are still considered the standards and people aren't even using xz, no one wants to use such a niche tool for anything serious.
- Arnt 11y ago1. Well, there are people who serve web fonts and CSS sprite assets to about 10¹²³ people per hour and would go to some lengths to save a few bytes on those, even if it involves niche tools that many others don't bother with. 2. "What's the incentive" is IMNSHO a terrible question for a research area.
- gwern 11y ago> 1. Well, there are people who serve web fonts and CSS sprite assets to about 10¹²³ people per hour Those people have the problem that the delivery mechanisms are extremely limited and hardwired and a lot of the possible advances cannot be shoehorned into a DEFLATE-compatible bytestream or whatever it is IE6 supports... > 2. "What's the incentive" is IMNSHO a terrible question for a research area. Researchers are human too. It's demotivating to try to research fancier data compression techniques if you're certain that no one will ever use it.