La compression de données
Partie 2 sur 4
3Les familles de compression
Les méthodes se classent selon plusieurs critères qui se croisent. La figure 1 les résume ; détaillons-les.
3.1Compression physique et compression logique
La compression physique agit directement sur les données : elle regarde les motifs redondants d’un train de bits à un autre, sans chercher à comprendre ce que ces bits représentent. Les méthodes de ce type sont générales : elles marchent sur un texte comme sur un programme. La compression logique, au contraire, procède par un raisonnement : elle remplace une information par une autre, équivalente et plus courte. Écrire « 3 × 7 » plutôt que « 7 + 7 + 7 » en est l’image simple ; stocker un cercle d’une image vectorielle par son centre et son rayon, plutôt que par les milliers de points qui le composent, en est une autre.
3.2Compression symétrique et asymétrique
Dans le cas de la compression symétrique, la même méthode sert à compresser et à décompresser, et il faut la même quantité de travail pour chacune de ces opérations. On la retient pour les transmissions de données en direct, comme un appel vidéo, où les deux côtés ont besoin d’aller vite. La compression asymétrique demande plus de travail pour l’une des deux opérations. On cherche souvent des algorithmes où la compression est plus lente que la décompression : le film est compressé une fois, longuement, par le studio, puis décompressé des millions de fois, rapidement, par les spectateurs. À l’inverse, des algorithmes plus rapides en compression qu’en décompression peuvent être utiles pour archiver des données auxquelles on accède rarement, par exemple pour des raisons de sécurité, car ils produisent des fichiers compacts sans immobiliser la machine pendant l’écriture.
3.3Compression sans pertes et compression avec pertes
La compression sans pertes (en anglais lossless compression) restitue exactement les données d’origine, bit pour bit. La compression avec pertes (lossy compression) se permet d’éliminer quelques informations pour atteindre le meilleur taux possible, tout en gardant un résultat le plus proche possible de l’original. C’est le cas de certaines compressions d’images (le JPEG, format de photo le plus courant) et de sons, comme le MP3 (le format de musique compressée le plus connu) ou le format libre Ogg Vorbis. Puisque ce type de compression supprime des informations contenues dans les données, on parle de méthodes irréversibles : une fois la photo réduite, vous ne retrouverez jamais les détails supprimés, même en la recompressant à qualité maximale.
Les fichiers exécutables, c’est-à-dire les programmes, ne peuvent évidemment pas être compressés avec des pertes : ils ont besoin de conserver leur intégrité pour fonctionner. Il n’est pas concevable de reconstruire approximativement un programme en omettant des bits ou en en ajoutant : une seule instruction altérée suffit à le faire planter. Il en va de même des documents, des tableaux de comptes ou des bases de données. En revanche, les données multimédias (audio, vidéo, images) peuvent tolérer un certain niveau de dégradation sans que les capteurs sensoriels (l’œil, le tympan) y perçoivent une altération significative. La compression avec pertes exploite cette tolérance : elle s’appuie sur des modèles de la perception, par exemple le fait que l’oreille entend mal un son faible quand un son fort le couvre. Nous y revenons en partie 7.
3.4Encodage adaptatif, semi-adaptatif et non adaptatif
Beaucoup de méthodes s’appuient sur un dictionnaire ou une table de fréquences, qui dit comment coder chaque élément. Un encodeur non adaptatif utilise un dictionnaire fixe, préparé pour un type de données : par exemple, il suppose que la lettre « e » est la plus fréquente, ce qui est vrai en français et faux dans d’autres langues. Les occurrences des lettres dans un fichier texte dépendent en effet de la langue dans laquelle il est écrit. Un encodeur adaptatif ne part d’aucun dictionnaire préparé : il s’adapte aux données qu’il rencontre et construit son dictionnaire au fil de la lecture. Un encodeur semi-adaptatif procède en deux temps : il construit d’abord son dictionnaire en parcourant tout le fichier, puis compresse le fichier avec ce dictionnaire, qu’il joint au résultat.
Chaque approche a ses forces. Le non adaptatif est le plus rapide, mais pas le plus efficace si les données diffèrent du modèle. Le semi-adaptatif donne un bon taux mais impose deux passes. L’adaptatif traite les données en une seule passe, sans rien joindre : les méthodes de la partie 6 appartiennent à cette famille, ce qui explique leur succès.
4Les plages : concaténation de points et RLE
La plus simple des idées de compression consiste à ne pas répéter ce qui se répète. Elle a été appliquée très tôt aux images, parce qu’une image contient souvent de larges zones uniformes.
4.1La concaténation de points
Avant même de compresser, on peut ranger les données de façon économe. La concaténation de points (c’est-à-dire leur mise bout à bout) est une méthode de stockage optimal : pour une image monochrome, il n’y a par définition que deux couleurs, par exemple noir et blanc. Un point de l’image peut donc être codé sur un seul bit (0 ou 1, voir le binaire), au lieu d’un octet entier. Huit points tiennent alors dans un seul octet, ce qui divise par huit la taille par rapport à un stockage « un octet par point ». Ce n’est pas encore de la compression au sens strict, mais cela montre que la première économie est d’éviter le gaspillage.
4.2Le codage par plages (RLE)
La méthode RLE (Run Length Encoding, « codage par longueur de plage », parfois notée RLC pour Run Length Coding) est utilisée par de nombreux formats d’images, dont BMP, PCX et TIFF. Elle repose sur la répétition d’éléments consécutifs. Le principe de base consiste à coder d’abord un nombre, qui donne le nombre de répétitions d’une valeur, puis la valeur à répéter.
Prenons la chaîne AAAAAHHHHHHHHHHHHHH : cinq « A » suivis de quatorze « H », soit 19 caractères. Compressée, elle donne 5A14H, soit 5 caractères. Le gain de compression est (19 − 5) / 19, soit environ 73,7 %. C’est excellent. Mais prenons maintenant le mot REELLEMENT, où la redondance est faible : un codage naïf donne 1R2E2L1E1M1E1N1T, soit 16 caractères pour 10 au départ. Le gain est (10 − 16) / 10, c’est-à-dire −60 % : la compression a grossi le texte !
En réalité, la compression RLE est régie par des règles particulières, qui permettent de compresser lorsque c’est utile et de laisser la chaîne telle quelle lorsque la compression induirait un gaspillage. Dans la variante utilisée par le format BMP, les règles sont les suivantes :
- lorsque trois éléments ou plus se répètent consécutivement, la méthode RLE est utilisée (nombre de répétitions, puis valeur) ;
- sinon, un caractère de contrôle (00) est inséré, suivi du nombre d’éléments de la chaîne laissée non compressée, puis de cette chaîne elle-même ;
- si le nombre d’éléments de la chaîne est impair, le caractère de contrôle (00) est ajouté à la fin, pour que les données restent alignées par paires d’octets.
Enfin, des caractères de contrôle spécifiques ont été définis pour coder des événements propres à l’image : une fin de ligne (00 01), la fin de l’image (00 00), et un déplacement du pointeur dans l’image de XX colonnes et de YY lignes dans le sens de la lecture (00 02 XX YY), ce qui permet de sauter une zone sans la coder du tout. Ces règles montrent qu’un format réel n’est jamais « juste » l’algorithme : il faut aussi prévoir les fins de ligne, les marqueurs, les cas où l’on ne compresse pas.
La compression RLE n’a donc de sens que pour les données qui possèdent de nombreux éléments consécutifs redondants, notamment les images à larges parties uniformes : schémas, logos, captures d’écran, fax (voir plus bas). Elle a toutefois l’avantage d’être peu difficile à mettre en œuvre : quelques lignes de programme suffisent, et elle est très rapide. Il existe des variantes dans lesquelles l’image est encodée par pavés de points (petits carrés), selon des lignes, ou même en zigzag, un parcours qui augmente les chances de rencontrer des points voisins identiques.
4.3Ce que RLE nous apprend
RLE met en évidence trois leçons qui valent pour toutes les méthodes. Première leçon : une méthode n’est bonne que pour certaines données. Deuxième leçon : il faut une porte de sortie pour les données qui ne se compressent pas, sinon on les grossit. Troisième leçon : le format compte autant que l’algorithme : savoir où finissent les lignes et l’image est indispensable à la décompression.
Pour s’exercer
Exercice 2 : compresser en RLE
Compressez en RLE (nombre puis valeur) la chaîne BBBBBBBBNNNNWWWWWWWWWWWW. Calculez le gain.
Voir la réponse
Huit B, quatre N, douze W : 8B4N12W, soit 7 caractères sur 24. Gain : (24 − 7) / 24, soit environ 70,8 %. Les longues plages sont le cas idéal du RLE.
Exercice 3 : quand RLE échoue
Compressez naïvement « ABCABC » en RLE. Que constatez-vous ? Quelle règle des formats réels évite ce problème ?
Voir la réponse
Chaque lettre est isolée : 1A1B1C1A1B1C, soit 12 caractères au lieu de 6, un gain de −100 %. Les formats réels n’appliquent le RLE qu’à partir de trois éléments identiques consécutifs ; sinon ils insèrent un caractère de contrôle et recopient les données telles quelles.