Compression de Données

La compression de Données est un Processus automatisé activé pour réduire la taille physique des messages ou Fichiers Numériques.

Un Logiciel de compression de données intègre généralement deux Algorithmes complémentaires :

• Le compresseur se charge du Transcodage du fichier initial pour réduire le nombre de Bits à stocker. Le fichier résultant a un Format spécifique de compression (pour exemple connu : ZIP).
• Le décompresseur active également un algorithme de transcodage qui rétablit les données sous leur format antérieur à la compression.

La compression des données a deux justifications principales : réduire l’espace requis pour le stockage ou l’archivage des données ; réduire le temps nécessaire à la transmission effective d’un fichier.
La pratique de la compression des données a été encouragée par la croissance rapide de la puissance des Processeurs (voir à ce sujet l’article relatif à la Loi de Moore), comparativement aux progrès du débit des réseaux ou de la capacité de stockage des supports numériques.

Les Logiciels du marché annoncent aujourd’hui des gains en volume de 50 % des textes, de 80 % des images fixes et jusqu’à 95 % des vidéos. Mais mesurer l’efficacité d’un logiciel de compression des données est un exercice complexe qui doit considérer trois critères complémentaires :

1. L’espace de stockage économisé (que constate le taux de compression des données) ;
2. Les ressources et le temps consommé par les compressions et décompressions des données ;
3. L’Information éventuellement perdue lors du transcodage.

Comme toujours, la pertinence du choix d’un logiciel dépend du contexte auquel son application est destinée. Typiquement :

• Quel est le Format des données à compresser ?
  Le format dépend lui-même de la nature de l’information numérisée (texte, multimédia, exécutable, etc.). Selon la structure du format original et le contenu spécifique du fichier, le taux de compression constaté sera plus ou moins élevé.
• Quels sont les bénéfices attendus ?
  Est-ce la réduction du volume de stockage ou plutôt l’optimisation du temps de transport des données ?
• Les données supportent-elles d’être transformées par la compression ?
  Certains algorithmes de compression modifient irrémédiablement les données sources. On parle alors de compression non conservatrice (en anglais « Lossy compression », ou compression avec perte [de données]). Ces solutions sont particulièrement adaptées aux supports multimédias. Ainsi, le format MP3 permet la compression efficace de sons et de vidéos, avec une perte de qualité réelle, bien que difficilement perceptible par notre système sensoriel.
  Mais certaines applications exigent un algorithme conservateur (en anglais « Lossless compression », ou compression sans perte). C’est par exemple le cas pour un fichier contenant un Programme (source ou exécutable) pour lequel l’intégrité du code original programmé doit être strictement respectée.
• Combien de fois le fichier compressé sera-t-il décompressé pour être utilisé en entrée d’un traitement ?
  Il est souvent pertinent de compresser les textes à archiver et de laisser en l’état ceux qui seront consultés fréquemment.
  Un logiciel de compression est qualifié d’asymétrique quand le temps moyen nécessaire à la compression des données est significativement différent de celui nécessaire à leur décompression. Ainsi, en environnement industriel, au-delà du seul taux de compression, cette asymétrie des logiciels de compression participe de leur pertinence :
  • Lorsque la compression des données se justifie pour limiter l’espace requis par l’archivage de données, la fréquence des compressions est supérieure à celle des décompressions. On favorisera les solutions dont la compression est peu consommatrice.
  • Quand la fréquence des compressions est moindre, on favorisera au contraire l’efficacité de la décompression.

Quand faut-il compresser les données?

1. Le stockage des données a des contraintes techniques et financière, mais la pertinence de leur compression dépend des priorités fonctionnelles que se fixe le décideur. 
   Pour illustration, considérons deux utilisateurs d’un appareil photographique numérique Canon, un touriste et un photographe professionnel ou passionné. Le paramétrage de leur appareil permet un stockage de ses photos au format ‘.raw’ (format propriétaire du constructeur de l’appareil) ou au format ‘.jpeg’, moins consommateur d’espace sur sa carte mémoire mais rendant irréversible le retour au format natif ‘.raw’ .
   Le touriste favorisera le paramétrage ‘.jpeg’, lui garantissant le stockage d’un maximum de cliché sur un minimum de cartes mémoires.
   Un professionnel privilégiera le stockage intermédiaire de ses clichés sous le format ‘.raw’. Plus gourmand en terme de stockage immédiat, ce format natif ouvre par contre une plus large palette de traitements numériques  postérieurs.
2. Quand la vitesse de transfert des données est cruciale, l’optimisation de la taille des fichiers échangés est la réponse efficace, mais le traitement de leur compression a un coût.

