Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

autre algorithme de compression ?

Posté par
supernco
14-09-08 à 00:40

bonjour, ceci est mon premier message sur ce forum (l'ayant déja posé sur un autre forum sans réponse) et je suis surtout venu pour le poser.
Cela concerne une technique qui permettrait de réduire grandement la taille d'un fichier, au détriment d'un très long calcul de l'ordinateur.
Cela existe sans doute, mais je ne sais pas très bien comment chercher ce genre de truc, et j'ai beau avoir posé la question à plusieurs profs, aucune réponse.

voila l'idée de base.
tout fichier informatique est un ensemble de bits donc une suite de nombre entre 0 et 1. Pour plus de facilité, je considère que l'on transforme ce nombre binaire en nombre en base 10. On a donc une suite de chiffres codant par exemple une image (cette technique n'a d'interêt que pour les fichiers de grande taille)

La question mathématique que je pose est : est-il possible de trouver une suite ordonnée de n caractères en base 10, dans une partie d'une écriture décimale d'un nombre réel. (je ne suis pas très clair alors je vais essayer différemment). si on a un nombre, donc une suite de 1,2,3,4,5,6,7,8,9,0; peut on, pour toute suite trouver un intervalle dans l'écriture décimale d'un nombre qui est identique.

Je crois que la réponse est oui, mais incapable de le prouver (et à vrai dire, prouver cette partie n'est à mon avis pas le plus important).

Cette technique permettrait de gagner de l'espace, par exemple, mettons que l'on possède un fichier dont l'écriture en base 10 est égale à l'écriture de racine de 2 entre le chiffre 3 et 10542 (par exemple), au lieu d'envoyer le fichier base on enverrait : (racine de 2 - 3 - 10542). donc beaucoup moins d'espace (du moins pour du stockage ou du téléchargement, car on devrait toujours lire le fichier).

j'avais quelques idées de syntaxes permettant de nombreuses possibilités par exemple :
nombre ; puissance ; début intervalle ; fin intervalle
c'est le plus simple, mais j'en ai de beaucoup plus complexes, par exemple en changeant un bit à un endroit, ou juste en faisant +1 à tous les chiffres, ou en faisant une somme de nombres à des puissances différentes...

le problème est de savoir si pour toute suite de nombres à partir d'un certain nombre n (n étant grand); on peut trouver une fonction telle que l'écriture via cette technique soit beaucoup plus rapide.

je ne crois pas que ce soit si sur que ça.
enfin l'idéal serait (si c'est possible) de trouver que pour x% des nombres entre n et m il y a un nombre tel que pour cette syntaxe on utilise seulement y% de l'espace.

Qui plus est le temps pour calculer ce code en utilisant cette syntaxe est exponentiellement long quand on augmente n. mais l'algorithme pour le trouver est basique (même moi je suis capable d'en créer un, et dieu sait si je sais à peine programmer, il suffit de faire augmenter chacune des variables dans le code syntaxé de manière à avoir une taille du code qui augmente régulièrement, puis qui s'arrête si le code devient trop long. )

Donc en gros les questions que je pose

1 - Prouver le problème de la suite.
2 - Savoir si on trouve une fonction à partir d'un certain n, en gagnant de l'espace
3 - savoir si il y a une moyenne de la taille du code en fonction du nombre n. (si le code existe)
4 - Voir quel temps il faudrait pour calculer avec les ordinateurs d'aujourd'hui, par exemple pour un livre, une image, une chanson, un film...
je crois que le problème 1 est assez facile, alors que pour le 3 et le 4, je ne suis pas sur qu'on puisse donner une réponse approchée.

si ça se trouve on a déjà fait ça mais je n'ai rien réussi à trouver  alors s'il vous plait, si ça existe, dites moi où chercher.

Au fait, je ne fais ça que par pure curiosité, et je serais ravi de savoir même s'il est possible de répondre à ces questions.

Posté par
Fractal
re : autre algorithme de compression ? 14-09-08 à 19:18

Bonjour

Déjà pour ta première question, c'est loin d'être quelque chose d'aussi simple que tu ne le penses.
C'est clairement faux pour les nombres rationnels, mais même pour des nombres aussi simples que racine de 2 ou pi, personne ne connait la réponse ().
D'autre part, supposons que l'on veuille coder un fichier de 100 chiffres décimaux; en considérant que les chiffres après la virgule de racine de 2 sont répartie aléatoirement et uniformément, on a une chance sur 10^100 qu'une séquence donnée de chiffres corresponde exactement, donc il faut aller s'enfoncer d'en gros 10^100 chiffres décimaux dans racine de 2.
Ce qui implique un temps de calcul relativement considérable (on veut dix milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de chiffres décimaux), et le fait d'indiquer dans le fichier la position où chercher nécessitera donc environ 100 chiffres décimaux pour indiquer le début, et 100 autres pour indiquer la fin.
Donc au bout de quelques milliards de milliards ... de milliards d'années de calcul, tu auras réussi à ... doubler la taille de ton fichier!

En gros, tu n'as aucune chance de tirer un quelconque algorithme de compression efficace de cette technique.



Fractal

Posté par
supernco
re : autre algorithme de compression ? 14-09-08 à 21:38

merci beaucoup fractal.
bon, je vais compliquer encore un peu le problème :

si on avait un ordinateur quantique, on pourrait théoriquement calculer plusieurs de ces solutions à la fois. Donc ce problème disparaitrait peut-être non ?
c'est juste une idee.

Posté par
Fractal
re : autre algorithme de compression ? 15-09-08 à 20:36

Alors, si on a un ordinateur quantique, le temps de calcul pourrait éventuellement devenir raisonnable. Mais ce n'est pas le principal problème.
Il faudra de toutes façons aller chercher très loin dans racine de 2 (ou un autre nombre), et le simple fait d'écrire dans le fichier compressé le nombre de décimales à partir duquel aller chercher prendra de la place en mémoire. Cela ressemble certes à un simple nombre, mais il faut aller chercher tellement loin que l'écriture décimale de ce nombre risque fortement de dépasser la taille du fichier de départ.
Il ne faut pas se faire d'illusions, c'est un fait parfaitement évident que le nombre de fichiers possibles de taille au plus 100 est supérieur au nombre de fichiers possibles de taille au plus 99, donc pour tout algorithme de compression quel qu'il soit il existera des fichiers dont la taille sera augmentée après passage de l'algorithme.
Les algorithmes de compression couramment utilisés se basent sur le fait semiempirique qu'un fichier informatique n'est jamais totalement aléatoire et que des chaînes de caractères se répètent régulièrement.

Si tu es sous Linux, je t'invite d'ailleurs à faire la petite expérience suivante dans une invite de commande:

Citation :
$ cd /tmp
$ dd if=/dev/urandom of=rand.rand bs=1024 count=1     # On crée un fichier rempli d'un Kio de bits aléatoires

     1+0 enregistrements lus
     1+0 enregistrements écrits
     1024 octets (1,0 kB) copiés, 0,000328133 s, 3,1 MB/s

$ ls -l rand.rand     # On vérifie la taille du fichier

     -rw-r--r-- 1 fractal fractal 1024 2008-09-15 20:18 rand.rand

$ zip <rand.rand >rand.zip     # On le compresse en zip
$ bzip2 -kz rand.rand     # On compresse en bzip2
$ ls -l rand.*     # On regarde la taille des fichiers obtenus

     -rw-r--r-- 1 fractal fractal 1024 2008-09-15 20:23 rand.rand
     -rw-r--r-- 1 fractal fractal 1320 2008-09-15 20:23 rand.rand.bz2
     -rw-r--r-- 1 fractal fractal 1124 2008-09-15 20:24 rand.zip


On voit donc bien que le fait d'avoir compressé le fichier aléatoire a augmenté sa taille au contraire de l'avoir diminuée, et ce n'est pas en allant chercher dans les décimales de pi que cela changera quelque chose, au contraire, les décimales de pi étant "aléatoires", compresser un fichier texte ne permettra aucune amélioration du taux de compression et il n'y a donc aucune raison pour qu'on obtienne des taux un tant soit peu intéressants de compression.

Donc non, un ordinateur quantique ne fait pas tout

Fractal



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !