Reprise du message précédent :
LA COMPRESSION ABSOLUE C4EST LE GRAND SATAN §§
J4INVOQUE LA COMPRESSION ABSOLUE §§§
 
                                       
                                                                           
                           
                             

tout ceci m'a inspiré:
 

Alors il faut appeler
TROLL KILLER

A l'entrainement :  

Ce ne sont pas des trolls, ce sont des domo-kun

M'en fous ils ont la même pilosité pour moi c'est pareil
 

 
BAM - Headshot quand même

Moi je propose d'épingler ce topic parceque je n'ai quand même jamais autant rit depuis très longtemps  

Y'en a qui devraient (re)lire leurs cours de théorie de l'information !

Moi j'aurais pas parlé de lire/relire, simplement d'en prendre.
Ceci étant, je parie que notre génie de l'info s'est déjà rendu compte de son erreur et qu'il est allé se pendre en Arizona.

C'est pas avec des remarques aussi conformistes et rétrogrades que l'on va redresser le déclin de la France.
Je veux croire.

Non mais un peu de sérieux, c'est pas au temps du Général que le premier loufiat venu aurait pu radiner ses guêtres en prétendant révolutionner le monde! Ce genre de racaille gauchiste aurait été prestement exilée.

Si tu pouvais éviter de raconter n'importe quoi ce serait cool en fait

 
Dans le contexte de ce topic, je trouve cette phrase spécialement goûtue

Ouais mais non hein, raconter des conneries plus grosses que soi auké, mais pas manquer de respect au général

 
Non mais j'ai pas manqué de respect au général
Je disais que de son temps, gingembre1 aurait été envoyé au bagne manu militari

Il te remercie.

hé bé...
 
de toute façon, je vous met tous minables.
 
moi je peux vous compresser n'importe quel fichier ASCII avec un gain de compression minium de 1/8, c'est sûr et certain.
 
alors passer de 4096 à 4016...

Moi je connais un algo de compression super balèze qui non seulement peut compresser à peu près n'importe quoi, mais rajoute de la valeur aux données comprimées.
 
Ca s'appelle l'algo de César.
 
 
 
Exemple:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Avant:

 
Après:

 
Et le pire, c'est que c'est encore plus cher après.

en plus l'algo de césar ça a existé, c'était un algo de cryptage utilisé pendant l'antiquité (décalage des lettres de l'alphabet il me semble)

c'est d'ailleurs le premier algo de cryptage dont on aie la trace aujourd'hui

En fait ce serait le second
http://lwh.free.fr/pages/algo/crypto/cesar.htm
 
