Les PRNG peuvent-ils être utilisés pour compresser des choses comme par magie?

38

Cette idée m'est venue en tant qu'enfant apprenant à programmer et rencontrant pour la première fois les PRNG. Je ne sais toujours pas à quel point c'est réaliste, mais maintenant, il y a échange de pile.

Voici un schéma de 14 ans pour un algorithme de compression incroyable:

Prenez un PRNG et ensemencez-le avec une graine spour obtenir une longue séquence d'octets pseudo-aléatoires. Pour transmettre cette séquence à une autre partie, il vous suffit de communiquer une description du PRNG, le germe approprié et la longueur du message. Pour une séquence assez longue, cette description serait beaucoup plus courte que la séquence elle-même.

Supposons maintenant que je puisse inverser le processus. Avec suffisamment de temps et de ressources informatiques, je pourrais faire une recherche brutale et trouver une graine (et PRNG, ou en d'autres termes: un programme) qui produirait la séquence souhaitée (disons une photo amusante de chats espiègles).

Les PRNG se répètent après qu'un nombre suffisant de bits ait été généré, mais par rapport aux cycles "typiques", mon message est assez court, ce qui ne semble pas vraiment poser de problème.

Voilà, un moyen efficace (si rube-goldbergien) de compresser les données.

Donc, en supposant que:

  • La séquence que je souhaite compresser est finie et connue d'avance.
  • Je ne manque ni d'argent ni de temps (tant qu'un montant limité des deux est requis)

J'aimerais savoir:

  • Y at-il une faille fondamentale dans le raisonnement derrière le schéma?
  • Quelle est la méthode standard pour analyser ce type d’expériences de pensée?

Sommaire

Il arrive souvent que de bonnes réponses indiquent clairement non seulement la réponse, mais aussi ce que je demandais vraiment. Merci pour la patience de chacun et ses réponses détaillées.

Voici ma nième tentative de résumé des réponses:

  • L'angle PRNG / seed ne contribue en rien, ce n'est qu'un programme qui produit en sortie la séquence souhaitée.
  • Principe du casier: Il y a beaucoup plus de messages de longueur> k qu'il n'y a de programmes (générant des messages) de longueur <= k. Ainsi, certaines séquences ne peuvent tout simplement pas être la sortie d'un programme plus court que le message.
  • Il est à noter que l'interprète du programme (message) est nécessairement fixé à l'avance. Et sa conception détermine le (petit) sous-ensemble de messages pouvant être générés lorsqu'un message de longueur k est reçu.

À ce stade, l’idée originale de PRNG est déjà morte, mais il reste au moins une dernière question à régler:

  • Q: Pourrais-je avoir de la chance et découvrir que mon message long (mais fini) est la sortie d'un programme de longueur <k bits?

Strictement parlant, ce n'est pas une question de hasard, car la signification de chaque message (programme) possible doit être connue à l'avance. Soit il est la signification de certains messages de <k bits ou il n'est pas .

Si je choisis un message aléatoire de> = k bits au hasard (pourquoi le ferais-je?), J’aurais de toute façon une probabilité de disparition capable de l’envoyer en utilisant moins de k bits, et une quasi-certitude de ne pas pouvoir envoyer du tout en utilisant moins de k bits.

