4 ms·
pngcrush doesn't actually brute force, for exactly the reason the article gives, it would take too long. Instead, pngcrush is using yet more heuristics to gues
by tialaramex 5y ago
pngcrush doesn't actually brute force, for exactly the reason the article gives, it would take too long.
Instead, pngcrush is using yet more heuristics to guess what else is likely to work and then trying some of the other options that wouldn't be picked by the defaults.
By default it only tries a few approaches that it deems most likely to work, but even with the "brute" parameter it does not truly try everything, again, that would take too long, and pngcrush "brute" is already very slow, it just tries all the methods it would ever have used on any image.
Actual brute force of a relatively tiny 32x32 image would require trying all five filters for each line in combination with each such filter for each other line or else you might miss a combination which, astonishingly, was smaller even though it wasn't immediately obvious why. I think that's 5 raised to the power 32 combinations.
- magicalhippo 5y agoIt 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 ?