3 ms·
> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem. I don't se
by BigTTYGothGF 4mo ago
> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem.
I don't see why that would be relevant here. The goal is to find the best compression of a given source among all possible DEFLATE streams, not to find the best compression of a given source among all possible ways to compress data. There are only so many DEFLATE streams shorter than the original source, you "simply" try them all, and then you've halted. That said:
> Now, Zopfli is the software that performs an exhaustive search across all possible syntactically valid streams
Maybe I don't understand LZ77 as well as I thought, but surely the search space is way too big to exhaust?
- dj_axl 4mo agoToo big to exhaust... the concluding sentences of the article contain the details. "Hybrid search with pruning" is the current state of the codebase.
- BigTTYGothGF 4mo agoThat's where OP ended up, I was disputing the description of zopfli.
- ghssds 4mo ago> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem. That sentence was pasted unmodified from the LLM output.