OTOH, si je choisis un message spécifique de> = k bits parmi ceux qui sont la sortie d'un programme de moins de k bits (en supposant qu'il existe un tel message), je profite en fait des bits déjà transmis au récepteur (la conception de l'interprète), qui compte dans le message transféré.

Finalement:

En fin de compte, les deux nous disent la même chose que le principe (plus simple) de casier nous dit à quel point nous pouvons compresser: peut-être pas du tout, peut-être certains, mais certainement pas autant que nous le souhaitons (sauf si nous trichons).

DW
la source
6
Ajustez légèrement votre question et vous ne pouvez toujours pas compresser toutes les chaînes (comme décrit dans les réponses ci-dessous), mais vous obtenez la théorie de l'information algorithmique ( en.wikipedia.org/wiki/Kolmogorov_complexity ). Remplacez "PRNG" par "machine de Turing universelle" et "graine" par "bande d'entrée contenant un programme générant le résultat souhaité". La plupart des bandes d'entrée sont plus longues que les sorties qu'elles génèrent, mais pour chaque sortie, il existe au moins une entrée générant cette sortie.
Wandering Logic
Non, mais la taille compressée correspond à l'entropie de la source ^ _ ^
Navin
5
Si vous implémentez réellement cela, vous trouverez une chose intéressante: pour reconstruire une entrée arbitraire, vous aurez besoin d’un nombre initial de données d’impression qui soit, en moyenne, tout aussi volumineux que les données originales. Oops.
Marc
Une autre façon de comprendre pourquoi cela ne fonctionne pas: même si un PRNG peut générer une sortie arbitrairement longue , il ne peut pas générer de sortie arbitraire . (La sortie d'un PRNG sera toujours un cycle ou motif fixe, contrainte par la taille de son état.)
Pi Delport
@PietDelport, Pour tout n, il existe un PRNG dont le cycle est beaucoup plus volumineux et la question posée est connue d'avance. Je ne suis donc pas convaincu que le fait que les PRNG soient cycliques règle directement la question.

Réponses:

43

Vous avez un nouveau schéma de compression brillant, hein? Bon, alors ...

♫ Jouons tous, le jeu d'entropie

Juste pour être simple, je suppose que vous voulez compresser des messages d’exactement bits, pour certains n fixes . Cependant, vous voulez pouvoir l'utiliser pour des messages plus longs, vous avez donc besoin d'un moyen de différencier votre premier message du deuxième (il ne peut pas être ambigu de ce que vous avez compressé).nn

Votre méthode consiste donc à déterminer une famille de PRNG / graines telle que si vous voulez compresser, par exemple , vous écrivez simplement un nombre k , qui identifie un combo de graines / PRNG précalculé (et partagé) qui génère ces bits après n questions. Bien. Combien y a-t-il de différentes chaînes de bits de longueur n ? 2 n (vous avez n choix entre deux éléments: 0 et 1 ). Cela signifie que vous devrez calculer 2 n de ces combos. Aucun problème. Cependant, vous devez écrire k en binaire pour que je puisse le lire. Quelle taille peut k obtenir? Eh bien, il peut être aussi grand que 201000111001knn2n012nkk . Combien de bits dois-je écrire 2 n ? log 2 n = n .2n2nlog2n=n

Oops! Votre schéma de compression a besoin de messages aussi longtemps que ce que vous compressez!

« Haha! », Vous dites: « mais qui est dans le pire des cas! Un de mes messages sera mis en correspondance à , qui n'a besoin que d' 1 bit pour représenter! Victoire! »01

Oui, mais vos messages doivent être sans ambiguïté! Comment puis-je distinguer suivi de 0 à 10 ? Puisque certaines de vos clés ont une longueur n , elles doivent toutes l'être, sinon je ne peux pas vous dire où vous avez commencé et ce que vous avez arrêté.1010n

"Haha!", Dis-tu, "mais je peux juste mettre la longueur de la chaîne en binaire en premier! Cela n'a besoin que de compter jusqu'à , ce qui peut être représenté par log n bits! Donc mon 0 est maintenant préfixé avec seulement log n bits, je gagne encore! "nlogn0logn

Oui, mais maintenant ces très gros nombres sont préfixés avec bits. Votre schéma de compression a rendu certains de vos messages encore plus longs! Et la moitié de tous vos numéros commencent par 1 , donc la moitié de vos messages sont beaucoup plus longs!logn1

Vous passez ensuite à plus d'idées, comme un caractère de fin, gzipping le nombre et comprimant la longueur elle-même, mais toutes ces situations se heurtent à des cas où le message résultant est simplement plus long. En fait, pour chaque bit que vous enregistrez sur un message, un autre message sera plus long en réponse. En général, vous ne ferez que modifier le "coût" de vos messages. En raccourcir certaines ne fera que rallonger les autres. Vous ne pouvez vraiment pas insérer messages différents dans moins d'espace que d'écrire 2 n chaînes binaires de longueur n .2n2nn

"Haha!", Dis-tu, "mais je peux choisir des messages comme" stupides "et les rendre illégaux! Alors je n'ai pas besoin de compter jusqu'à , parce que je ne supporte pas autant de messages!"2n

Vous avez raison, mais vous n'avez pas vraiment gagné. Vous venez de réduire le nombre de messages que vous prenez en charge. Si vous avez uniquement pris en charge et b = 111111110101000 les messages que vous envoyez, vous pouvez alors disposer du code a 0 , b 1 , ce qui correspond exactement à ce que j'ai dit. Ici, n = 1 . La longueur réelle des messages n’a pas d’importance, mais leur nombre.a=0000000011010b=111111110101000a0b1n=1

"Haha!", Dis-tu, "mais je peux simplement déterminer que ces messages stupides sont rares! Je vais faire en sorte que les messages rares soient grands et les messages communs petits! Ensuite, je gagne en moyenne!"

Oui! Félicitations, vous venez de découvrir l' entropie ! Si vous avez messages, où le i e un message a une probabilité p i d'être envoyé, vous pouvez obtenir la longueur de votre message attendu jusqu'à l'entropie H = Σ n i = 1 p i log ( 1 / p i ) de cet ensemble des messages. C'est une sorte d'expression bizarre, mais tout ce que vous avez besoin de savoir, c'est que c'est le plus gros message quand tous les messages ont la même probabilité, et plus petit quand certains sont plus communs que d'autres. À l'extrême, si vous connaissez fondamentalement chaque message va être unnipiH=i=1npilog(1/pi) . Ensuite, vous pouvez utiliser ce code super efficace: a 0 , x 1 x sinon. Ensuitelongueur de votre message attendu est essentiellement 1 ,qui est génial, et que ça va être vraiment proche de l'entropie H . Cependant, H est une limite inférieure et vous ne pouvez vraiment pas la battre, peu importe les efforts que vous déployez.a=000111010101a0x1x1HH

Tout ce qui prétend battre l'entropie ne fournit probablement pas assez d'informations pour récupérer le message compressé sans ambiguïté, ou est tout simplement faux. Entropy est un concept puissant que nous pouvons lié baisser (et parfois même supérieure liØe) le temps d' exécution de certains algorithmes avec elle, parce que s'ils courent très vite (ou très lent), alors ils doivent faire quelque chose qui viole l' entropie .

Alexis Beingessner
la source
13
Boy, est-ce que je parais idiot quand vous prétendez être moi? Dieu merci, je peux être fier d’avoir découvert l’entropie. Blague à part, c'est une bonne réponse - Si seulement le ton n'était pas aussi teinté de moquerie.
6
Je n'avais pas l'intention de me moquer, je ne fais que jouer avec l'idée d'un "schéma pour un algorithme de compression épatant de 14 ans". :)
Alexis Beingessner
3
Cela ne m'a pas semblé moqueur non plus :) C'est un schéma assez courant pour expliquer les problèmes de la science populaire (et de quelques autres domaines), même s'il est vrai que le "demandeur" est généralement Alice ou Bob plutôt qu'un "réel" personne: D Vois avec quelle facilité tu peux tout à coup comprendre à quel point la question est complexe! (pour ne pas mentionner que quand je réfléchis à une question complexe dans ma tête, j'utilise le même processus - un dialogue intérieur est incroyablement bon pour simuler "plus de têtes en savent plus")
Luaan
2
@ SteveJessop, c'est une fausse dichotomie et n'y allons pas. C'est une bonne réponse et je suis peut-être trop sensible, c'est tout.
3
@ Chipmonkey, je pense que cela reste couvert par la réponse d'Alexis à propos du "jeu d'entropie". Le nombre d’algorithmes requis pour faire cela serait peut-être si important que le nombre de bits requis pour spécifier celui qui a été utilisé annulerait l’avantage.
21

2N1N2NN

Dans la vraie vie, nous savons souvent quelque chose à propos de la séquence que nous compressons, disons une voix ou une image. Dans le cas de la compression sans perte, le théorème de Shannon montre que le taux de compression optimal est égal à l'entropie de la source. Pour le codage avec perte, il existe d'autres théorèmes en théorie de l'information (théorie du taux de distorsion). Ainsi, même dans ce cas, le nombre de compressions de données pouvant être compressées est limité.

Yuval Filmus
la source
Je ne l'ai jamais envisagé de cette façon, mais cela m'est venu à l'esprit: Shannon dit que même le meilleur des cas ne peut pas être compressé arbitrairement et que le principe de Pigeonhole garantit qu'il doit y avoir un cas pire qui ne peut pas être compressé. du tout. Est-ce une caractérisation sensible?
Jörg W Mittag Le
1
Le meilleur des cas peut toujours être compressé, car vous pouvez inclure une chaîne comme cas particulier de votre algorithme de compression. Cet argument fonctionne non seulement pour le cas le plus défavorable, mais également pour le cas moyen, montrant que la compression moyenne est d'au plus 2 bits.
Yuval Filmus
Ah bien sur. if input.empty? then output_very_long_stringdonnerait un taux de compression infini comme le meilleur des cas. En fait, il existe même un algorithme de compression qui l'utilise. (J'ai oublié le nom, malheureusement.) Il est destiné à des chaînes très courtes, et il a encodages spéciaux pour les sous - chaînes codées en dur comme http://, www., .comet ainsi de suite.
Jörg W Mittag Le
Puis-je battre cet argument si j'ai un moyen de concevoir une famille PRNG telle que les séquences qu'elles ne peuvent pas exprimer soient celles que j'exclus par avance? (la formation de bruit vient à l'esprit).
3
H=ipilog1/pipiH
7

