Le meilleur algorithme de compression du monde !

[Pio2001]

Pour le son, il y a des algorithmes sans pertes aussi. Les signaux musicaux sont tout de même relativement ordonnés. Le fichier compressé fait entre 35 % (classique avec beaucoup de passages doux) et 80 % (métal saturé à donf) de la taille initiale.

Propriétaires : ALAC de chez Apple-i-Tunes, MLP dans les DVD-audio.
Le format libre qui tend à s'imposer est le FLAC.

Et il y a des codecs avec pertes : mp3, wma, aac, vorbis...

Pour l'image, sans pertes, il y a le PNG, et on peut aussi compresser en LZW dans un conteneur TIFF.
Le gif est à part, car il n'accepte pas plus de 256 couleurs par image. Une fois ces couleurs définies, il compresse sans pertes. Son seul intérêt par rapport au png est d'accepter les images animées. Les smileys du forum sont des animations gif :

Et il repart dans son monde en emportant dans la baguette toutes les connaissances de l'humanité.

Génial
-----

[invite765432345678]

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+

C'est très fort !

[erik]

Il se retrouve avec un nombre fractionnaire en basse 2 avec un nombre de chiffres considérable mais fini.

L'idée est rigolote, mais totalement inapplicable, il faudrait pour pouvoir retrouver le nombre faire une mesure de longueur sur le baton précise de plusieurs millions de décimales, c'est à dire une mesure dont la marge d'erreur est énormément inférieure à la taille (pour peu que le concept de taille ici ait un sens) d'une particule élémentaire, j'ai bien peur que notre ET soit soumis aux lois de la MQ comme le reste de l'univers.

Sinon l'idée est rigolote.

[invité576543]

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 ?

Pas de tête. Cela fait partie de mon métier, c'est basé sur mon expérience.

En cherchant code d'Huffman par exemple, tu peux, j'imagine, trouver des trucs sur le sujet sur le net.

Cordialement,

[invité576543]

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.

Si c'est UN fichier particulier, il est "compressible" sans perte.

Par contre, si on impose que TOUS les fichiers ainsi générés (c'est à dire en fait tous les fichiers possibles) soit comprimés sans perte et avec gain et par un algorithme défini sans la donnée des données à comprimer, ce n'est pas possible.

La notion de "au hasard" est d'ailleurs intimement liée à la compressibilité. (On peut quasiment définir "généré au hasard" comme "non compressible par un quelconque algorithme de compression donné a priori".)

A l'opposé, je pourrais aisément montrer des dizaines (en fait bien plus) de fichiers qui sont indistinguables du "au hasard", et qui pourtant se compriment en quelques bits. (Evidemment ils ne sont pas générés n'importe comment!)

Ce sont des questions du ressort de la cryptographie, et assez bien maîtrisées.

Cordialement,

[triall]

Bonjour, prenons un fichier simple, composé de 0 et de 1 au hasard (pile ou face) , la façon de le compresser c'est d'écrire par exemple 3x1 , 2x0 , 1x1 , 1x0 , 2x1 au lieu de 111001011 .Combien on a gagné ainsi? y at-il d'autres façons de le compresser ? Est ce qu'on le compresse en l'écrivant en base dix ?

[jiherve]

Bonjour, prenons un fichier simple, composé de 0 et de 1 au hasard (pile ou face) , la façon de le compresser c'est d'écrire par exemple 3x1 , 2x0 , 1x1 , 1x0 , 2x1 au lieu de 111001011 .Combien on a gagné ainsi? y at-il d'autres façons de le compresser ? Est ce qu'on le compresse en l'écrivant en base dix ?

Bonsoir,
La base la plus compacte c'est e donc 3 si l'on se restreint aux entiers.
JR

[triall]

Merci pour la base e, je ne savais pas qu'on pouvait écrire un nombre en base e ; vous ne confondez pas avec les dimensions ..?
Mais c'était pas ma question 439 (base dix) =111001011 (base deux)....9 bits pour écrire ce fichier (?); combien pour l'écrire 3x1 , 2x0 , 1x1 , 1x0 , 2x1 combien pour l'écrire 439 ; en base quatre cent tente neuf il s'écrit...... 10 combien de bits... la même chose, patron ! Non!

[Pio2001]

L'écriture la plus compacte du nombre 439 se fait en base 440. On peut alors l'écrire I (lettre majuscule cyrillique I biélorusse-ukrainien, 440e caractère de la table de caractère Windows).

[invité576543]

Bonjour, prenons un fichier simple, composé de 0 et de 1 au hasard (pile ou face) , la façon de le compresser c'est d'écrire par exemple 3x1 , 2x0 , 1x1 , 1x0 , 2x1 au lieu de 111001011 .Combien on a gagné ainsi? y at-il d'autres façons de le compresser ? Est ce qu'on le compresse en l'écrivant en base dix ?

