Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange.

Here's a 14 year-old's scheme for an amazing compression algorithm:

Take a PRNG and seed it with seed s to get a long sequence of pseudo-random bytes. To transmit that sequence to another party, you need only communicate a description of the PRNG, the appropriate seed and the length of the message. For a long enough sequence, that description would be much shorter then the sequence itself.

Now suppose I could invert the process. Given enough time and computational resources, I could do a brute-force search and find a seed (and PRNG, or in other words: a program) that produces my desired sequence (Let's say an amusing photo of cats being mischievous).

PRNGs repeat after a large enough number of bits have been generated, but compared to "typical" cycles my message is quite short so this dosn't seem like much of a problem.

Voila, an effective (if rube-Goldbergian) way to compress data.

So, assuming:

  • The sequence I wish to compress is finite and known in advance.
  • I'm not short on cash or time (Just as long as a finite amount of both is required)

I'd like to know:

  • Is there a fundamental flaw in the reasoning behind the scheme?
  • What's the standard way to analyse these sorts of thought experiments?

Summary

It's often the case that good answers make clear not only the answer, but what it is that I was really asking. Thanks for everyone's patience and detailed answers.

Here's my nth attempt at a summary of the answers:

  • The PRNG/seed angle doesn't contribute anything, it's no more then a program that produces the desired sequence as output.
  • The pigeonhole principle: There are many more messages of length > k then there are (message generating) programs of length <= k. So some sequences simply cannot be the output of a program shorter then the message.
  • It's worth mentioning that the interpreter of the program (message) is necessarily fixed in advance. And it's design determines the (small) subset of messages which can be generated when a message of length k is received.

At this point the original PRNG idea is already dead, but there's at least one last question to settle:

  • Q: Could I get lucky and find that my long (but finite) message just happens to be the output of a program of length < k bits?

Strictly speaking, it's not a matter of chance since the meaning of every possible message (program) must be known in advance. Either it is the meaning of some message of < k bits or it isn't.

If I choose a random message of >= k bits randomly (why would I?), I would in any case have a vanishing probability of being able to send it using less then k bits, and an almost certainty of not being able to send it at all using less then k bits.

OTOH, if I choose a specific message of >= k bits from those which are the output of a program of less then k bits (assuming there is such a message), then in effect I'm taking advantage of bits already transmitted to the receiver (the design of the interpreter), which counts as part of the message transferred.

Finally:

Ultimately, both tell us the same thing as the (simpler) piegonhole principle tells us about how much we can compress: perhaps not at all, perhaps some, but certainly not as much as we fancy (unless we cheat).

share|improve this question
5  
Tweak your question a little bit and you still can't compress every string (as described in the answers below), but you get Algorithmic Information Theory(en.wikipedia.org/wiki/Kolmogorov_complexity). Replace "PRNG" with "universal Turing machine" and "seed" with "input tape containing a program that generates the output I want." Most input tapes are longer than the outputs they generate, but for every output there exists at least one input that generates that output. –  Wandering Logic Mar 24 at 18:44
    
No, but the compressed size is the entropy of the source ^_^ –  Navin Mar 25 at 1:31
4  
If you actually implement this, you'll find an interesting thing: in order to reconstruct arbitrary input, you'll need a seed+rng that is, on average, every bit as large as the original data. Oops. –  Mark Mar 25 at 4:35
    
Another way to understand why this won't work: even though a PRNG can generate arbitrarily long output, it cannot generate arbitrary output. (A PRNG's output will always be some fixed cycle or pattern, constrained by the size of its state.) –  Piet Delport Mar 25 at 11:33
    
@PietDelport, For any n there is a PRNG whose cycle is much much larger, and the question posed has n known in advance. So i'm not convinced that the fact that PRNGs are cyclic itself directly settles the question. –  user15782 Mar 25 at 13:07
show 8 more comments

7 Answers 7

up vote 32 down vote accepted