• Améliorer conjointement la rapidité et la performance des algorithmes de compression est d’abord une demande de la recherche et de l’industrie (domaine médical, nucléaire, transmissions spatiales de longue distance, etc.) plus que des utilisateurs particuliers de l’informatique. Dans le domaine de l’HPC (« High-Performance Computing », traduit souvent en français par Supercalculateur), gagner du temps sur l’acheminement sans perte des données est essentiel pour accroître la réactivité globale du Système d’Information.
  L’objectif est atteint quand le temps total de compression, de transmission et de décompression du fichier est inférieur au seul temps de transmission du fichier non compressé.

• De même, pour les particuliers qui conçoivent leur Site Internet, la compression des Fichiers Multimédia qu’il contient est une condition de la fluidité de son utilisation.

Les Algorithmes de compression :

Ce paragraphe est une présentation très sommaire des principaux algorithmes de compression sans perte. Elle pourra être complétée par la lecture des nombreux descriptions ou exemples de programmation de ces algorithmes disponibles sur l’Internet.

• Les premiers messages compressés ont été envoyés en Morse, code précurseur des communications numériques : à chaque signe de l’alphabet Morse international est associé un codage unique constitué d’une séquence d’impulsions courtes et longues. Pour raccourcir la longueur des messages, les combinaisons les plus courtes ont été assignées aux lettres les plus fréquemment utilisées (E = ; T = — ; I = •• ; etc.) et les combinaisons les plus longues aux lettres les plus rares (Q = — — • —, Y = — • — — ; Z = — — • •).
• En 1952, l’Américain David Huffman, thésard au MIT (« Massachusetts Institute of Technology ») a proposé un système de compression sans perte des données reposant également sur une analyse statistique. Ses principales phases consistent à :
  • Élaborer un dictionnaire des mots ou séquences codées dans le message d’origine (par l’analyse des Octets constituant les données à compresser) ;
  • Mesurer la fréquence de chacun des mots dans le message d’origine ;
  • Associer à chacun des mots une nouvelle séquence numérique d’autant plus courte que les occurrences du mot sont fréquentes dans le message ;
  • Constituer séquentiellement le fichier compressé en substituant au codage initial de chaque mot la nouvelle séquence numérique qui lui est attribuée.
  • La décompression du message est le processus inversé d’application du dictionnaire.
• Il existe plusieurs variantes et enrichissements de cet algorithme. Citons particulièrement la technique algorithmique couplée au système Huffman qui a été inventé par Abraham Lempel et Jakob Ziv en 1977. C’est celle mise en œuvre par les compressions ZIP bien connues.
• L’algorithme RLE (pour « Run length encoding », ou codage par plage) recherche les répétitions d’une même valeur numérique pour les factoriser.
  Pour exemple, ce logo monochrome du Havre tient sur une grille de 50 pixels sur 32, soit 1600 bits ou 200 Octets :

• À partir de la première cellule (ligne 1, colonne 1) jusqu’à la dernière (ligne 50, colonne 32), on compte les séquences de Bits vides (à valeur 0) et de bits colorés (à valeur 1) qui se succèdent.
• Ainsi de L1C1 à L5C4, on compte 132 cellules à la suite ayant pour valeur 0. On stocke ce constat sur un octet 132.0 (en binaire 1000100 0) ; de L5C5à L5C10, 6 cellules ont la valeur 1 (0000110 1) ; de L4C11 à L6c4, 26 cellules ont la valeur 0 (0011010 0) et ainsi de suite.
• Il faut 145 Octets au total pour décrire ces séquences. Le taux de compression du résultat est de 72,5 % (145/200).

Notes et commentaires

• Le taux de compression, souvent exprimé sous la forme d’un pourcentage, indique le rapport entre le nombre de Bits du transcodage compressé et le nombre de bits pour contenir le codage original.
  Attention : ce taux n’indique rien quant aux pertes de données potentielles liées à l’algorithme de compression.
• Le besoin de compresser les fichiers attachés à un courriel n’est pas seulement une réponse à l’exigence de limiter la durée de leur transmission. La taille des attachements est également contrainte par:
  • la capacité de stockage de la boite aux lettres destinataire ;
  • la volonté initiale des concepteurs de l’Internet de ne pas détourner la messagerie électronique de son usage initial, les échanges pair-à-pair offrant la réponse adéquate pour les volumes de données importants.
• Dans ce même glossaire, l’article Image Numérique qui compare les images matricielles et les images vectorielles complète utilement l’exemple basique de compression RLE d’une image numérisée proposé ci-dessus.