Le meilleur algorithme de compression du monde !

[_Goel_]

Bonjour,

Quel est le meilleur algorithme de compression de données du monde ?

(Réponse en spoiler)

(PS : la réponse que j'attend est sans doute un peu polémique ! on pourra en discuter quand elle sera trouvée)

J'attend vos réponses !
-----

[erik]

Salut,

Aucun, il n'y a pas d'algo de compression universel, tout dépend de ce que tu veux comprimer.
Un algo de compression ultra efficace pour un fichier texte sera une catastrophe pour de la vidéo et inversement.

Après meilleur ça veut dire quoi ? meilleur taux de compression, rapidité de la compression, rapidité de la décompression, absence de dégradation du ficier source (dans le cas d'image, de son, de video) ?

[invite88ef51f0]

Salut,
Donne-moi n'importe quelles données et je te les comprime en 1 bit (et je te donne le programme de décompression). Et tout ça sans pertes.

[erik]

Salut Coincoin,

Et si je te donne 3 fichiers différents il marche encore ton algo

[A voir en vidéo sur Futura]

[invite88ef51f0]

Euh... tu commences à en demander trop, les performances risquent de diminuer : ça utilisera 2 bits au lieu d'un.

[erik]

les performances risquent de diminuer

Bof, de nos jours les machines sont puissantes, on peut pousser à 1 octet, et on pourra compresser 32768 fichiers

Pas certain que Goel attendait ce type de réponses, mais peut être qu'il commence à entrevoir le fait qu'il n'y a pas de réponse.

[invite765432345678]

Euh... tu commences à en demander trop, les performances risquent de diminuer : ça utilisera 2 bits au lieu d'un.

Bonjour,

Quand je pose cette question à mon fils (25 ans d'expérience en programmation), il me répond systèmatiquement: "il n'existe aucun logiciel universel qui puisse répondre parfaitement à tous les problèmes. Si tel était le cas, il n'y aurait plus d'informaticiens."

Simplement dans le domaine de la compression des images, j'ai bien du mal à m'y retrouver. D'après ma compréhension, tous les algorithmes détruisent la qualité de l'image initiale.

Je crois que le meilleur algorithme est le gif qui permet d'agir sur la transparence mais c'est un format propriétaire. Pour me simplifier la vie , je garde toujours sur mes sites un original de bonne qualité. J'utilise deux formats principaux: gif et jpeg.

Cordialement,

[erik]

tous les algorithmes détruisent la qualité de l'image initiale.

Non, il y'a des algo de compression d'images sans perte, de mémoire il me semble que le format GIF est sans pertes (contrairement à JPEG)

[invite765732342432]

mais peut être qu'il commence à entrevoir le fait qu'il n'y a pas de réponse.

D'un autre coté, on est dans "science ludique"...
Je présume que la réponse espérée était l'ADN ? Il est plus efficace que le JPG (c'est peu de le dire), mais le résultat est pas mal hasardeux !

[invite765432345678]

Non, il y'a des algo de compression d'images sans perte, de mémoire il me semble que le format GIF est sans pertes (contrairement à JPEG)

Vous avez raison pour le GIF. Ci-joints deux aide-mémoire écrits dans le but de m'y retrouver dans le dédale des extensions de fichiers et des types de formatage d'images. C'est incomplet mais c'est un travail perso d'amateur.
Les formats de fichiers.pdf
Format d'images pour demain.pdf

Cordialement,

[erik]

D'un autre coté, on est dans "science ludique"...

Youps j'avais pas vu

[invite765432345678]

D'un autre coté, on est dans "science ludique"...
Je présume que la réponse espérée était l'ADN ? Il est plus efficace que le JPG (c'est peu de le dire), mais le résultat est pas mal hasardeux !

Cà alors ! Je ne connais pas cet algorithme !

[_Goel_]

Salut,
Donne-moi n'importe quelles données et je te les comprime en 1 bit (et je te donne le programme de décompression). Et tout ça sans pertes.

En effet... le "programme" de décompression est assez sophistiqué... mais (chose assez rare), il est inclu dans le "fichier" de sortie.

[_Goel_]

D'un autre coté, on est dans "science ludique"...
Je présume que la réponse espérée était l'ADN ? Il est plus efficace que le JPG (c'est peu de le dire), mais le résultat est pas mal hasardeux !

J'adooore quand on lit dans mes pensées... !
En effet, faire tenir l'intégralité de l'information contenue dans un corps humain en 6Go, faut le faire, non !?

Evidemment, on ne peut pas vraiment considérer que la compression s'effectue avec pertes, dans ce cas, c'est plutôt la décompression !

[invite765432345678]