You've got a brilliant new compression scheme, eh? Alrighty, then...

♫ Let's all play, the entropy game ♫

Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ambiguous what you have compressed).

So, your scheme is to determine some family of PRNG/seeds such that if you want to compress, say, $01000111001$, then you just write some number $k$, which identifies some precomputed (and shared) seed/PRNG combo that generates those bits after $n$ queries. Alright. How many different bit-strings of length $n$ are there? $2^n$ (you have n choices between two items; $0$ and $1$). That means you will have to compute $2^n$ of these combos. No problem. However, you need to write out $k$ in binary for me to read it. How big can $k$ get? Well, it can be as big as $2^n$. How many bits do I need to write out $2^n$? $\log{2^n} = n$.

Oops! Your compression scheme needs messages as long as what you're compressing!

"Haha!", you say, "but that's in the worst case! One of my messages will be mapped to $0$, which needs only $1$ bit to represent! Victory!"

Yes, but your messages have to be unambiguous! How can I tell apart $1$ followed by $0$ from $10$? Since some of your keys are length $n$, all of them must be, or else I can't tell where you've started and stopped.

"Haha!", you say, "but I can just put the length of the string in binary first! That only needs to count to $n$, which can be represented by $\log{n}$ bits! So my $0$ now comes prefixed with only $\log{n}$ bits, I still win!"

Yes, but now those really big numbers are prefixed with $\log{n}$ bits. Your compression scheme has made some of your messages even longer! And half of all of your numbers start with $1$, so half of your messages are that much longer!

You then proceed to throw out more ideas like a terminating character, gzipping the number, and compressing the length itself, but all of those run into cases where the resultant message is just longer. In fact, for every bit you save on some message, another message will get longer in response. In general, you're just going to be shifting around the "cost" of your messages. Making some shorter will just make others longer. You really can't fit $2^n$ different messages in less space than writing out $2^n$ binary strings of length $n$.

"Haha!", you say, "but I can choose some messages as 'stupid' and make them illegal! Then I don't need to count all the way to $2^n$, because I don't support that many messages!"

You're right, but you haven't really won. You've just shrunk the set of messages you support. If you only supported $a=0000000011010$ and $b=111111110101000$ as the messages you send, then you can definitely just have the code $a\rightarrow 0$, $b\rightarrow 1$, which matches exactly what I've said. Here, $n=1$. The actual length of the messages isn't important, it's how many there are.

"Haha!", you say, "but I can simply determine that those stupid messages are rare! I'll make the rare ones big, and the common ones small! Then I win on average!"

Yep! Congratulations, you've just discovered entropy! If you have $n$ messages, where the $i$th message has probability $p_i$ of being sent, then you can get your expected message length down to the entropy $H = \sum_{i=1}^np_i\log(1/p_i)$ of this set of messages. That's a kind of weird expression, but all you really need to know is that's it's biggest when all messages are equally likely, and smaller when some are more common than others. In the extreme, if you know basically every message is going to be $a=000111010101$. Then you can use this super efficient code: $a\rightarrow0$, $x\rightarrow1x$ otherwise. Then your expected message length is basically $1$, which is awesome, and that's going to be really close to the entropy $H$. However, $H$ is a lower bound, and you really can't beat it, no matter how hard you try.

Anything that claims to beat entropy is probably not giving enough information to unambiguously retrieve the compressed message, or is just wrong. Entropy is such a powerful concept that we can lower-bound (and sometimes even upper-bound) the running time of some algorithms with it, because if they run really fast (or really slow), then they must be doing something that violates entropy.