sk2kn2nns

(Comme l’a noté une autre réponse, cela se produira pour n’importe quelle fonction de compression choisie.)

Louis
la source
En soi, cela ne prouve pas que je ne peux pas construire un PRNG qui génère la séquence choisie comme l'une de ses sorties possibles, tout en nécessitant beaucoup moins de bits. D'après ce que j'ai compris des autres réponses, l'entropie impose de manière prouvée une limite inférieure sur le nombre de bits requis. C'est-à-dire que je ne peux tout simplement pas faire arbitrairement bien pour ma séquence choisie.
Tout ce que cela dit, c’est que si vous composez votre PRNG préféré, je peux alors venir à vous avec une séquence qu’elle ne produit pas, qui casse déjà votre idée. Une déclaration plus forte est qu'il existe des séquences qui ne sont pas émises par un programme beaucoup plus court. (En d'autres termes, vous perdez toujours même si je vous laisse changer de fonction après avoir vu ma séquence. C'est ce à quoi Yuval fait allusion avec "la complexité de Kolmogorov".)
Louis
4

Outre les points déjà répondus, je souhaite simplement ajouter ce lien: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

À présent, la production annuelle d’énergie de notre soleil est d’environ 1,21 × 10 ^ 41 ergs. Cela suffit pour alimenter environ 2,7 × 10 ^ 56 modifications sur un seul bit sur notre ordinateur idéal; assez de changements d'état pour mettre un compteur 187 bits à travers toutes ses valeurs. Si nous construisions une sphère de Dyson autour du soleil et capturions toute son énergie pendant 32 ans, sans aucune perte, nous pourrions faire en sorte qu'un ordinateur puisse compter jusqu'à 2 ^ 192. Bien sûr, il n’aurait pas assez d’énergie pour effectuer des calculs utiles avec ce compteur.