On ne gagne strictement rien.

La notion de compression d'un seul fichier n'a pas grand sens, quitte à se répéter.

On ne peut chercher un algo de compression que pour un ensemble de fichiers potentiellement à transmettre. Si cet ensemble est réduit à un seul élément, alors on le comprime sur 0 bit.

A l'opposé, si l'ensemble potentiel contient tous les 2ⁿ fichiers de n bits, alors il n'est pas possible de les comprimer tous. Le mieux possible consiste à ne rien faire, et donc utiliser n bits.

Cordialement,

[_Goel_]

On ne peut chercher un algo de compression que pour un ensemble de fichiers potentiellement à transmettre. Si cet ensemble est réduit à un seul élément, alors on le comprime sur 0 bit.

Dans le cas d'un fichier comprimé sur 0 ou 1 bit, cela signifie que c'est l'outil de décompression qui contient l'information. Dans ce cas il n'y a pas compression (l'ensemble "outil de compression decompression" + "fichier compressé" est supérieur à l'ensemble "fichier non compressé")

[invité576543]

annulé.............

[invite765732342432]

Dans le cas d'un fichier comprimé sur 0 ou 1 bit, cela signifie que c'est l'outil de décompression qui contient l'information. Dans ce cas il n'y a pas compression (l'ensemble "outil de compression decompression" + "fichier compressé" est supérieur à l'ensemble "fichier non compressé")

Pas trop d'accord... si tu conçoit un logiciel de compression qui pèse 200Mo, ça ne veut pas dire que les fichiers inférieurs à 200Mo ne sont pas compressés...

[invite6754323456711]

Merci pour la base e, je ne savais pas qu'on pouvait écrire un nombre en base e ; vous ne confondez pas avec les dimensions ..?
Mais c'était pas ma question 439 (base dix) =111001011 (base deux)....9 bits pour écrire ce fichier (?); combien pour l'écrire 3x1 , 2x0 , 1x1 , 1x0 , 2x1 combien pour l'écrire 439 ; en base quatre cent tente neuf il s'écrit...... 10 combien de bits... la même chose, patron ! Non!

Cela n'est qu'une analogie avec les transmissions et ne concerne pas la compression.

Regrouper les bits par symbole (on transmet des symboles à une certaine rapidité de modulation) trouve son intérêt en transmission pour augmenter le débit binaire (bits/s). Exemple de constellation http://fr.wikipedia.org/wiki/Modulat...ature_de_phase

Patrick

[invité576543]

Dans le cas d'un fichier comprimé sur 0 ou 1 bit, cela signifie que c'est l'outil de décompression qui contient l'information. Dans ce cas il n'y a pas compression (l'ensemble "outil de compression decompression" + "fichier compressé" est supérieur à l'ensemble "fichier non compressé")

Oui, mais c'est une situation très courante.

Il y a nécessairement de l'information dans l'outil de décompression. Elle est maximale dans la compression 0-bit, et minimale (nulle) dans le cas où la donnée est transmise telle quelle.

Cordialement,

[invité576543]

Regrouper les bits par symbole (on transmet des symboles à une certaine rapidité de modulation) trouve son intérêt en transmission pour augmenter le débit binaire (bits/s). Exemple de constellation http://fr.wikipedia.org/wiki/Modulat...ature_de_phase

Entre autres. C'est aussi utile pour pour des algo de compression simple, pour les algo utilisant de la redondance pour détecter et/ou corriger des erreurs, etc.

Mais c'est effectivement un leurre que de penser qu'augmenter la taille de l'ensemble des symboles change quoi que ce soit aux performances de compression.

Cordialement,

[jiherve]

Merci pour la base e, je ne savais pas qu'on pouvait écrire un nombre en base e ; vous ne confondez pas avec les dimensions ..?

Bonjour,
Si on peut.
la compacité d'une base c'est le produit du nombre de signes (chiffre = b) par le nombre de ceux ci pour écrire un nombre et le résultat optimal c'est e.
JR

[invité576543]

Bonjour,
Si on peut.
la compacité d'une base c'est le produit du nombre de signes (chiffre = b) par le nombre de ceux ci pour écrire un nombre et le résultat optimal c'est e.
JR

Certes.

Mais quelle est l'importance du nombre de symboles? Une mesure plus intéressante n'est-elle pas le log du nombre de symboles?

Et selon cette dernière mesure, toutes les bases sont équivalentes au premier ordre.

Cordialement,

[jiherve]

Certes.

Mais quelle est l'importance du nombre de symboles? Une mesure plus intéressante n'est-elle pas le log du nombre de symboles?

