Comment by evo | Hacker News Reader

Comment by evo | Hacker News Reader

Parent Full thread

I would imagine that there is no exponential form that would take up less space in all cases than the original offset itself. You could think of the "exponential form" as a sort of compression algorithm with the same pitfalls as the latter, some exponential forms will end up taking more space than the original offset.

Furthermore, I would guess the offset has even less entropy on average than the bitsequence you're hoping to compress, so if you had an algorithm that would shorten the expression of the offset you might very well be able to apply it to the original bitsequence with the same or better results.

I'd think an information theory expert could probably tackle these sorts of questions very rigorously, but I am not one so this is mostly conjecture.

You are absolutely right, and the argument is the same as why there cannot be a compression algorithm that compresses something without making something else larger.

Namely that there are 2^n possible signals with n bits, so if a compression algorithm compresses some signal that is larger than n bits down to n bits or less, then there aren't enough possibilities left for all possible signals of at most n to also be encoded with n bits or less.

Indeed he is correct. But I would like to note that you can cap how much space you waste on incompressible things, though. Just store a flag with it that indicates whether that chunk of data is incompressible and don't even try to compress the incompressible things. The decoder for that is simple: read the flag (which only has to be 1 bit) and decompress it if it was compressed, or just return the unchanged data otherwise.

However, you'll still find that there are still limits to exactly how much you can compress things. And you'll find that, sometimes when you think you've found something that looks like it should be able to compress things down to nothing, that you've just been hiding the data in your decompression program.

In a sense, when you consider special-purpose compression and decompression functions, it's not unlike how "RETR some_huge_file.rar" sent to an FTP program will "decompress" that tiny string into some multi-GB file. But that only works because the program already has a copy of the data.

Reply on news.ycombinator.com