6 ms·

Wow, this is a incredible visualization of how compression works. I never understood how it worked before, but the simple mentioning of pointers and then that v

Wow, this is a incredible visualization of how compression works. I never understood how it worked before, but the simple mentioning of pointers and then that video was all it took for me. I've always wondered if this is true: If we approach infinite computational power, does the amount of information we need to represent data decrease? (Excuse any incorrect use of my terminology here.) I think about a number like pi that, as far as we know, has an infinite number of digits, and theoretically speaking every message is contained in that number. So if we just get the pointer of where that message is contained in the number and then calculate the number up to that pointer then we'll have ourselves the message. Hence, more computational power, less information needed.

ryanpetrich 13y ago
It's possible that for many messages, the pointer of the message into the representation of pi may actually be larger than the message itself.
willvarfar 13y ago
There is a flaw in your random sequence approach; lets see if you can find it? Its a fun thinking exercise. You can estimate the minimum bound on compression using Shannon's estimate http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) An excellent problem for hobby coders is the Hutter Prize. Even if you don't win - and that'd be front page HN news if you did - its a really fun challenge and an excellent introduction to compression: http://prize.hutter1.net/ http://prize.hutter1.net/ Also worth googling is Kolmogorov complexity.
sillysaurus2 13y ago
There is a limit beyond which you can't compress data any further, called the Shannon limit. Any sequence of bytes is just a number. So if you think of pi as an RNG, then the chances of finding a run of N digits equal to another number with N digits is (1/10) to the power of N, which quickly becomes intractible. In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. It would be easier to search for that number by randomly seeding an RNG then searching the RNG output for the number. Then you could just store the seed+offset, which may be significantly less than the Shannon limit. But since the chance of encountering such a number is (1/256)^N, it quickly becomes impossible. And even if it weren't, the receiver would need to invoke the RNG [offset] times, which will be a massive number of times due to the probabilities involved. So it's not like you could precompute the index: the receiver still needs to compute the answer, which requires just as many computations as the sender. In general, the closer you try to get to the Shannon limit, the more computation that is required. And perfect compression is impossible in practice except in constrained cases, so I'd speculate it requires infinite computational resources.
- wging 13y ago
  >In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. This is actually not known to be true. In fact, it's conjectured that pi is normal[1]--meaning that we should expect every sequence of digits of a given length to be as likely as any other, no matter what base we're using. So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. Where this fails, of course, is that you're likely to have to search a long time to find your message in pi, and you're also probably unlikely to be able to express your starting offset in fewer bits than it would take to write your full message. [1] http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number
  - sillysaurus2 13y ago
    So pi containing 3.141592653579 is equally likely as pi containing 1415926535797, which is equally likely to contain ABCDEFGHIJKL for every random ABCDEFGHIJKL? Fascinating. Completely impossible to take advantage of, too, but fascinating.
    - dbaupp 13y ago
      If the conjecture of being normal is true, yes.
    - weavie 13y ago
      Hmm.. it would also mean that somewhere in pi there is a sequence of 1 trillion consecutive zeros.
      - judk 13y ago
        http://en.m.wikipedia.org/wiki/Feynman_point http://en.m.wikipedia.org/wiki/Feynman_point
    - p4bl0 13y ago
      > Completely impossible to take advantage of That depends on your goals, to do geeky things it's pretty cool :). I know my birth date (in the "ddmmyy" format) appears at the 262768th decimal of π. By the way this example validates part of the answer of sillysaurus2 to mvleming: I need 6 digits to encode 6 other. Not that good a compression.
danieldk 13y ago
So if we just get the pointer of where that message is contained in the number and then calculate the number up to that pointer then we'll have ourselves the message. As others have pointed out, the pointer would be longer than the original text in many cases. It's very easy to express in layman's terms why perfect compression does not exist. If you had a compression algorithm that compressed every piece of data, it would introduce non-determinism. Say you had 4 bits (16 possibilities) and always compressed to fewer than 4 bits (8 possibilities), then one or more compressed datapoints would map to multiple uncompressed datapoints. Or in other words, you would lose information. For a nice, format description, see Shannon's original paper: http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948...
tlarkworthy 13y ago
Kolmogorov complexity captures your example. Kolmogorov complexity is the length of the shortest computer code that encodes a sequence. So the digits of Pi has a low computational complexity, because short programs exist that iteratively estimate PI. Random sequences have a high Kolmogorov complexity as their are no ways of generating the data. Kolmogorov complexity measures the compressibility of a sequence. Its related to the information content, and is NP-Hard to compute! The measure that takes into account the time to compute a sequence is the newer measure called "logical depth", but I only heard about that last week. The sequence of Ramsey numbers would have be very logically deep. A short program exists, but it takes forever to computer. The logical depth captures the amount of time you are saved by having the sequence precomputed.
rmc 13y ago
It's impossible to have a lossless compression system that will always compress anything down to less size than it was originally, otherwise you could run it as many times as you want and compress everything down to 1 bit. This includes "pointer to pi digits". What would probably happen there is the byte representation of the offset would be longer than the input string itself! Although, now for curiousity, I'd like to actually try that "offset in pi" algorithm. :) Just for fun.
- tjgq 13y ago
  Not to spoil your weekend project, but someone's done it already :) https://github.com/philipl/pifs https://github.com/philipl/pifs
