Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lossless GIF recompression via exhaustive search

blog.arusekk.pl

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Lossless GIF recompression via exhaustive search

#11

Post by dj_axl »

BigTTYGothGF wrote: post #10

> 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…

Too big to exhaust... the concluding sentences of the article contain the details. "Hybrid search with pruning" is the current state of the codebase.

Re: Lossless GIF recompression via exhaustive search

#12

Post by ghssds »

BigTTYGothGF wrote: post #10

> 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…

> 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.

Re: Lossless GIF recompression via exhaustive search

#15

Post by BigTTYGothGF »

dj_axl wrote: post #11
BigTTYGothGF wrote: post #10

> 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…

Too big to exhaust... the concluding sentences of the article contain the details. "Hybrid search with pruning" is the current state of the codebase.

That's where OP ended up, I was disputing the description of zopfli.

Re: Lossless GIF recompression via exhaustive search

#16

Post by EliasWatson »

gsquaredxc wrote: post #4

> Here I should note that Python is not the best choice for CPU-bound software. I want to take the opportunity to learn Zig. For optimizing CPU-bound operations in Python, there’s some low hanging fruit with numba. I would recommend this as a 5-minute solution to you limiting your algorithm because regular Python is too slow. I regularly tell people that if their Python program is slow enough to take several minutes,…

For exhaustive searches, a library like or-tools or clingo can speed things up a lot. But first you have to figure out how to express your problem declaratively.
Post reply on HN