Comment by Natsu | Hacker News Reader

Comment by Natsu | Hacker News Reader

Parent Full thread

This sort of discussion often leads to someone wondering why it can't be used as a compression scheme, especially when you can calculate hexadecimal digits of pi without calculating any of the previous digits.

The first problem with that is finding the desired content somewhere in the number. You can't just Google it. In fact, I know of no way to search for it except for brute force (i.e. continue to calculate pi until such time as you find it). Because the odds are so low for any reasonably sized file, this is going to take a long time. Even if you measure using a scale where one unit is the current age of the universe, you would find the scale to be too small.

Even if someone solves that problem, the other problem is file size. You have to store offset and length. The length for most files would be reasonable, the problem is the offset. In all probability, that number is larger than your original file. Much larger. There are exceptions, of course, but not enough of them to help.

That said, I wonder how long it will be before some mathematician starts writing theorems about the "set of illegal numbers" like the 09F9 number and the rest.

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.

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