Et sinon, il a inventé le calendrier Julien, qui est à 11 minutes près, le calendrier actuel, le grédorien (y'a juste les années bissextilles des sciècles qui manquent). Et c'était déjà à l'époque les mêmes noms de mois que maintenant (quel homme )
http://fr.wikipedia.org/wiki/Calendrier_julien

Mon algorithme compresse de façon bijective 1337 bits en 1295 soit .. bits de gagnés à chaque cycle de compression.

Pas réellement.
Avant la technique de César, il esistait d'autres algos plus primitifs. Le tout premier connu est attribué à Nabuchodonosor (7° siècle avant JC) qui rasait la tête de ses esclaves pour y inscrire un texte et laissait ensuite les cheveux repousser. Mais cette technique est plus classée dans le domaine de la stéganographie (art de cacher un texte) plutôt que cryptographie (art de rendre un texte incompréhensible).
En fait, un des premiers algos de cryptographies connu est la "scytale" (5° siècle avant JC donc 4° siècle avant César). On enroule une bande autour d'un baton de diamètre précis (la scytale) et on écrit le texte en vertical. Une fois le bandeau déroulé, le texte est incompréhensible jusqu'à ce qu'on place la bande sur un baton de diamètre identique. Mais cet algo ne fait que changer l'ordre des lettres sans changer la lettre elle-même. En fait, l'algo de César est le premier algo connu où une lettre est remplacée par une autre...

En lisant ce topic, drolatique, j'ai quand même un question:
 
Qu'entendez-vous par entropie d'un nombre ?

 
pas un nombre, mais plutôt des données, même si un nombre sur un très grand nombre de bits peut être assimilé à une petite quantité de données.
L'entropie c'est une façon formelle de mesurer le "désorde, l'irrégularité" des données.
Par exemple :
01010101010101010101010101010101010101010101010101010101010101010101010101010101
 a peu d'entropie car c'est une suite régulière de "01".
01111100010101000100010100111101010101000010101000111010101000111111011101010010
 a beaucoup plus d'entropie car c'est une suite irrégulière, il serait dificile de la résumer. La première pourrait être compressée en "(01) quanrante* fois". La deuxième, ça serait plus dur.
 
Ca existe en physique et en chimie aussi l'entropie.
 
* : j'ai pas compté sil y en a 40, c'est un exemple

Merci pour le truc.
Mais quand tu compresses des datas, on est obligé de faire ça en plusieurs passes ?
Ex: une pour voir les séquences revenant le plus souvent, l'autre pour créer le fichier ?
Dans ce cas, doit-on imposer une longueur minimale de séquence (style sur 2 bits, 4 bits, etc...) ? Ou c'est plutot une algo type backtracking ?

il y a des techniques qui font ça en deux passes.
 
le plus courant pour du sans pertes et d'avoir un dictionnaire qui est actualisé au fur & à mesure du compresses.

+1 les compresseurs modernes font plusieurs passes.

j'ai rien compris a ce que gimgembre veut faire ... si c juste codé certaines info sur moins de bit (les moins presentes) ca deja ete fait depuis longtemps (Huffman)
 

gingembre croit avoir trouvé un algo qui compresse tout type d'infomation sur moins de bits. C'est juste le 1000e type croyant avoir trouvé l'algo de compression absolue qui n'existe pas et dont on a prouvé (facilement) la non-existance...

Pour répondre à la question posée au début:
 
A titre indicatif: au bout de 15 secondes d'attente d'une page web, 50% des internautes abandonnent. Une page web moyenne mesure dans les 10Ko.
 
La compression est finalement peu utilisée à cause de ces contraintes de temps. Autre exemple, tous les OS peuvent d'une manière ou une autre compresser automatiquement toutes les données d'un disque, mais comme celà multiplie par deux le temps d'accès au disque, extrèmement peu de gens utilisent la compression systématique (en fait je n'en connais pas, et l'utilisateur lambda n'est même pas au courant de ces options, même les systèmes de sauvegarde évitent les disques compressés et préfèrent le sytème de disques en parallèle qui en fait multiplie par un facteur constant la taille des données).
 
Ce qui se fait couramment, par contre, est la compression systématique de certains types de fichiers, ou de certains moyens de transmission lents.
Pour les fichiers, la compression avec perte peut être énormément plus avantageuse: pour un signal physique donné (son, photographie, vidéo, etc...) une compression avec pertes limitées/contrôlées permet un énorme gain de compression contre la plus petite perte de qualité discernable par nos sens (ou dans certains cas par un appareil de mesure).
Pour les moyens de transmission lents, ils est possible qu'ils aient tendance à se raréfier puisque les connexions internet actuelles mettent les processeurs à genoux déjà sans compression.
 
Pour résumer, donc, la compression sans perte a un rapport compression/attente qui est dores et déjà peu apprécié des utilisateurs, et un rapport gain-de-mémoire/puissance-de-calcul trop élevé pour les processeurs. Plus de compression contre plus de temps n'arrange pas non plus l'utilisateur moyen, qui recherche plutôt plus de compression en moins de temps.
 
L'avenir d'un hypothétique algorithme de compression qui puissent compresser toutes les données présentes dans toutes les bibliothèques du monde dans une puce de la taille d'un ongle est la suivante: envoyer la puce dans une sonde spatiale pour voir si dans quelques millions d'années les extra terrestres pourront décompresser ces données et y répondre. Le reste est pure science-fiction.
 
