Ceci est une traduction automatique ; le texte original est en anglais. Consulter l'original
Aucun compresseur ne peut réduire tous les fichiers, et la démonstration tient en un paragraphe
Tous les quelques ans, quelqu'un annonce un algorithme réduisant n'importe quel fichier de 50 %. Appliqué deux fois, il réduirait n'importe quel fichier d'un quart, et appliqué suffisamment de fois, à un seul bit.
Considérez l'ensemble des fichiers possibles de exactement 1 000 bits. Il y en a 2¹⁰⁰⁰. Considérez maintenant tous les fichiers possibles plus courts que cela — 999 bits, 998, et ainsi de suite jusqu'à zéro. Additionnez-les et vous obtenez 2¹⁰⁰⁰ − 1 fichiers, soit un de moins qu'au départ.
Un compresseur sans perte doit associer des entrées distinctes à des sorties distinctes, sans quoi il ne pourrait pas être réversible. Or, il est impossible de faire entrer 2¹⁰⁰⁰ éléments dans 2¹⁰⁰⁰ − 1 boîtes sans en placer deux dans la même boîte. Aucun compresseur sans perte ne peut donc réduire toutes les entrées. S'il en réduit certaines, il doit nécessairement en agrandir d'autres.
Aucune hypothèse sur l'algorithme n'a été nécessaire, donc aucune astuce ne permet d'y échapper. C'est le principe des tiroirs, et c'est ce qui explique pourquoi tout compresseur réel présente un pire cas où la sortie est légèrement plus grande que l'entrée : le fichier original plus quelques octets d'en-tête.
Ce qui est réellement exploité
La structure. La compression ne supprime pas la « redondance » au sens flou du terme ; elle réattribue les codes courts aux éléments fréquents.
Le texte en anglais est extrêmement prédictible. Après « th », la lettre suivante est de très loin le « e ». Les espaces représentent le caractère le plus fréquent. Une image de mur présente de longues suites de pixels presque identiques. Dans chaque cas, le fichier, considéré comme une variable aléatoire, possède une faible entropie — l'incertitude moyenne par symbole est faible — et Shannon a démontré en 1948 que cette quantité constitue la borne inférieure exacte. On ne peut pas coder une source avec moins de bits par symbole que son entropie, et on peut toujours s'en approcher arbitrairement près.
Ce qui fait de la compression une compétition de prédiction. Un compresseur qui modélise bien la source attribue des codes courts avec précision et atteint un niveau proche de l'entropie. Un compresseur qui la modélise mal gaspille des bits. C'est pourquoi l'état de l'art en compression de texte ressemble de plus en plus à un modèle de langue : bien prédire le symbole suivant et bien compresser sont un seul et même problème sous des habits différents.
Vous pouvez observer la convergence vers cette limite dans l'outil Entropy Coding, et visualiser l'attribution des codes elle-même dans Huffman Encoding.
Pourquoi compresser une archive ZIP ne produit aucun effet
La structure d'un fichier bien compressé a été éliminée. Ce qui subsiste ressemble, statistiquement, à du bruit : chaque symbole est à peu près équiprobable, sans corrélation utile entre voisins. Son entropie par bit est proche de 1, il ne reste donc plus rien à exploiter, et une seconde passe le rendra généralement très légèrement plus grand — en raison de l'en-tête, auquel s'ajoute l'incapacité du compresseur à trouver le moindre motif digne d'être codé.
Cela explique également pourquoi un fichier JPEG dans une archive ZIP ne réduit pratiquement pas, pourquoi des données chiffrées sont incompressibles (un bon chiffrement est spécifiquement conçu pour ressembler à du bruit), et pourquoi compresser avant de chiffrer est le bon ordre — après chiffrement, il n'y a plus rien à compresser.
La version honnête du « 50 % plus petit »
Toute affirmation sincère sur la compression porte sur une classe d'entrées. « Réduit de moitié la taille d'un texte en anglais » est une déclaration réelle et utile. « Réduit de moitié la taille de n'importe quel fichier » est démontrablement faux, et la preuve en est le paragraphe ci-dessus.
Le cas de la compression avec perte, un tout autre sujet
Rien de tout cela ne s'applique à la compression avec perte, car elle n'a pas à être réversible. Le JPEG, le MP3 et tous les codecs vidéo éliminent délibérément des informations, en choisissant ce qu'ils abandonnent à l'aide de modèles fondés sur ce que les yeux et les oreilles humains ne perçoivent pas.
La question ne devient plus « quelle est la quantité de structure présente », mais « quelle quantité peut être éliminée avant que quiconque ne s'en plaigne », ce qui est une question de perception plutôt que de mathématiques. C'est aussi pourquoi le compromis de la compression avec perte comporte un curseur d'ajustement, contrairement à celui de la compression sans perte : l'entropie est une propriété intrinsèque des données, tandis que la distortion acceptable est une appréciation propre aux destinataires.
Le seul point commun entre les deux est qu'une spécification honnête est toujours conditionnelle. Un compresseur sans perte est performant pour une classe d'entrées. Un compresseur avec perte est performant à un niveau de distortion donné.