Hacker News Reader

Comment by DougWebb | Hacker News Reader

There's bound to be an exponential form for the offset which would take up a reasonable amount of space. eg: 2^100^100 takes up just 9 bytes, but if I wrote it out longhand it would be over 3000 bytes. Remember that it doesn't have to be human readable either; the 2 could be assumed and the 100's could be \x64\x64, just two bytes. In that form, you have a compact way to express large numbers, and any offset could be expressed as a sum of some such numbers.

I think the real problem, as you said, is having a copy of the full sequence around for encoding and decoding, and finding any given string of bits within it.

View on HN

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.

The problem is information content. 2^100^100 is a special case: what if I want 2^100^100+1? or (2 * 10^100) + (1 * 10^99) + (3 * 10^98) + (7 * 10^97)... it would be much shorter to write that in its regular decimal form 2,137,... So to specify a sequence, you would (on average, not for special cases like the one you picked) need just as much information as there is in the sequence!

Reply on news.ycombinator.com