PS: vérifie quand même que ton algo est capable de décompresser, à te lire on en douterait.
 
kfman>
En général, la compression sans perte s'effectue en effet en plusieurs passes, et sur des blocs de taille limités. Une entête est ajoutée avec les infos de décompression (dictionnaire) suivie des données compressées, pour chaque bloc. Augmenter la taille des blocs de compression améliore la compression (de peu) et augmente les temps de calcul (de beaucoup) et de mémoire temporaire (d'autant). Les algos actuels explorent grosso modo N*N possibilités, l'ordre de grandeur du temps de calcul est à peu près proportionnel au carré du bloc à compresser. L'utilisation de blocs rends le temps d'éxécution de ces algorithmes proportionnel à la taille totale à compresser, tout en gardant beaucoup de gain de compression.
 
La compression avec perte est un poil plus compliqué: en général on passe par un modèle mathématique intermédiaire de type fréquenciel, puis on élimine artificiellement certaines fréquences en dehors du champ d'intérêt, puis un algo de compression sans perte est appliqué. Ainsi, les JPEG de base sont coupés en blocs de 16x16 ou 8x8 pixels puis les couleurs et motifs simplifiés et répertoriés dans un dictionnaire, les fichiers MP3 en blocs de quelques millisecondes à quelques secondes puis les fréquences inaudibles ou trop faibles ou trop proches éliminées. DIVX fait une analyse fréquentielle en 3D (largeur, hauteur, temps), puis élimine les fréquences trop élevées. MPEG (entre autre les DVD) ressemble à JPEG, avec en plus une compression dûe à la persistence de blocs d'une image vidéo à l'autre. On peut remarquer les artefacts de la compression avec perte: à la télé quelques fois lors de mauvaise réception/transmission les blocs de pixels colorés peuvent apparaître, sur les fichiers MP3 trop compressés on n'entends que la voix du chanteur et moins bien les instruments ou parfois la voix paraît comme <<robotisée>> (suppression de trop de fréquences). En ouvrant un JPEG avec un logiciel de retouche, et en changeant le contraste au maximal, on observe les blocs 8x8 qui apparaissent.
 
Comme les blocs de compression sans perte ne correspondent pas forcément à ceux de compression avec perte, il est possible de gratter quelques pourcentages de compression sur des fichiers de type MP3 ou DIVX, en appliquant une post-analyse fréquentielle (fonction dérivée, non destructive) supplémentaire et en recompressant sans perte. Ça ne fonctionne pas sur du JPEG de base, qui possède des tailles de bloc sans/avec perte identiques.
 
Outre les infos de décompression, les blocs peuvent contenir d'autres infos, notamment des infos de reprise comme par exemple les MP3 et les MPEG qui contiennent un tag bien reconnaissable en début de trame. Lorsque le fichier est tronqué ce code permet de reconnaître le début d'une trame et de reprendre la lecture audio/vidéo. Certains formats de compression sans perte, comme les .Z, possèdent aussi ce type de tag de reprise, et aussi des codes de contrôle pour vérifier l'intégrité du bloc (code de contrôle de base: somme de tous les octets du bloc modulo 256, mais aussi MD5 ou SHA1 (logiciels peer-to-peer)).
 
La description exacte des formats ZIP, GZIP, JPEG, MPEG, ou MP3 peut facilement être trouvé sur le net.

