Ce que nous savons, c'est que π est infini et contient très probablement toutes les chaînes finies possibles de chiffres ( séquence disjonctive ).

J'ai vu récemment un prototype de πfs qui suppose que chaque fichier que vous avez créé (ou quelqu'un d'autre) ou que vous créerez, il est déjà là, donc il s'agit de l'extraire. Il existe également piFile qui peut convertir vos fichiers en métadonnées pi.

Il y a déjà la formule de type BBP (dans le cadre des mathématiques expérimentales) qui nous permet de calculer n ième chiffre binaire de pi. Ainsi, en stockant la position de notre début et la longueur des données, nous pouvons théoriquement extraire les données de notre intérêt. Il y a des arguments contre cela que nos métadonnées (par exemple le décalage de nos données) pourraient être plus grandes que les données extraites. Les symboles matriciels et π peuvent être encodés en base-256 pour le rendre plus efficace (voir la blague ).

Sur la base de ce qui précède, ma principale question est:

• Existe-t-il des algorithmes de compression basés sur PI?

Sinon, est-ce logique? Ou y a-t-il eu des recherches dans ce domaine?

Ou peut-être que π n'est pas le bon, alors qu'en est-il de la constante d'Euler ou de Tau (τ)? Cela ferait-il une différence?

^{Crédits image: Dinosaur Comics}

Voir également:

• Peut-on trouver une chaîne de bits finis dans pi dans un délai raisonnable? à SO
• Le stockage de l'indice dans π ne serait-il pas aussi grand (ou plus grand) que les données d'origine? chez GitHub

Votre suggestion n'a pas beaucoup de sens, pour de nombreuses raisons. Tout d'abord, lorsque vous essayez de compresser un gros fichier, disons un fichier de taille octets, vous devrez trouver une place dans l'expansion binaire de qui correspond à votre fichier. Puisque le fichier est de bits, on s'attendrait à ce que cet endroit soit autour du ème bit. Ce serait donc assez difficile à trouver. Ce n'est pas seulement parce que nous devons aller loin dans l'expansion, mais aussi parce que nous nous attendons à essayer emplacements différents avant de trouver un hit.π 128 2 128 2 $16$$\pi$$128$$2^{128}$$2^{128}$

Deuxièmement, alors que dans certains cas, votre schéma entraînera une compression majeure, cela ne se produira que lorsqu'une certaine chaîne apparaît relativement tôt dans l'expansion de . Il n'y a aucune raison de vouloir compresser ce type de chaîne. En revanche, d'autres algorithmes de compression tentent de trouver une structure dans les données et ont des garanties qui montrent que si une telle structure existe, ils peuvent toujours l'exploiter.$\pi$

Changer avec un autre numéro ne changerait pas l'image. L'algorithme est trop spécifique, ne compressant que les chaînes qui ne nous intéressent pas vraiment; et très inefficace en phase de compression.$\pi$

Basé sur la réponse de Yuval, avec une explication légèrement différente et un exemple pour aider à éclairer le problème.

Théorie

Prenez un fichier de octets ( bits). L'algorithme de compression suit:$16$$128$

1. Déterminez où l'expansion binaire de correspond au contenu.$\pi$
2. Stockez le décalage et le nombre de bits séquencés ( ).$128$

Le décalage pour le contenu du fichier doit être autour du ^ème bit; cependant, il faut du temps pour trouver le décalage car il nécessite:$2^{128}$

• une recherche approfondie de la configuration binaire; et
• en regardant emplacements différents (en moyenne).$2^{128}$

Les correspondances qui se produisent suffisamment tôt dans pour atteindre une compression significative ne seront pas modifiées. Autrement dit, il n'est pas possible d'utiliser pour compresser des données réelles et intéressantes, car les chaînes de mots réels ne se produiront probablement pas tôt.$\pi$$\pi$

Voir aussi, entropie d'informations .

Exemple

Compressons un numéro de sécurité sociale (SSN): 938-933-556 . Calculez le nombre de bits pour coder cette valeur à l'aide de , qui est ~ et doit être arrondi à (car les bits sont indivisibles).29,8 $log_2(938933556)$$29.8$$30$

Dans , ce SSN commence à l'offset , qui a besoin de bits, ou ~ et doit également être arrondi à . Il peut y avoir un décalage antérieur, mais il est peu probable qu'il nécessite beaucoup moins de bits.597 , 507 , 393 l o g 2 ( 597507393 ) 29,2 $\pi$$597,507,393$$log_2(597507393)$$29.2$$30$

Peut-être que nous pouvons couper les chiffres?

