2 ms·

Not the same problem, but I have been on and off thinking about infinite/recursive compression and compression of random data. Finding patterns in numbers can b

• Retric 8y ago
  I have gone down such rabbit holes before. However, it's easy to demonstrate you can't compress arbitrary unbiased random data without going lossy. For every possible input 0 to X you need to map to a different 'compressed' format. So, if you want to handle every possibility then some of your compressed versions need to be as long if not longer than the original version. That's not a problem if their is some bias in how your generating the data. Just map the more common versions to shorter encoding and you get a useful compression even if sometimes it makes things worse on average their is an improvement. But, with unbiased random data you can't chose which subset is more likely because every version is equally likely. Which is why it does not work.
  • odonnellryan 8y ago
    To be said another way: certainly you can figure out a compression algorithm for any one set of data by being clever and taking your time, but that algorithm will not apply to a general case and would be worthless. If you go about finding patterns in a random string it is unlikely that another random string will have those patterns.
    • mojomark 8y ago
      Concur. Said yet another way, one data sets entropy is another data sets negentropy.