super nargy enfin une reponse un peu constructive qui apporte autre chose que tout les trolls de ce topic... (qui nont rien a foutre ici je crois que gimgembre a bien compris quon etait pas daccord avec luià
 
 

 
 
par contre la je comprends pas / plus
 

 
par contre ca je savais pas je pensait que c'était une variante du mpeg ... tu c nous en dire plus la dessus ??? (sans entrer dans les détails)  

Euh, c'est pas trop vrai ton truc. La plupart des serveurs web utitilise par défaut la compression GZIP sur les documents qu'ils envoient aux clients. Autant ZIP, pour les images et autres documents binaire n'apporte pas grand chose, autant pour le texte, ça réduit quand même la taille de 80 à 90% (surtout pour du HTML d'ailleurs, à cause du nombre de répétitions de mots et phrases entiers dû au langage). Pour les images, elles sont de toute façon déjà compressées en JPG, PNG ou GIF, ce qui correspond à des taux généralement suppérieurs à 90%. Donc pour moi, le web, c'est au contraire un mauvais exemple pour dire que la compression est inutile
 

C'est plus ou moins vrai. En effet, personnes ne l'utilise, mais surtout parceque la compression sur un disque déjà rempli est très lente, et que le gain (autour de 10% dans le meilleur des cas) est négligeable surtout quand on voit la taille des disques actuels.
Mais les CPU actuels permettent, au contraire, de gagner en vitesse par rapport à l'utilisation de données non compressées.
 
En effet, compresser/décompresser 1 Mo avec les algo simples utilisés pour la compression FS, ça prend beaucoup moins de temps de lire effectivement sur le disque des informations en plus. C'est d'autant plus vrai sur un disque fragmenté, puisqu'avec moins de fragments, on gagne quasi 10 ms de temps d'accès à chaque fragment économisé.

La bande passante d'une connexion internet très haut débit (je parle de la de la fibre optique là) est du même ordre de grandeur que celle des CPUs même les plus récents.
Celà veux dire que si tu télécharge à la vitesse de la fibre optique, et que tu dois décompresser en même temps, tu n'utilise pas toute la bande passante internet puisque le CPU ne peut plus suivre le débit, tant et si bien qu'avec la compression c'est au final plus lent de télécharger un fichier, alors que justement la compression dans la transmission de donnée devrait servir à diminuer les temps de transmission.
 
Quand au DIVX, je ne l'ai pas étudié en détail. Aussi je ne pourrait pas être exhaustif sur l'implémentation. Par contre le principe reste le même que MP3 et il est plus simple de raisonner avec MP3 puisque l'analyse fréquentielle se fait en 1 dimension seulement.
 
L'algo utilisé est le même: le fameux FFT, ou Transformée Rapide de Fourrier. Cet algorithme en O(n*ln(n)) aisément implémentable par des circuits électroniques digitaux (balladeurs MP3), et utilisable aussi bien avec des nombre flottants que des nombre entiers, transforme une onde (valeur physique bornée en fonction du temps) en spectre fréquentiel avec pour chaque fréquence analysée son intensité.
 
L'opération contraire pour passer d'un spectre fréquentiel à une onde est faite en O(n), et reconstitue le signal original (avec quelques erreurs de calculs cependant pour le calcul flottant).
 
Le truc, c'est que de la représentation en onde à celle de spectre, on n'a pas augmenté l'entropie (le nombre d'informations interessantes), donc le fichier se compresse potentiellement vers la même taille que la représentation en onde.
 
Mais par contre on peut éliminer des fréquences: celle qui ne sont pas audibles, celles qui sont trop proches et celles qui sont trop faibles. Du coup, en contrôlant les informations éliminées, on contrôle aussi la qualité du rendu final. Par la même occasion, on retire des informations du fichier original, et la compression s'en trouve améliorée.
 
Pour le DIVX, idem, sauf que cette fois la transformée de Fourrier se fait en 3D: largeur, hauteur, temps. L'analyse fréquentiel est alors un spectre en 3D difficillement représentable, mais dont on peut aussi retirer des fréquences. Dans le DIVX la suppression des hautes fréquences sont privilégiées: ainsi l'image se trouve lissée, aussi bien en hauteur, largeur et temps. Un pixel isolé sur une image qui présente des caractéristiques de couleur très différentes de ses voisins aura tendance à disparître. De même les parasites qui apparaissent d'une image à l'autre sont lissé. Enfin, les fréquences dont l'intensité est trop faible sont éliminées.
 