Il suffit donc d’itérer (sans comparaison ...) pour trouver une constellation valide de 187 bits de vos données souhaitées que dans des conditions (non réalisables) idéales, il faudrait plus d’énergie que le soleil n'en émet sur une année.

utilisateur1186178
la source
1

Une preuve très rapide qu'un compresseur universel ne peut pas exister. Supposons que vous en fassiez une et que vous compressiez une entrée. Maintenant, compressez de manière itérative la sortie de votre programme. Si vous pouvez toujours réduire la taille, elle deviendra de plus en plus petite à chaque étape, jusqu'à atteindre un bit.

Vous pourriez peut-être soutenir que la sortie de votre algorithme a une structure telle qu'il ne peut pas être compressé davantage, mais vous pouvez ensuite appliquer un mélange aléatoire * avant la recompression.

Note de bas de page: Certains remaniements déterministes sont réellement utiles dans certains schémas de compression: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Davidmh
la source
Je pense que vous manquez que chaque message compressé a une graine sassociée. Le message 01001011 avec un ´s´ de 2348 sera différent du même message avec un ´s´ de 3924. À moins que je n’ai mal compris l’algorithme de foo1899 de quelque manière que ce soit.
Azeirah
1

L'utilisation d'un PRNG pour la "compression" est fondamentalement utile dans une situation: lorsqu'il est nécessaire d'utiliser un groupe de données "aléatoire" et d'enregistrer de manière compacte les données qui ont été utilisées. La plupart des générateurs pseudo-aléatoires ne peuvent générer qu'une infime fraction de séquences possibles, mais si l'on n'a besoin que d'un nombre faible à modéré de séquences "aléatoires", la fraction de séquences possibles qu'un PRNG peut générer sera souvent plus que suffisante.