Et selon cette dernière mesure, toutes les bases sont équivalentes au premier ordre.

Cordialement,

Bonsoir,
Dans ce cas s'il s'agit bien du logarithme naturel alors e est vraiment la meilleure base .
Une question Michel: j'ai lu quelque part que le taux de compression maximal sans pertes était lié à l'entropie des données à comprimer cela a t il un sens?
JR

[Médiat]

j'ai lu quelque part que le taux de compression maximal sans pertes était lié à l'entropie des données à comprimer cela a t il un sens?

Oui cela a un sens : http://perso.telecom-paristech.fr/~r...Entropique.pdf

[jiherve]

Bonjour,
Merci Mediat je stocke ça dans ma doc et le lirais à tête reposée.
JR

[invite4fef019b]

Hello,

Admettons que j'ai en ma possession un algorithme universel de compression capable de compresser sans perte de qualité une vidéo de 4Go dans fichier de compris entre 4 et 5 Mo. Combien ça pourrait se vendre?

[Médiat]

Hello,

Admettons que j'ai en ma possession un algorithme universel de compression capable de compresser sans perte de qualité une vidéo de 4Go dans fichier de compris entre 4 et 5 Mo. Combien ça pourrait se vendre?

Je ne suis pas certain que FSG soit le lieu pour de telles questions, mais si votre algorithme est plus efficace (vous annoncez un taux de 1000:1, connaissez-vous les taux des formats existants ?), et aussi performant en terme de rapidité de compression/décompression, cela doit se chiffrer en millions de dollars (tous les serveurs internet, opérateurs télécom, fournisseurs de contenus video etc. pourraient être intéressé par un système permettant de diviser par un nombre significatif le coût de leurs serveurs,et de leurs communications ...)

[invite4fef019b]

C'était juste un exemple pour comprendre l'importance de la compression de données encore aujourd'hui alors que les débits ne cessent d'augmenter ainsi que les espaces de stockage.
J'imagine que les investissements sur la recherche dans ce domaine doivent être conséquent.
Qu'est ce qui pose problème aujourd'hui?

[invite765732342432]

Qu'est ce qui pose problème aujourd'hui?

A priori, on a atteint une quasi-limite à la compression sans perte de données: les fichiers obtenus ont une distribution de bits proche d'une suite aléatoire donc, à ma connaissance, incompressible.
On doit encore pouvoir grappiller par-ci, par-là, mais c'est mineur.

[invité576543]

Le plus gros des progrès portent sur la compression avec perte.

C'est évident pour le codage de la parole pour la transmettre par exemple.

[Garion]

Ce n'est pas à proprement parler de la compression, mais il est théoriquement possible de stocker n'importe quel fichier avec 3 particules.
Il suffit de les aligner et de les positionner de telle sorte que si l'on fait le rapport entre la distance Particule1-Particule2 et la distance Particule2-Particule3, ça nous donne un nombre à virgule dont les décimales sont un encodage du fichier.

(Je ne veux pas qu'on me parle de distance de planck )

[HachavBanav]

Trouvé !
De 16 cars, je passe à 12...sans perte...sauf qu'il faut 40mn à 1 thread @2.5Ghz pour décompresser...donc, c'est une bonne nouvelle pour Voyager3

[azad]

Salut, hé bien moi j’ai fait mieux, et en toute modestie. Mon système de compression de données permet de compacter d’environ 91% un fichier informatique. Cela ne fonctionne que pour les fichiers texte pur. Je le reconnais, la mise en page et tout ce qui peut enjoliver un texte disparait, mais le résultat est très lisible. Le principe très simple, est basé sur une la théorie controversée dite «*mémoire de l’eau*» Cette théorie qui fit couler beaucoup d’eau en son temps, et dont aujourd'hui personne ne se souvient, s’est avérée applicable dans le domaine de l’informatique.
En gros j’ai pris une copie de cette théorie et j’alterne chacune de ses lignes avec une ligne du texte à compresser. Plus on laisse macérer plus le résultat est significatif, ensuite on supprime les lignes de la théorie devenues inutiles, et on s’aperçoit qu’il ne reste presque plus rien du texte initial. (En gros 10 caractères pour une page de texte)
Evidemment, comme je n’ai pas encore obtenu le brevet, je ne peux pas vous expliquer le principe en détail de la transformation inverse qui restitue le fichier original intégralement. Mais le nom de ma théorie «*Mémoire de l’octet*» devrait peut-être mettre sur la voie (d’eau ) les esprits ouverts et assoiffés de savoir.

[HachavBanav]

...l'algo dont je parle (16 octets ->12 octets) est breveté...mais peut être que le dépositaire acceptera d'en discuter car on ne peux pas en faire grand chose à cause du temps de décompression.