4 ms·

Then how would you find redundancy in arbitrarily large random data?

• ars 14y ago
  See my comment http://news.ycombinator.com/item?id=5025527 http://news.ycombinator.com/item?id=5025527 This is a misunderstanding of the pigeonhole principle, which only applies to a specific compression algorithm. It does NOT apply if you get to write a custom algorithm for this data set. There are always redundancies in random data. If you can pick them out ahead of time with a custom algorithm it's certainly possible to "compress" it. Edit: I think I may be wrong here.
  • jessaustin 14y ago
    ...except in this case a complex custom algorithm will make the decompressor bigger which will count against your total size.
  • CJefferson 14y ago
    Except, that 'specific compression algorithm' could be "attach an x86 program to your compressed data, which I will run", which then covers all algorithms you might care to submit.