La compression de données expliquée

Chaque page web que vous chargez, chaque fichier ZIP et chaque image PNG a été compressé : rendu plus petit sans perdre un seul bit, puis décompressé à l'arrivée. Les méthodes qui le permettent sont étonnamment simples. Elles cherchent ce qui se répète et disent « comme avant » au lieu de le redire. Jusqu'où cette idée mène, et où elle s'arrête, c'est l'une des plus belles histoires de l'informatique.

Une ligne de texte dont les passages répétés sont remplacés par des flèches pointant vers leur première apparition, à côté de barres montrant la taille originale et la taille compressée
Une ligne de texte dont les passages répétés sont remplacés par des flèches pointant vers leur première apparition, à côté de barres montrant la taille originale et la taille compressée

Sans perte et avec perte

La compression existe sous deux formes. La compression sans perte redonne exactement l'original, ce qui est indispensable pour le texte, les programmes, les tableurs et tout ce où un seul bit erroné compte. La compression avec perte, utilisée pour les photos, la musique et la vidéo, supprime des détails que l'on perçoit à peine et atteint des tailles bien plus petites, mais l'original est perdu pour de bon. Cette page et le démonstrateur traitent de la compression sans perte, qui consiste à trouver et à supprimer la redondance : les parties des données qui auraient pu être prédites.

Le codage par plages

La méthode la plus simple remplace une plage de symboles identiques par un compte et le symbole : douze pixels blancs deviennent 12W (W pour « white », blanc). Les télécopieurs, les premiers formats bitmap et le format d'image PCX l'utilisaient, car les pages numérisées et les dessins simples sont pleins de longues plages. Sur un texte ordinaire, il est inutile, voire nuisible : les plages sont rares, et écrire un compte pour chaque lettre double la taille. Le codage par plages survit pourtant à l'intérieur d'autres méthodes, pour les suites de zéros laissées par une première transformation.

LZ77 : renvoyer en arrière

En 1977, Abraham Lempel et Jacob Ziv, deux chercheurs du Technion, en Israël, publièrent une méthode qui transforma le domaine. Le codeur garde une fenêtre du texte qu'il vient de traiter. Si les caractères suivants figurent déjà dans la fenêtre, il écrit une paire : à quelle distance en arrière commence la copie antérieure et quelle est sa longueur. Sinon, il écrit le caractère lui-même. Le décodeur n'a besoin d'aucun dictionnaire, seulement du texte qu'il a déjà reconstruit. Une référence peut même chevaucher le texte qu'elle produit, si bien qu'une plage de 100 lettres identiques se résume à une lettre et une référence.

Abraham Lempel, qui avec Jacob Ziv au Technion en 1977 publia la méthode de fenêtre et de références aujourd’hui appelée LZ77.
Abraham Lempel, qui avec Jacob Ziv au Technion en 1977 publia la méthode de fenêtre et de références aujourd’hui appelée LZ77.

LZW : apprendre un dictionnaire

La seconde méthode de Lempel et Ziv, LZ78, construit un dictionnaire au lieu de regarder en arrière dans une fenêtre. Son perfectionnement par Terry Welch en 1984, LZW, part des 256 valeurs d'octet et, à chaque étape, envoie le numéro de la plus longue chaîne qu'il connaît déjà, puis ajoute cette chaîne suivie du caractère suivant comme nouvelle entrée. Le décodeur reconstruit le même dictionnaire à partir des seuls numéros. Rapide et simple, LZW a été adopté par la commande Unix compress, le format d'image GIF et les fichiers TIFF, jusqu'à ce que les brevets qui le protégeaient provoquent un long conflit dans les années 1990.

Deflate, ZIP et au-delà

La méthode deflate de Phil Katz, introduite avec PKZIP 2 en 1993, combine LZ77 avec le codage de Huffman : une fois les répétitions trouvées, elle attribue les codes binaires les plus courts aux littéraux, longueurs et distances les plus fréquents. Deflate est utilisé dans ZIP, gzip, les images PNG et la compression des pages web, et c'est la méthode que le démonstrateur mesure avec le compresseur intégré au navigateur. Des méthodes plus récentes comme Zstandard, Brotli et xz utilisent des fenêtres plus grandes, une recherche de correspondances plus fine et un codage entropique plus précis, et réduisent les fichiers courants de 10 à 30 % supplémentaires.

Pourquoi tout ne peut pas rétrécir

Aucune méthode ne peut réduire tous les fichiers. Il existe 2ⁿ fichiers de n bits, mais seulement 2ⁿ − 1 fichiers plus courts ; si une méthode les réduisait tous, deux d'entre eux aboutiraient au même résultat et ne pourraient pas être restitués tous les deux : c'est le principe des tiroirs. Tout compresseur agrandit donc certaines entrées, en général des données d'apparence aléatoire comme les fichiers chiffrés, les fichiers déjà compressés et le bruit. C'est aussi un test du caractère aléatoire : des données qu'aucun compresseur ne parvient à réduire ont l'air aléatoires.

La limite de l'entropie

Claude Shannon a montré en 1948 que l'entropie d'une source est le plus petit nombre moyen de bits par symbole possible pour un code sans perte. Comptée lettre par lettre, l'entropie d'un texte anglais est d'environ 4 bits par lettre, la moitié des 8 bits dans lesquels il est stocké. Les méthodes qui exploitent le contexte, comme LZ77, descendent sous ce chiffre lettre par lettre sur un texte répétitif, car une référence représente tout un passage à la fois. Les meilleurs compresseurs modernes, qui prédisent chaque lettre à partir de tout ce qui précède, ramènent l'anglais à moins de 2 bits par lettre.

Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.
Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.

À vous d'explorer

Ouvrez le démonstrateur de compression pour appliquer LZ77, LZW et le codage par plages à un paragraphe, une chanson avec refrain, une ligne de pixels, un tableau de données, des lettres aléatoires ou de l'ADN, ou à votre propre texte. Cliquez sur une référence LZ77 pour voir ce qu'elle copie, regardez le dictionnaire de LZW grandir, et comparez toutes les méthodes avec ZIP et la limite d'entropie.

Questions fréquemment posées

Que signifie un taux de compression de 3 : 1 ?

Que l'original est trois fois plus gros que la version compressée : le fichier compressé occupe un tiers de la place et en fait économiser deux tiers. Avec ZIP, un texte atteint en général 2 : 1 à 4 : 1 ; des données très répétitives, comme des fichiers journaux, souvent bien davantage.

Pourquoi compresser à nouveau un fichier ZIP ne sert-il à rien ?

Le premier passage a déjà supprimé les répétitions, et son résultat paraît presque aléatoire. Un second passage ne trouve rien à quoi renvoyer et ne fait qu'ajouter son propre surcoût : le fichier garde la même taille ou grossit légèrement.

Pourquoi une fenêtre LZ77 plus grande est-elle meilleure ?

Une fenêtre plus grande permet au codeur de trouver des répétitions situées plus loin en arrière, comme un refrain qui revient après plusieurs couplets. En contrepartie, chaque distance demande plus de bits et la recherche prend plus de temps ; c'est pourquoi deflate s'arrête à 32 KB, tandis que les méthodes plus récentes autorisent des mégaoctets.

La compression est-elle la même chose que le chiffrement ?

Non. La compression rend les données plus petites, et n'importe qui peut l'annuler ; le chiffrement rend les données illisibles sans clé. Les deux sont souvent combinés, et il faut alors compresser d'abord : des données chiffrées paraissent aléatoires et ne peuvent plus être compressées.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le démonstrateur de compression