• 938 , offset , 11 bits$1,124$
• 933 , décalage , 11 bits$1,216$
• 556 , décalage , 14 bits$11,727$

C'est bits, un résultat encore pire. Peut-être un morceau différent?$36$

• 9,389,335 , offset , 24 bits$15,312,393$
• 6 , décalage , 3 bits$8$

C'est bits, ce qui vaut mieux que , mais a des problèmes. Tout d'abord, l'ajout d'un segment non uniforme nécessite plus d'informations pour indiquer où les segments commencent et s'arrêtent. Deuxièmement, il est encore plus long de trouver le segment optimal pour atteindre le moins de bits. Troisièmement, l'enregistrement de trois bits est à peine considéré comme une compression.$27$$30$

Différents nombres transcendantaux auront plus ou moins le même résultat statistique. Même si vous vous rasez un cheveu, disons, pour deux bits, la constante qui a été utilisée doit être indiquée. Trois bits permettent à l'algorithme de sélectionner l'un des huit nombres différents. En conséquence, l'algorithme serait beaucoup plus lent en raison de la recherche de séquences au lieu d'une.$N$

Existe-t-il des algorithmes de compression basés sur PI?

ouais, https://github.com/divinity76/pi_compression

Est-ce que ça fait du sens?

non, le stockage des décalages prend généralement plus d'espace disque que vous n'en économisez, au moins avec l'implémentation ci-dessus (3 choses notables à ce sujet qui pourraient être améliorées cependant, il ne prend en compte que les 2 ^ 32 premiers octets d'une représentation binaire de pi, et il utilise une quantité excessive de bits pour stocker le nombre d'octets correspondants par décalage, à savoir 8 bits tandis que le test montre que 3 bits seraient optimaux, et il ne prend en compte que les correspondances à octets complets, donc s'il y a une correspondance à 15 bits quelque part, il être considéré uniquement comme une correspondance sur 8 bits. également si les 4 derniers bits d'un octet correspondent mais pas le bit # 3, et les 4 premiers bits des octets suivants correspondent mais pas le bit # 5, il n'est pas considéré comme une correspondance à tout)

Ou y a-t-il eu des recherches dans ce domaine?

euh bien sûr, c'est pourquoi j'ai écrit l'implémentation ci-dessus, et les résultats semblent être que dans les premiers 4 Go de pi, vous trouverez probablement 4 octets correspondants de .. à peu près n'importe quoi, ce qui est très difficile, voire impossible, pour gagner de la compression, j'ai au moins échoué. (mais mon implémentation n'est pas optimale, comme expliqué ci-dessus) - la compression est également très lente, mais mon implémentation est monothread, mais l'algorithme permet le multithreading si quelqu'un peut être arsé en écrivant le code, ce qui permettrait une mise à l'échelle des performances avec le nombre de cœurs disponibles.

la décompression est cependant très rapide.

Existe-t-il des algorithmes de compression basés sur PI?

cette question semble être motivée par l'idée qu'il existe des spéculations de "science populaire" selon lesquelles ou d'autres constantes mathématiques contiennent toutes les séquences possibles de chiffres, mais elle n'est pas prouvée. un algorithme de compression basé sur ayant des séquences arbitraires de chiffres n'est pas inconcevable mais dépendrait de la propriété suivante. c'est-à-dire "afaik" c'est un problème / question ouvert si la question suivante est (non) décidable (et il en va de même pour les autres constantes classiques):$\pi$$\pi$

séquence d' entrée . sortie, Y / N, contient la séquenceπ $X$$\pi$$X$

il n'y a pas d' algorithmes de compression "grand public" basés sur mais dans (T) CS, il est difficile / problématique de tracer une frontière stricte autour du "grand public" . contrairement à l'usage populaire du terme, se référant à un ensemble d'algorithmes "largement utilisés" ou "standard", un "algorithme de compression" en CS est un concept très large. techniquement oui, "un algorithme de compression basé sur existe", car il est facile d'en construire un "artificiel" (exercice au lecteur), mais non, aucun algorithme standard n'est basé sur des séquences de chiffres dans des constantes mathématiques.$\pi$$\pi$

même si une constante mathématique se révélait avoir la propriété remarquable de "contenir toutes les chaînes", un argument simple est que l'algorithme de compression passerait "trop ​​de temps" à rechercher la position de la chaîne et décrire son emplacement prendrait souvent longue (er) chaîne de chiffres.

voir aussi / contrast / try to conconcile with similar high-Vote question how can it decidable whether si contient une séquence de chiffres . (cs.se) (indice: le titre peut être considéré comme quelque peu trompeur)