apw 13y ago
It would be better to say that this is a visualization of how a certain kind of dictionary compression works. The outer limits of data compression lie in using predictive models plus arithmetic coders. A visualization of how they work might look very different.

ryanpetrich 13y ago

It's possible that for many messages, the pointer of the message into the representation of pi may actually be larger than the message itself.

willvarfar 13y ago

There is a flaw in your random sequence approach; lets see if you can find it? Its a fun thinking exercise. You can estimate the minimum bound on compression using Shannon's estimate http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) An excellent problem for hobby coders is the Hutter Prize. Even if you don't win - and that'd be front page HN news if you did - its a really fun challenge and an excellent introduction to compression: http://prize.hutter1.net/ http://prize.hutter1.net/ Also worth googling is Kolmogorov complexity.

sillysaurus2 13y ago

There is a limit beyond which you can't compress data any further, called the Shannon limit. Any sequence of bytes is just a number. So if you think of pi as an RNG, then the chances of finding a run of N digits equal to another number with N digits is (1/10) to the power of N, which quickly becomes intractible. In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. It would be easier to search for that number by randomly seeding an RNG then searching the RNG output for the number. Then you could just store the seed+offset, which may be significantly less than the Shannon limit. But since the chance of encountering such a number is (1/256)^N, it quickly becomes impossible. And even if it weren't, the receiver would need to invoke the RNG [offset] times, which will be a massive number of times due to the probabilities involved. So it's not like you could precompute the index: the receiver still needs to compute the answer, which requires just as many computations as the sender. In general, the closer you try to get to the Shannon limit, the more computation that is required. And perfect compression is impossible in practice except in constrained cases, so I'd speculate it requires infinite computational resources.

wging 13y ago
>In reality the digits of pi are biased, so finding a particular number of N digits is even less likely. This is actually not known to be true. In fact, it's conjectured that pi is normal[1]--meaning that we should expect every sequence of digits of a given length to be as likely as any other, no matter what base we're using. So if you know the position at which the string you're interested in appears, you can just 'compress' by giving the location in the binary expansion of pi at which your message appears, and the length of your message in bits. Where this fails, of course, is that you're likely to have to search a long time to find your message in pi, and you're also probably unlikely to be able to express your starting offset in fewer bits than it would take to write your full message. [1] http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number
- sillysaurus2 13y ago
  So pi containing 3.141592653579 is equally likely as pi containing 1415926535797, which is equally likely to contain ABCDEFGHIJKL for every random ABCDEFGHIJKL? Fascinating. Completely impossible to take advantage of, too, but fascinating.
  - dbaupp 13y ago
    If the conjecture of being normal is true, yes.
  - weavie 13y ago
    Hmm.. it would also mean that somewhere in pi there is a sequence of 1 trillion consecutive zeros.
    - judk 13y ago
      http://en.m.wikipedia.org/wiki/Feynman_point http://en.m.wikipedia.org/wiki/Feynman_point
  - p4bl0 13y ago
    > Completely impossible to take advantage of That depends on your goals, to do geeky things it's pretty cool :). I know my birth date (in the "ddmmyy" format) appears at the 262768th decimal of π. By the way this example validates part of the answer of sillysaurus2 to mvleming: I need 6 digits to encode 6 other. Not that good a compression.

danieldk 13y ago

So if we just get the pointer of where that message is contained in the number and then calculate the number up to that pointer then we'll have ourselves the message. As others have pointed out, the pointer would be longer than the original text in many cases. It's very easy to express in layman's terms why perfect compression does not exist. If you had a compression algorithm that compressed every piece of data, it would introduce non-determinism. Say you had 4 bits (16 possibilities) and always compressed to fewer than 4 bits (8 possibilities), then one or more compressed datapoints would map to multiple uncompressed datapoints. Or in other words, you would lose information. For a nice, format description, see Shannon's original paper: http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948...

tlarkworthy 13y ago

Kolmogorov complexity captures your example. Kolmogorov complexity is the length of the shortest computer code that encodes a sequence. So the digits of Pi has a low computational complexity, because short programs exist that iteratively estimate PI. Random sequences have a high Kolmogorov complexity as their are no ways of generating the data. Kolmogorov complexity measures the compressibility of a sequence. Its related to the information content, and is NP-Hard to compute! The measure that takes into account the time to compute a sequence is the newer measure called "logical depth", but I only heard about that last week. The sequence of Ramsey numbers would have be very logically deep. A short program exists, but it takes forever to computer. The logical depth captures the amount of time you are saved by having the sequence precomputed.

rmc 13y ago

It's impossible to have a lossless compression system that will always compress anything down to less size than it was originally, otherwise you could run it as many times as you want and compress everything down to 1 bit. This includes "pointer to pi digits". What would probably happen there is the byte representation of the offset would be longer than the input string itself! Although, now for curiousity, I'd like to actually try that "offset in pi" algorithm. :) Just for fun.

tjgq 13y ago
Not to spoil your weekend project, but someone's done it already :) https://github.com/philipl/pifs https://github.com/philipl/pifs

apw 13y ago

It would be better to say that this is a visualization of how a certain kind of dictionary compression works. The outer limits of data compression lie in using predictive models plus arithmetic coders. A visualization of how they work might look very different.