5
$\begingroup$

This is basically a recurring thought I have from time to time and I suspect it is flawed, so my question is basically why can't you do the following:

Basically, I imagine that given a seed and a random number generator, the binary result at a given length might have something in common with some target data that you want to compress. In the case that it just happened to be the same, you'd get a phenomenal amount of compression.

That said, I suspect this is in the same league as the perpetual motion machine I thought I invented when I was a kid (air lock at the bottom of a tube of water, ball floats to top and falls back down to air lock...)

$\endgroup$
4
  • $\begingroup$ The probability of any small seed generating exactly the output you are trying to compress is minuscule. So no, it won't work (except 0.0001% of the time). $\endgroup$
    – Alex Becker
    Jun 29, 2013 at 1:07
  • $\begingroup$ This basically comes down to whether you can find a pattern in your data and use just knowledge elf the pattern + a seed case to describe the data in the hope that takes less space $\endgroup$
    – Sidharth Ghoshal
    Jun 29, 2013 at 3:02
  • $\begingroup$ I just had this thought.. $\endgroup$
    – Austin Burk
    May 2, 2015 at 0:49
  • $\begingroup$ The random generator would have to create a mix of distorted vectors (trigo maybe) to fit real life organisation of things obeying to physics laws, maths laws, or other general organisation laws. Since you want to optimize it, that could not be totally random. It makes more sense in lossy compression. And probably we could say existing lossy video codec are kinda already using randomness, depending of our definition of 'random' and 'arbitrary'. In the other, an un-optimal - only random - algorithm would cover case where 'white noise' is compressed. $\endgroup$
    – Léon Pelletier
    Jul 8, 2015 at 14:00

3 Answers 3

Reset to default
6
$\begingroup$

"In the case it just happened to be the same" is the key. It will (almost) never happen. Say you have million bit strings. There are $2^{1000000}\approx 10^{301030}$ of them. If the string happened to be $\pi$, you would have a phenomenal amount of compression. That happens very rarely. If your random number generator is good, it will happen just as rarely. The compression we use reflects the non-randomness in the files we compress. There are tremendous correlations in text (because it is generated in natural language, not random) or photos (big areas are close in color). Compression takes advantage of that.

$\endgroup$
2
$\begingroup$

The randomness isn't essential in your argument; what you're really talking about is the idea of a function with small inputs having large outputs. So one idea is instead of doing random numbers, take a huge library of videos or images or code, etc. and analyze them to find frequently recurring patterns, and then make a list of those patterns. The location in that list is similar to the seed for a random number generator.

This has been done before; I went to a talk recently where they said the most common pictures in photographs were sharp lines, so they encoded ever instance of a line-like object (viewed as a subset of a five by five grid) in a list, and then decomposed photographs using these masks. It was really interesting and fun! I think Morse theory had been used similarly, but I'm not sure.

$\endgroup$
1
$\begingroup$

Consider this. If one small seed generates one long random sequence then it is impossible to create all possible sequences using a random function because for $n$ digit decimal seeds there can be only $10^n$ distinct possible sequences. If you have to create a sequence that doesn't belong to this set, you will have to use a different function... and in the end you will end up using just the same amount of data as the original sequence.

$\endgroup$
1
  • $\begingroup$ Amazing!! Thank you for this! This answers the heart of the question with a limiting principle! $\endgroup$
    – GDub
    Jul 5 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.