I PRNG possono essere usati per comprimere magicamente le cose?

Question

Questa idea mi è venuta in mente come un bambino che imparava a programmare e per aver incontrato il primo PRNG. Ancora non so quanto sia realistico, ma ora c'è uno scambio di stack.

Ecco uno schema di 14 anni per un fantastico algoritmo di compressione:

Prendi un PRNG e semi con seme s per ottenere una lunga sequenza di byte pseudo-casuali. Per trasmettere tale sequenza a un'altra parte, è necessario comunicare solo una descrizione del PRNG, il seme appropriato e la lunghezza del messaggio. Per una sequenza abbastanza lunga, quella descrizione sarebbe molto più breve della sequenza stessa.

Supponiamo ora che potrei invertire il processo. Dato abbastanza tempo e risorse computazionali, potrei fare una ricerca a forza bruta e trovare un seme (e PRNG, o in altre parole: un programma) che produce la mia sequenza desiderata (diciamo una foto divertente di gatti maliziosi).

Le prng si ripetono dopo che sono stati generati un numero sufficientemente elevato di bit, ma rispetto ai cicli "tipici" il mio messaggio è piuttosto breve, quindi questo non sembra un problema.

Voilà, un modo efficace (se rube-goldbergian) per comprimere i dati.

Quindi, supponendo:

• La sequenza che desidero comprimere è finita e conosciuta in anticipo.
• Non sono a corto di denaro o tempo (fino a quando è richiesto un importo limitato di entrambi)

Vorrei sapere:

• C'è un difetto fondamentale nel ragionamento alla base del regime?
• Qual è il modo standard per analizzare questo tipo di esperimenti di pensiero?

Riepilogo

È spesso il caso che le buone risposte chiariscono non solo la risposta, ma ciò che stavo davvero chiedendo. Grazie per la pazienza di tutti e le risposte dettagliate.

Ecco il mio nth tentativo di un riepilogo delle risposte:

• L'angolo di PRNG/Seed non contribuisce a nulla, non è altro che un programma che produce la sequenza desiderata come output.
• Il principio di Pigeonhole: ci sono molti più messaggi di lunghezza> k rispetto ai programmi (generazione di messaggi) di lunghezza <= k. Quindi alcune sequenze semplicemente non possono essere l'output di un programma più corto del messaggio.
• Vale la pena ricordare che l'interprete del programma (messaggio) è necessariamente fissato in anticipo. E il suo design determina il (piccolo) sottoinsieme di messaggi che possono essere generati quando viene ricevuto un messaggio di lunghezza k.

A questo punto l'idea del PRNG originale è già morta, ma c'è almeno un'ultima domanda da risolvere:

• D: Potrei essere fortunato e scoprire che il mio messaggio lungo (ma finito) sembra essere l'output di un programma di lunghezze <k bit?

A rigor di termini, non è una questione di possibilità poiché il significato di ogni possibile messaggio (programma) deve essere noto in anticipo. O è il significato di alcuni messaggi di <k bit o non lo è.

Se scegliessi un messaggio casuale di> = k bit in modo casuale (perché dovrei?), Avrei in ogni caso la probabilità di essere in grado di inviarlo usando meno di K bit e una quasi certezza di non essere in grado di inviare È affatto usando meno di K bit.

Otoh, se scelgo un messaggio specifico di> = k bit da quelli che sono l'output di un programma inferiore a K bit (supponendo che ci sia un tale messaggio), quindi in effetti sto sfruttando i bit già trasmessi al Ricevitore (la progettazione dell'interprete), che conta come parte del messaggio trasferito.

Infine:

• D: Cos'è tutto questo Entropia/complessità di Kolmogorov attività commerciale?

Alla fine, entrambi ci dicono la stessa cosa del (più semplice) principio di Pigeonhole ci dice di quanto possiamo comprimere: forse per niente, forse alcuni, ma certamente non tanto quanto noi (a meno che non imbrogliamo).