Mais, dans ces méthodes, il y a deux types d'inconvénients:

• en retirant des informations au signal original, on l'affaiblit, il faut donc l'amplifier à la lecture, et le calcul du facteur d'amplification peut être gourmand (théoriquement il faut décompresser pour le caculer exactement, mais des méthodes de calcul approchées peuvent suffire).

Ainsi, il peut s'avérer que sur des vidéo DIVX l'image soit assombrie, et les zones noires étendues. En MP3, c'est plus facile et donc précis à calculer, mais il peut s'avérer que l'amplitude finale ne soit pas la même (inaudible ou écrêté).

• retirer certaines fréquences peut être nuisible. Anisi des filtres heuristique prédéfinis permettent de garder la qualité dans des cas extrèmes. Pour le MP3, on tente de garder au mieux les fréquences entre 400 et 4000Hz qui correspondent à la voix humaine, et les instruments de musique peuvent être diminués. Le rendu des graves étant plus précis (question de fréquence), les intruments de percussion sont en général de bonne qualité, ce qui convient en général très bien à la musique rock/pop/techno, mais les amateurs de musique classique sont plus exigents. Pour la vidéo, il y a deux types de problèmes du même ordre: la qualité des mouvements, et la sur-qualité des images. En effet, en supprimant trop de fréquences, on peut se retrouver avec une image floue dans les scènes rapides (explosions, effets spéciaux,...) puisque la compression tend à supprimer les hautes fréquences. Au contraire, pour compresser un dessin animé, le nombre de couleurs dans une image donnée est très limité, et les formes simples, aussi un meilleur taux de compression peut être atteint en éliminant encore plus les hautes fréquences correspondantes aux dimensions hauteur&largeur.

Voilà, en gros, une autre notion importante dans la compression avec perte, est celle de VBR (variable bit rate, vitesse variable). En effet, tout au long d'une vidéo, ou d'un morceau de musique, différentes scènes s'enchaînent avec des caractéristiques différentes. VBR précalcul dans une première passe quelle est la complexité fréquentielle de l'image/signal audio, puis tout en gardant un taux de compression global moyen, augmente la compression des silences audio, des scènes vidéo sombres ou lentes, et au contraire augmente la qualité des passages avec beaucoup d'instruments, et des scènes vidéo rapides.

Pas par défaut non (mais c'est rarement compliqué d'activer GZIP ou Deflate)

C'est ce que j'ai écrit, en effet, mais celà ne s'applique pas forcément aux serveurs Web, je parlais dans un cas plus général.
A peu près 10% des serveurs web utilisent la compression GZIP (je n'ai pas personnellement vérifié ce chiffre, il pourrait s'agir du nombre de pages).

Heu, en ce qui concerne les serveurs web, la compression est redondante: que ce soit du modem des années 90 aux connexions ADSL2.0, ces protocoles compressent déjà les données, certe avec des algo rapides et peu efficaces, mais tout de même les suites d'espaces dans les pages web sont déjà compressés.

Non, ce n'est pas le cas. Si ça l'était, un simple GZIP ne fournirait pas des gains allant fréquement de 70 à 85% sur les pages web ou les CSS.

Exact, c'est fort possible, la compression étant généralement inactive par défaut. Voir le protocole PPP.

Page HFR : 100Ko
Page sncf.fr : 130ko
Page accueil Elysée.fr : 135ko
Page Google.com : 10Ko
Page yahoo.fr : 132 Ko
http://fr.wikipedia.org/wiki/W3C : 103 ko
http://www.w3.org/ : 73Ko
 
Je voudrais bien savoir où tu as trouvé tes 10ko de moyenne
 

Pour les pages web heureusement que la compression est utilisée (mod Gzip) ca permet de passer l'ensemble d'une page (texte, html, css, js) à 50% de la taille originelle. Et c'est un plus non négligeable.
 
Edit : burned x10