2 ms·
It could also use a look-ahead scheme. That is, cloning the compression state, compressing the current line for each of the different filters, retaining the sta
by magicalhippo 5y ago
It could also use a look-ahead scheme. That is, cloning the compression state, compressing the current line for each of the different filters, retaining the state that lead to the highest compression and discarding the others.
This could be trivially extended to multiple lines of look-ahead, though at exponential memory and CPU cost.
Probably dog slow though.
- tialaramex 5y agoThe simplest of these schemes is pretty fast, only five times slower than the naive approach. But it absolutely doesn't give you the benefit from trying all the combinations and I expect it will produce worse results than existing tools. The problem is, while you know which outputs compressed best so far you can't be sure which will compress best in combination with future outputs you haven't as yet filtered. Imagine for example that one filter for the current row gives what seems like a random sequence that doesn't compress very well. Your proposed scheme rejects this filter, it compressed poorly, so don't use it. But, what if it turns out that every future row can be compressed to the exact same sequence with some other filter? Deflate can compress the rows extremely well together, even though the first one on its own did not compress.
- magicalhippo 5y agoObviously local approaches can fail to find the global minimum. This is mitigated somewhat though I imagine by the limited 32kB window deflate has. Would be a fun weekend project...
- userbinator 5y agoI haven't looked into the theory of it much, but wouldn't the local minimum also be the global one? In your example, even if the first row is more poorly compressed with one filter, could future rows "catch up" the loss? Unless you have a specific counterexample, I don't think it can, because the filtration operates before compression and there's no feedback as such.
- tialaramex 5y ago> I don't think it can, because the filtration operates before compression and there's no feedback as such. The compressor consumes the entire filtered data. You may have been thinking it goes something like Compress(Filter(row1,method=2)).Compress(Filter(row2,method=4)).Compress(Filter(row3,method=1)) and so on. But that would be terribly wasteful. What they do is actually closer to Compress(Filter(row1,method=2).Filter(row2,method=4).Filter(row3,method=1) and so on Does that make it clearer that if the results of two Filter steps are more or less similar, even if those results compress badly on their own, it helps them compress better when they're both nearby ?