share|improve this answer
9  
Boy, do I sound silly when you pretend to be me. Thank god I can take pride in having discovered entropy. Jokes aside, this is a fine answer -- If only the tone wasn't so tinged with mockery. –  user15782 Mar 25 at 0:54
4  
I wasn't intending to mock, just playing along with the idea of "a 14 year-old's scheme for an amazing compression algorithm". :) –  Alexis Beingessner Mar 25 at 0:56
1  
Didn't sound like mocking to me either :) This is quite a common scheme of explaining problems in popular science (and a few other fields), although it's true that the "asker" is usually Alice or Bob rather than a "real" person :D See how easily you can suddenly understand how complex the issue really is! (not to mention that when I'm thinking out a complex issue in my head, I use the same process - an inner dialogue is amazingly good at simulating "more heads know more") –  Luaan Mar 25 at 12:12
1  
Fair enough, but why do I have to play the role of simplicio? :) –  user15782 Mar 25 at 12:58
2  
@chipmonkey, I think that's still covered by alexis's answer about the "entropy game". Possibly, the number of algorithms required to do that would be so large, that the number of bits needed to specify which one was used would cancel out the benefit. –  user15782 Mar 25 at 19:59
show 6 more comments

There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many applications of Kolmogorov complexity.

In real life, we often know something about the sequence we are compressing, say it's voice or a picture. In the case of lossless compression, Shannon's source coding theorem shows that the optimal compression rate is equal to the entropy of the source. For lossy encoding there are other theorems in information theory (rate-distortion theory). So even in this case there's a limit to how much you can compress data.

share|improve this answer
    
I've never looked at it this way, but this just came to me: basically, Shannon says that even the best-case can't be compressed arbitrarily and the Pigeonhole Principle guarantees that there must be a worst-case which cannot be compressed at all. Is that a sensible characterization? –  Jörg W Mittag Mar 24 at 19:28
1  
The best case can always be compressed, since you can include some string as a special case of your compression algorithm. This argument works not only for the worst case but also for the average case, showing that the average compression is at most 2 bits. –  Yuval Filmus Mar 24 at 19:58
    
Ah, of course. if input.empty? then output_very_long_string would give an infinite compression ratio as the best case. Actually, there is even a compression algorithm which uses this. (I forgot the name, unfortunately.) It is intended for very short strings, and it has special encodings for hard-coded substrings like http://, www., .com and so on. –  Jörg W Mittag Mar 24 at 20:31
    
Can I beat this argument if I have a way to design a PRNG family such that the sequences they cannot express are ones I exclude in advance? (noise-shaping springs to mind). –  user15782 Mar 24 at 21:18
3  
@foo1899, if you can determine some strings are more likely then others, then you can do better on average, yes. In general, the lower bound is that your expected compressed message size cannot beat $H=\sum_ip_ilog1/p_i$. Where $p_i$ is the probability of the ith possible message being sent. $H$ is maximal when all messages are equally likely, and smaller otherwise. At the extreme, you can get excellent average performance if almost every message is "hello", and every other message is rare. Just set "hello"->0, and x->1x otherwise. –  Alexis Beingessner Mar 24 at 21:47
show 3 more comments

Imagine that your seed $s$ has length $k$. Your PRNG is a deterministic function of the seed, so it outputs at most $2^k$ different sequences of length $n$. There are $2^n$ of these, so your scheme isn't going to work unless it falls back on just sending the whole $n$-bit string when there is no corresponding $s$.

(As another answer noted, this will happen for any compression function you choose at all.)

share|improve this answer
    
In itself that doesn't prove I cannot construct a PRNG that just happens to generate my chosen sequence as one of it's possible outputs, while requiring far less bits to do so. As I understand from the other answers, entropy provably enforces a lower bound on the number of bits required. That is, I simply can't do arbitrarily well for my chosen sequence. –  user15782 Mar 25 at 13:35
    