Si la séquence de données que l'on souhaite stocker coïncide pour coïncider avec ce qu'un certain PRNG générerait si la graine appropriée était donnée, le stockage de la graine pourrait constituer une alternative compacte au stockage des données. À moins que la source des données ne soit telle que de telles correspondances soient susceptibles de se produire, elles seraient toutefois si peu fréquentes que leur recherche n'en aurait pas valu la peine.

supercat
la source
Les PRNG sont utilisés de cette manière pour représenter de manière compacte des données (pseudo) aléatoires, par exemple à des fins de répétabilité des expériences.
Yuval Filmus
1
@YuvalFilmus: exactement. Ils peuvent également être utilisés dans certaines situations, telles que la génération de niveau de jeu vidéo où une petite fraction des niveaux générés seraient considérés comme acceptables, mais où un concepteur de jeu vidéo peut générer de manière aléatoire des niveaux jusqu’à ce qu’il en trouve certains qui soient à son goût et enregistre les généré ceux-ci. Un concept historiquement très utile pour coder une machine de jeu vidéo avec 128 octets de RAM et essayer d’intégrer le programme dans une cartouche de 4096 octets de ROM.
Supercat
C'est un très bon exemple, cela correspond au schéma de la recherche d'une "bonne" graine que j'ai décrit, mais tire parti du fait que dans ce scénario, de nombreux messages possibles sont bons.
@ foo1899: Incidemment, le jeu "Pitfall" fr.wikipedia.org/wiki/Pitfall ! utilisé la technique susmentionnée pour utiliser générer une carte de 256 écrans sur une cartouche de jeu 4K sur une machine avec 128 octets de RAM.
Supercat
1

Voici un élément à considérer pour ajouter à la cacophonie de réponses qui expliquent pourquoi certaines chaînes ne peuvent pas être compressées en raison de la nature injective de la décompression et de l'univers limité des chaînes compressées à sélectionner pour représenter des messages: la plupart des chaînes ne peuvent pas être compressées car il y a beaucoup plus d'entrées hautes et désordonnées que d'entrées inférieures et structurées, donnant ainsi lieu à la condition que nous voyons en pratique que: la compression est la plupart du temps utile, car les messages Le plus souvent, ceux qui souhaitent compresser sont ceux qui possèdent le plus souvent une aliquote d’ordre et de structure et font ainsi partie de l’univers beaucoup plus petit des objets à entropie inférieure. Cela signifie qu'il est possible qu'en choisissant une longueur de sortie appropriée, nous pouvons tout compresser dans l'univers plus petit et structuré. Le terme structuré, entropie et ordonné ici est délibérément imprécis, afin de refléter les définitions subjectives de la sémantique et de l'utilité des messages que nous pouvons souhaiter compresser.

Et en réponse directe à la demande de l'interlocuteur: * oui, vous pouvez bien sûr avoir de la chance et trouver que la sortie de votre PRNG est le message exact que vous souhaitez compresser, c'est que vous ne le trouverez souvent pas, car la propriété même qui caractérise un PRNG, à savoir son aptitude à produire une variété (presque) infinie de chaînes différentes, l’empêche parallèlement de produire le vôtre.

Bien sûr, vous pouvez atténuer cette invraisemblance en utilisant un PRNG pour parcourir un "graphe de domaine" de transitions mot à mot, et vous augmentez considérablement la probabilité d'apparition de votre message. Vous devez également ajouter le graphe de domaine au message compressé. longueur.

Cris
la source