Bonjour,

Quel est le meilleur algorithme de compression de données du monde ?

(Réponse en spoiler)

(PS : la réponse que j'attend est sans doute un peu polémique ! on pourra en discuter quand elle sera trouvée)

J'attend vos réponses !

C'est celui qui reste à inventer ! Un algorithme autoadaptatif qui réponde aux demandes différentiées de chaque utilisateur (taux de compression, cryptage des informations, facteur de perte à la restitution, possibilité de créer des animations d'images, conservation du formatage du texte, restitution du document sous un autre format que celui d'origine....).

[triall]

Une compression sans perte de donnée doit être capable de restituer le fichier d'origine .
Je suppose que l'algoritme de lecture que l'on fait fonctionner à l'envers doit redonner le fichier d'origine !
Un bon algoritme doit donc être capable de restituer le fichier d'origine....
L'adn c'est très fort comme compression , comme ça a déja été dit !!
Alors je dis ...le clonage !

[_Goel_]

Cela m'amène à une question :
Dans les jeux vidéo, une part énorme des données est consacrée aux textures. Pourrait-on considérer une texture comme une surface "paramétrable" (notament la granularité qui peut se faire en ajoutant un bruit variable à une image contenant peu de détails), et ainsi gagner en place ?
La texture serait créée au besoin, lors de l'exécution du jeu.

Est-ce envisageable ?

[_Goel_]

Alors c'est ...le clonage !

Ben, c'est le but d'un algorithme de compression sans perte.

[invite765432345678]

J'adooore quand on lit dans mes pensées... !
En effet, faire tenir l'intégralité de l'information contenue dans un corps humain en 6Go, faut le faire, non !?

Evidemment, on ne peut pas vraiment considérer que la compression s'effectue avec pertes, dans ce cas, c'est plutôt la décompression !

Ah ! C'est bien vrai. MS devrait s'en inspirer !

Le gros problème je crois réside dans la recopie des données qui n'est pas parfaite. Résultat, j'ai pris un coup de vieux depuis 50 ans !

Vous ne pourriez pas trouver un truc, les informaticiens, pour reprogrammer tous mes erreurs de recopie ! Je vous transmets le programme original !

[piwi]

Je me demande si je n'ai justement pas vu une news ici ou ailleurs à propos d'une équipe de recherche qui essait justement de créer un système de compression basé sur l'ADN.

Cordialement,
piwi

[erik]

En effet, faire tenir l'intégralité de l'information contenue dans un corps humain en 6Go, faut le faire, non !?

Bof, sachant que l'ADN n'est codé qu'à partir de 4 symboles (A C G T) et qu'il y'a plein de répétition on aurait pu compresser largement plus !

Mais bon je ne connais pas le cahier des charges "fabrication de l'homme" qui a amené à faire ce choix d'un truc pas totalement optimisé

[erik]

Je me demande si je n'ai justement pas vu une news ici ou ailleurs à propos d'une équipe de recherche qui essait justement de créer un système de compression basé sur l'ADN.

Basé sur l'ADN je ne voit pas trop comment, est ce qu'il ne s'agissait pas plutôt d'algorithmes génétiques ?

[invité576543]

Salut,
Donne-moi n'importe quelles données et je te les comprime en 1 bit (et je te donne le programme de décompression). Et tout ça sans pertes.

On peut faire la même chose avec 0 bit

Cordialement,

[invite765732342432]

Cela m'amène à une question :
Dans les jeux vidéo, une part énorme des données est consacrée aux textures. Pourrait-on considérer une texture comme une surface "paramétrable" (notament la granularité qui peut se faire en ajoutant un bruit variable à une image contenant peu de détails), et ainsi gagner en place ?
La texture serait créée au besoin, lors de l'exécution du jeu.

Grosso modo, ça existe déjà: il y a un jeu, dont le nom m'échappe hélas (c'est un FPS assez beau si j'ai bon souvenir), qui tient en très peu de place grace notamment à ces textures synthétisées.

Mais bon, de nos jours, ce n'est pas utile: la taille de stockage n'est absolument plus un problème. Et la décompression des textures prend trop de temps CPU pour être intéressante.

Par contre, j'utilise de temps en temps un algo de (dé)compression très simple: une seed de random (bref un nombre) et l'algo de random.
C'est très pratique pour générer des cartes géographiques toujours identiques mais sans avoir besoin de stocker quoi que ce soit d'autre qu'un nombre. Je suppose que ça doit être utilisé aussi dans des applications comme des jeux.

[invite765432345678]

Bof, sachant que l'ADN n'est codé qu'à partir de 4 symboles (A C G T) et qu'il y'a plein de répétition on aurait pu compresser largement plus !

Mais bon je ne connais pas le cahier des charges "fabrication de l'homme" qui a amené à faire ce choix d'un truc pas totalement optimisé

Quand on peut copier la nature, il ne faut pas s'en priver ! C'est pas breveté et le système est toujours parfait.

Lorsque qu'on mesure la sphéricité de la boule du col du fémur, on constate que le défaut de sphéricité ne dépasse pas 1 micron. Difficile d'atteindre une telle perfection, d'autant que la sphéricité est auto-adaptative. La courbure s'adapte en permanence à la pression exercée. Comme la meilleure courbe est la sphére !

Si l'INPI considérait que l'idée originale est la propriété du grand Architecte, ce serait évidemment une autre histoire !

[invité576543]

Une réponse plus sérieuse, un point qui est très souvent oublié ou inconnu:

Pour tout algorithme de compression sans perte pour toute entrée, il existe des entrées telles que le résultat est PLUS GRAND que l'entrée.

Un algorithme de compression sans perte échange de la compression sur un sous-ensemble des entrées possibles contre de "l'extension" des autres entrées.

Ce qui implique évidemment que le choix de l'algorithme dépende explicitement du sous-ensemble visé (du sous-ensemble pour lequel on désire une compression effective).

Si le sous-ensemble est réduit à n éléments et qu'on accepte de la perte pour des entrées autres, alors la compression peut descendre à log n bits (d'où 0 pour 1 seul élément). Si on exige l'absence de perte pour toute entrée et que le sous-ensemble visé à n éléments, alors on peut compresser ces éléments sur log (n+1) bits, et tous les autres occupent k+log(n+1) bits si k est leur taille d'entrée (d'où le 1 de Coincoin).

Notons aussi qu'il est courant d'utiliser des méthodes de compression qui utilisent un seul bit pour une (et une seule) entrée. "1" n'est pas une réponse "ludique", c'est quelque chose de très pratique! (C'est le plus souvent caché sous le nom de "valeur par défaut"...)

Cordialement,

[invite6dffde4c]

Bonjour.
Pour pouvoir compresser des données il faut déjà qu'elles soient compressibles.
Un fichier formé des données au hasard (du bruit blanc, par exemple), n'est tout simplement pas compressible sans perte de données.
Au revoir.

[erik]

Si le sous-ensemble est réduit à n éléments et qu'on accepte de la perte pour des entrées autres, alors la compression peut descendre à log n bits (d'où 0 pour 1 seul élément). Si on exige l'absence de perte pour toute entrée et que le sous-ensemble visé à n éléments, alors on peut compresser ces éléments sur log (n+1) bits, et tous les autres occupent k+log(n+1) bits si k est leur taille d'entrée

Super intéressant, est ce que tu aurais des références de doc sur le net parlant de ça, ou à défaut la référence d'un bouquin ?

[invite765432345678]

Bonjour.
Pour pouvoir compresser des données il faut déjà qu'elles soient compressibles.
Un fichier formé des données au hasard (du bruit blanc, par exemple), n'est tout simplement pas compressible sans perte de données.
Au revoir.

Pour les fichiers sons, que pensez-vous du format mp3 ? Quel est le meilleur format de compression ?

[invite6dffde4c]

Pour les fichiers sons, que pensez-vous du format mp3 ? Quel est le meilleur format de compression ?

Re.
Les algorithmes pour le son et pour les images (MP3, MP4) sont des algorithmes à perte de données. Mais à pertes savamment choisies en fonction de nos sens pour qu'elles ne soient pas gênantes.

Pour les algorithmes sans perte de données, comme ZIP, je trouve que RAR est plus lent mais qu'il compresse un peu plus. Pour des données "ordinateur". Et les fichiers PDF on déjà un algorithme suffisamment bon, pour qu'on ne gagne rien en essayant de les compresser.

Je profite pour vous raconter une histoire que j'ai lue en Scientific American il y a longtemps:

Un extraterrestre atterrit dans la Bibliothèque du Congrès pour emporter toutes les connaissances terrestres.
Il numérise le premier livre, qu'il écrit sous forme de nombre fractionnaire en base 2 en posant tous les octets à la suite: 0,1101011001....
Il numérise ainsi tous les livres et met les octets à la suite du premier nombre. Il se retrouve avec un nombre fractionnaire en basse 2 avec un nombre de chiffres considérable mais fini.
Il prend une baguette faite dans un matériau de son monde et fait une fine marque à l'endroit correspondant au nombre fractionnaire qu'il a obtenu.
Et il repart dans son monde en emportant dans la baguette toutes les connaissances de l'humanité.

A+