All this says is that if you make up your favorite PRNG, then I can come to you with a sequence it doesn't produce, which already breaks your idea. A stronger statement is that there are sequences which aren't emitted by any much shorter program at all. (In other words, you still lose even if I let you change your function after seeing my sequence. That's what Yuval alludes to with "Kolmogorov complexity".) –  Louis Mar 25 at 14:20
add comment

Beside other already answared points, I just want to add this link: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

So only iterating (no comparing...) to find a valid 187bit constellation of your desired data would take under (not attainable) ideal conditions more energy than the sun emits over a year.

share|improve this answer
add comment

A very quick proof that an universal compressor cannot exist. Let´s suppose you do make one, and you compress an input. Now, iteratively compress the output of your program. If you can always reduce the size, it will get smaller and smaller on every step, until you are down to 1 bit.

You could argue that, perhaps, the output of your algorithm has such a structure that it cannot be compressed more, but then you could just apply a deterministic shuffle* before recompressing.

Footnote: Some deterministic shuffling actually helps in some compression schemes: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

share|improve this answer
    
I think you're missing that each compressed message has a seed s associated with it. The message 01001011 with a ´s´ of 2348 will differ from the same message with a ´s´ of 3924. Unless I misunderstood foo1899's algorithm myself in any way. –  Azeirah Mar 25 at 23:32
add comment

The use of a PRNG for "compression" is basically useful in one situation: when it is necessary to use a "random" bunch of data and compactly record what data was used. Most pseudo-random generators can only generate a tiny fraction of possible sequences, but if one only needs a small-to-moderate number of "random" sequences, the fraction of possible sequences that a PRNG can generate will often be more than adequate.

If the sequence of data that one wishes to store happens coincidentally to match what a certain PRNG would generate given the right seed, storing the seed may be a compact alternative to storing the data. Unless the source of data is such that such matches are likely to occur, however, they would be so infrequent that searching for them would not be worthwhile.

share|improve this answer
    
PRNGs are used in this way to compactly represent (pseudo)random data, for example for the sake of repeatability of experiments. –  Yuval Filmus Mar 26 at 1:40
1  
@YuvalFilmus: Exactly. They can also be used in some situations like video game level generation where a small fraction of generated levels would be considered acceptable, but where a video game designer can randomly generate levels until he finds some which are to his liking, and record the seeds which generated those. A very useful concept historically, when coding for a video game machine with 128 bytes of RAM, trying to fit the program into a cartridge with 4096 bytes of ROM. –  supercat Mar 26 at 15:08
    
That's a very good example, it matches the scheme I described of searching for a "good" seed, but takes advantage of the fact that in that scenario many possible messages are good. –  user15782 Mar 26 at 22:07
    
@foo1899: Incidentally, the game "Pitfall" en.wikipedia.org/wiki/Pitfall! used the aforementioned technique to use generate a 256-screen map on a 4K game cartridge on a machine with 128 bytes of RAM. –  supercat Mar 26 at 22:28
add comment

Something to consider to add to the cacophony of answers that assert why there are some strings that cannot be compressed owing to the, by definition, injective nature of decompression, and the limited universe of compressed strings from which to select to represent messages is this: most strings cannot be compressed because there are very many more high entropy, disordered strings than there are lower entropy and structured ones, therefore giving rise to the condition that we see in practice that: compression is most of the time useful, since the messages we most often wish to compress are those most often possessive of some aliquot of order and structure, and by this dint, are part of the very much smaller universe of lower entropy objects. This means it is possible that, by choosing a suitable output length, we can compress everything in the smaller, structured universe. The term structured, entropy and ordered here are deliberately imprecise, to reflect the subjective definitions of the semantics and usefulness of messages we may wish to compress.

And in direct answer to the questioner's request : *yes, you could of course just get lucky and find the output of your PRNG is the exact message you wish to compress, it's just that you so often won't find this is the case because the very property that characterises a PRNG, namely, its ability to product an (almost) unending variety of different strings, make it concomitantly unlikley to produce yours.

Of course you could mitigate this unlikelihood by using a PRNG to walk over a "domain graph" of word to word transitions, and you increase greatly the likelihood of your message's apparition, and also find you must now add the domain graph to the compressed message length.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.