Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Croyez-vous en la compression Infini
Bonjour à tous,
Alors voila un petit débat qui me semble intéressant, Croyez vous en la compression infini ou à résultat fixe (c'est à dire que n'importe quel fichier peut arriver par exemple à 1-2 Mo quelque soit sa taille initiale).
J'avancerais mes arguments et mon point de vue ce soir, au calme, tête posée.
Pour ceux qui ont le temps, lancez vous
Cordialement,
Maldus
edit : Sans perte évidemment
Hie,
Non, définitivement, pas besoin de réfléchir.
(L'infini, c'est l'infini, et c'est ttttrrrèèèèsss grand)
Si les cons volaient, il ferait nuit à midi.
Non. Je ne pense pas qu'il puisse y avoir un réel débat à ce sujet.
Thierry
"The most important thing in the kitchen is the waste paper basket and it needs to be centrally located.", Donald Knuth
"If the only tool you have is a hammer, every problem looks like a nail.", probably Abraham Maslow
FAQ-Python FAQ-C FAQ-C++
+
La réponse est évidemment non... Il ne peut y avoir de bijection entre un ensemble infini (l'ensemble des fichiers possibles) et un ensemble fini (l'ensemble des fichiers de taille 2 Mo).Envoyé par Maldus
--
Jedaï
Selon moi, il me parait possible tout de même (avec un nombre de passe infini) d'approcher du zero absolu en compression (sans prendre en compte le facteur temps).
Imaginons une compression d'un fichier de 10Mo, en traitant les redondances, puis par dictionnaire, puis encore les redondances, etc Et ceci un nombre de fois n (ou n tend vers l'infini), il me parait possible d'approcher le zero (plus on fait de passes différentes plus on s'approche de celui-ci).
A terme (avec un gain fixe de 3% par exemple) pour 10 passes : 7.37MO
100 passes : 0.47Mo
1000 passes : 5.9x10^-13 Mo
Tout ceci sans compter dictionnaires et autres fichiers créés à la compression.
Bon ce n'est que de la pure théorie, et ce n'est pas vérifiable (car le temps de compression augmente exponentiellement en fonction du nombre de passes, et le gain diminue de la meme facon ...
Enfin bref, voila ce que j'ai en tete en ce moment (et que je tente de developper sachant pertinemment que le résultat ne sera pas celui excompté).
Hai,
Pourquoi vouloir discuter de cette possibilité strictement impossible.
Ton raisonnement est par conséquent ridicule (histoire de rester poli
Enfin, si tu as du temps à perdre, passe-le plutôt sur des sujets qui ont au moins une chance de déboucher, ne serait-ce qu'en démontrant la fausseté de diverses conjectures.
Si les cons volaient, il ferait nuit à midi.
C'est impossible, tu comprends ? IMPOSSIBLE
Réfléchis un peu : toute méthode de compression établit une bijection entre fichiers (séquence de bits), à chaque fichier correspond une version compressée et à chaque version compressée correspond un fichier d'origine, c'est ce que signifie le "sans perte".
De ce fait, aucune méthode de compression n'est en réalité parfaite, autrement dit il existe des fichiers pour lesquels la version compressée est au moins aussi longue que la version d'origine, sans même parler de trouver une méthode de compression qui réduirait indéfiniment la taille de tout fichier (une absurdité si tu réfléchis un peu aux chiffres). Les "bonnes" méthodes de compression sont celles qui exploite les régularités présentes dans les fichiers réels à l'origine et compressent réellement cette certaine classe de fichier, mais ce faisant elles créent des fichiers qui n'appartiennent que de façon marginale à cette classe, et si tu répètes plusieurs fois cette méthode, tu es certain de commencer à créer des versions "compressées" plus volumineuse que leur origine.
--
Jedaï
http://fr.wikipedia.org/wiki/Entropie_de_Shannon
Ici on a une limite théorique, mais on en sais déjà pas l'atteindre.
Bon, bha, le débat est clos je présume...
Mais je ne vois pas pourquoi s'enteter sur une théorie (théorie de shannon), alors que bien des théories ont été outrepasser dans les siècles précédents...
Après, je vous rejoins effectivement sur l'infaisabilité de la chose mais je trouvais intéressant de confronter les idées.
Enfin bon, soit, arrêtons nous là.
Pour confronter des idées, il faut qu'elles soient différentes. Or il semble qu'on soit tous d'accord.Bon, bha, le débat est clos je présume...
Mais je ne vois pas pourquoi s'enteter sur une théorie (théorie de shannon), alors que bien des théories ont été outrepasser dans les siècles précédents...
Après, je vous rejoins effectivement sur l'infaisabilité de la chose mais je trouvais intéressant de confronter les idées.
Enfin bon, soit, arrêtons nous là.
Thierry
"The most important thing in the kitchen is the waste paper basket and it needs to be centrally located.", Donald Knuth
"If the only tool you have is a hammer, every problem looks like a nail.", probably Abraham Maslow
FAQ-Python FAQ-C FAQ-C++
Pas tout à fait.
Dans l'absolu bien sûr, la compression infinie n'est pas possible :
Ensuite, la théorie de l'information nous enseigne comment calculer le nombre de bits minimum nécessaires pour encoder une certaine quantité d'information.
Cependant, la théorie c'est de la théorie. Même si la théorie montre l'existance d'une limite, est-on seulement capable de dire si on se trouve sur cette limite ?
Le principe de la théorie de l'information consiste à mesurer la quantité d'information transmise par un message ou un événement à partir de sa probabilité.
Appliqué à la compression de fichier, on applique le principe :
- Un octet = un événement.
- Un fichier = une succession d'octets indépendants = une succession d'événements.
Partant de ce principe, si on considère un fichier de 256 octets qui contiendrait tous les entiers de 0 à 255 dans l'ordre.
Chaque octet est présent avec la même fréquence donc la même probabilité.
Si on considère que chaque élément est indépendant les uns des autres, la théorie de l'information nous dirais que ce fichier est incompressible.
D'ailleurs, un LZW ou une compression huffman ne parviendrait pas à grand chose.
Pourtant, il m'a fallu moins de 256 caractères pour vous décrire le contenu du fichier et donc le transmettre... La limite théorique a donc été dépassée.
Pourquoi ? Tous simplement parce que les hypothèses de départ ne sont pas respectées.
Les probabilités de chaque événement (chaque octet) ne sont pas indépendantes, connaissant la valeur de départ, je connais automatiquement la valeur suivante, et finalement le fichier complet...
Ainsi, la limite de Shanon est une limite théorique. Cependant, dans la pratique on ne sait pas réellement dire si on l'a atteinte. Pour une raison simple : On ne connait pas la quantité d'information réellement présente dans le fichier d'origine, au mieux on peut calculer des quantités d'informations sur une représentation de cette information...
Mais rien ne nous dit qu'on ne peut pas trouver une meilleure représentation de l'information initiale et ainsi atteindre un meilleur taux de compression.
Donc Maldus, je dirais qu'il existe une limite. Seulement en général, on est bien incapable de savoir si cette limite théorique est atteinte, ni même si on s'en approche.
Merci de ta réponse et de ta courtoisie,
je vais continuer à rechercher dans cette voie (non pas de la compression infini mais de la compression maximale par passe) afin d'essayer de théoriquement toucher une quelconque limite. (par simple curiosité ne hurlez pas tout de suite).
Bonne journée.
Ah ben oui, dans ces conditions... On met tout le fichier dans un dictionnaire, et le fichier compressé fait 1 octet (je garde un octet pour l'identification du fichier, je suis généreux).
Tu n'a absolument pas dépassé la limite théorique : ton message ne transporte aucune information puisque unique et statique. Il n'y a rien a compresser.
Bien sur, huffman ou consort n'arriveront pas a compresser ton message, mais ce sont leur suppositions sur la façon de prévoir la suite du message qui ne conviennent pas.
Calculons l'entropie de shannon sut ton message :
H = somme(i=0,2^256,-p(i)*log(p(i))) avec p(i) = 0 avec i != 0x0001020304..FEFF et p(0x0001020304..FEFF) = 1 . avec lim (n->0) (n*log(n)) = 0 on as :
H = -1*log(1) = 0.
Forcement en même temps, tu ne propose qu'un message possible, il n'y a donc aucune info a transmettre . . .
Ben si, j'ai un tableau qui occupe 256 octets sur mon disque, qui quoi qu'en dise ta démonstration est bien présent et pour lequel toi même tu nous dis qu'il est beaucoup trop volumineux puisqu'il ne contient pas d'informations...Tu n'a absolument pas dépassé la limite théorique : ton message ne transporte aucune information puisque unique et statique. Il n'y a rien a compresser.
Plus sérieusement, ça dépend de ce que tu considères et comment tu définis le système.
Toi tu décides que je n'ai qu'un unique événement : la totalité du message. Qu'il ne peut prendre qu'une seule valeur : La totalité du message. Partant de là, tu en conclus que la probabilité de l'événement est certaine et donc le message ne contient aucune information.
Si on applique ton raisonnement, tout fichier est un message unique et statique. Donc qui ne contient aucune information et qui selon Shanon devrait alors pouvoir se résumé à rien du tout. (Tiens c'est pas la compression infinie ça ?
Sauf que ce ne sont pas les hypohèses de travail appliquées à la compression de fichier :
Le message transmit est une succession de 256 événements : Les octets lus.
Chaque octet prend successivement 256 valeurs différentes.
Lorsque tu lis un octet dans ton fichier, la probabilité de lire la valeur obtenue est de 1/256.
La variable aléatoire à considérer est l'octet. Ces variations sont les différentes valeurs que tu trouves lorsque tu lis le fichier octet par octet.
Donc ça donne plutôt quelque chose du genre :
H = somme(i=0,255,-p(i)*log(p(i))) avec p(i) = 1/256
H = somme(i=0,255, -1/256*log(1/256))
H = 256 * (-1/256*log(1/256))
H = -log(1/256)
Ca fait quelque temps que je n'ai pas fait de math, mais je doute que ça fasse 0.
En fait, c'est la capacité maximale d'expression d'un message de 256 octets.
Ben pour moi, huffman n'essaie pas de prévoir la suite du message. La compression huffman consiste simplement à écrire les octets sur des longueur variables, avec un nombre de bit plus faible pour codes les octets les plus probables et un nombre de bit plus important pour les valeurs les moins probables.Bien sur, huffman ou consort n'arriveront pas a compresser ton message, mais ce sont leur suppositions sur la façon de prévoir la suite du message qui ne conviennent pas.
La table de codage est soit figée, définit arbitrairement à priori (et standardisée bien sûr pour qu'on puisse décompresser sans transmettre la table).
Soit construite à partir d'une analyse statique du fichier à compresser (ce qui donne une compression a deux passes et l'obligation de transmettre la table avec le fichier).
Cette compression est déjà censée être optimale, car on utilise le nombre de bits nécessaires pour coder chaque octet en fonction de sa probabilité.... à condition de considérer que chaque octet doit être encoder sur un nombre entier de bit.
Dans la pratique, si la théorie de l'information te dit que l'octet doit être codé sur 0,001 bit huffman en utilisera au moins 1.
Pour résoudre ce problème, les compressions LZW et autre du même genre vont tenter d'encoder non plus des octets individuels, mais des séquences d'octets de façon à ce que le nombre de bits nécessaires pour compresser la séquence soit plus important.
Mais elle repose toujours sur le même principe et nécessite une redondance au niveau des octets à compresser.
les curieux devraient regarder de près la compression bzip2
http://en.wikipedia.org/wiki/Bzip2
Il faut bien comprendre ce qui se cache derrière l'entropie de shannon.
Un message fait une certaine taille. La quantité d'information utile dans ce message est forcément inférieur a cette taille.
Si on considère un film par exemple, l'information utile est l'image et le son produit. Mais il y a parmi tout ça une infinité de films possibles.
Quand tu donnes comme exemple la suite des octets de 0 a 255, ton mode de compression ne peut en fait rendre compte que d'un seul message.
La différence entre ton calcul et le mien, c'est que le tiens considère ta séquence comme une parmis toutes les séquences de 256 octets possibles. Dans ton cas non plus la limite fixée par shannon n'est pas dépassée, car il faudra que tu rajoute de l'infos pour fournir un système capable de coder toutes les séquences.
Ce système, s'il est efficace pour coder la fameuse suite d'octet, sera moins bon sur d'autres. Je tiens de plus a te préciser que ton codage considère la chaîne entière et non une suite d'octets, il y a donc contradiction entre ton calcul d'entropie et ton codage.
En fait, toute la différence se situe dans le p(i) et la taille des événements, qui n'est pas définit par shannon. Ce p(i) et cette taille sont a définir en fonction de l'information qui toi t'intéresse.
Un autre exemple du même genre serait le codage de musique. Ici, shannon fait des sienne, et nous impose une taux d'échantillonnage supérieur a 2x la fréquence la plus haut dans le son que l'on encode.
Bien sur, dire "la danse des canards" est bien plus court que l'encodage de cette chanson, et permet tout de même de transmettre l'infos. Cela dit, ce codage est impossible pour toute musique.
Dans ce beau troll qui prend forme, vous oubliez de poser la question "Ah quoi bon compresser puisque mon PC progresse plus vite que les recherches".
LE troll est mort depuis longtemps.
Essaierais-tu de le ranimer ?
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager