Bien des gens ne comprennent rien à la compression de données -- comment peut-on rendre quelque chose plus petit ? D'une certaine façon, on ne peut pas -- tout ce qu'on peut faire c'est d'encoder les données de manière plus efficace. Cet article explique quelques fondements et concepts entourant l'emmagasinage et la compression de données. Ces concepts sont beaucoup plus simples que ce que les gens ont tendance à imaginer -- seuls les détails d'implémentation sont complexes.
Fondamentalement, la compression de données sur ordinateur repose sur la recherche de ressemblances (dans la forme ou dans le motif), afin d'enregistrer la description de la forme ou du motif (en utilisant des tables ou des algorithmes mathématiques) plutôt que d'enregistrer l'image complète. Si vous n'y comprenez rien, poursuivez la lecture de cet article, vous y verrez plus claire.
La compression de formes est habituellement utilisée pour les images (mais peut s'appliquer au son, ondes, etc.). Les données sont rarement aléatoires : on peut trouver un motif si on cherche bien. Plutôt que d'enregistrer une image, on y cherche des ressemblances, et on crée une table de ces éléments communs. On n'a besoin ensuite que d'enregistrer les références (index dans la table) de ces éléments communs afin que l'image puisse être recréée à partir de celles-ci.
Le texte est un bon exemple pour expliquer la compression de forme. Examinons le bitmap (motif binaire) d'une police. Le «A» est représenté par un bitmap (image) constitué d'une matrice de 8 x 8 points. Un octet renferme 8 bits (chacun représentant un de ces points), on a donc besoin de 8 caractères (octets) pour représenter un «A». (Notre exemple montre également un «B» et un «C»).
Supposons que nous désirons enregistrer quelques pages de texte, si on décidait d'enregistrer l'image (bitmap) de ces caractères, ce serait très inefficace. Une page de texte est constitué d'environ 2000 caractères, chacun étant composé de 8 x 8 pixels (x le nombre de couleur) et ainsi de suite (2). Ainsi on aurait besoin de 2000 caractères x 8 octets x le nombre de pages (disons 3 pages) -- c'est à dire 48K (kilo-octets) pour enregistrer quelques pages de texte sous forme d'images -- et c'est sans compter les espaces blancs et le reste.
(2) Une police de 8 x 8 pixels x 1 couleur serait monotone. Une police plus grande et plus agréable utiliserait une matrice d'environ 14 x 9 -- ou presque 2 fois plus grande (en espace d'emmagasinage). Les informations de couleur requièrent encore plus d'espace d'emmagasinage également.
Plutôt que d'enregistrer une page sous forme d'image (ou de plusieurs images), pourquoi ne pas rechercher des ressemblances dans les formes ? On sait qu'un «A» dans une page ressemble à tous les autres «A» de la même page, alors pour chaque caractère on en crée une image et on l'ajoute à une table (en assignant à chaque caractère une valeur unique). Ainsi plutôt que d'enregistrer la page sous forme d'image, on enregistre la position que les caractères occupent dans notre table (appelée table de recherche, car c'est à cet endroit qu'on cherche). Lorsqu'on veut afficher la page, on recherche l'image de chaque caractère dans la table en utilisant sa valeur unique (index).
Un octet peut encoder 256 caractères différents (plus qu'il n'en faut), alors pour chaque octet de données, on peut enregistrer un caractère différent -- plutôt que d'enregistrer tous les graphiques de chaque caractère. C'est au moins 8 fois plus efficace pour les petites polices (compression 8:1) et des douzaines ou des centaines de fois plus efficace pour les grosses polices (3).
(3) Vous venez tout juste d'apprendre la manière dont le texte est enregistré dans les ordinateurs. La plupart des ordinateurs utilisent une table de recherche standard pour les caractères, appelée ASCII. Un format international existe (appelé Unicode) permettant aux ordinateurs d'encoder n'importe quel caractère existant dans le monde (incluant les milliers de caractères chinois et japonais).
C'est une méthode efficace de compression de forme. Puisque nos caractères sont standardisés, c'est facile à faire. On a qu'à rechercher les formes similaires (chaque lettre) et trouver une manière de décrire ces formes (en utilisant une table), puis il suffit de se rappeler d'un index dans la table (plutôt que se rappeler la forme elle-même). Cette technique de compression est formidable en autant que la forme à encoder est standard. C'est plus compliquer ou impossible si la forme n'est pas standard.
On décrit souvent les images par le terme «données brutes», les images peuvent occuper beaucoup d'espace. On les appelle également Pict, Icônes, bitmap, pixmap et ainsi de suite. Examinons l'image suivante de plus près :
Note: J'ai agrandi l'image pour qu'on puisse voir les données, la taille réelle de l'image est montrée à droite.
Cette image possède 16 pixels (points) de large par 16 pixels de haut, c'est à peu près la même dimension que le pointeur de souris ou d'un petit icône. Supposons qu'on peut afficher chaque pixel parmi 256 couleurs différentes -- chaque octet peut représenter une couleur parmi 256. Alors pour encoder cette image on aura besoin d'un octet (la couleur) x 16 pixels (hauteur) x 16 pixels (largeur), soit 256 octets au total pour encoder cette petite image.
Pourquoi ne pas encoder les données en utilisant les formes ? On pourrait conserver un jeu de tables qui donnerait de l'information sur chacune des formes :
Ce qui nous donne un total de 20 bits (2 octets et demi) pour chaque forme.
En utilisant notre table de formes on pourrait dessiner la même image en utilisant 3 formes.
On n'a besoin que de 60 bits, moins de 8 octets, pour encoder la même image en utilisant des techniques de dessin (encodage des formes) -- comparativement à 256 octets pour encoder les données brutes. Ainsi l'affichage (dans le cas présent) est 32 fois plus efficace (compression 32:1); et ce n'est que le début.
Supposons que l'image est 16 fois plus grande (256 x 256 pixels), on aurait besoin de 64K (kilo-octets) pour encoder les données brutes, alors qu'on aurait besoin d'environ 14 octets pour l'encoder en utilisant les formes -- une compression de 4000:1. Vous voyez maintenant que la technique du dessin est beaucoup plus efficace pour encoder les données comparativement à l'encodage des données brutes. Bien sûr le compromis c'est d'avoir suffisamment de formes afin d'être en mesure d'afficher une grande variété d'images (4).
(4) Les logiciels de dessin modernes peuvent manipuler des crayons de largeurs diverses, plusieurs couleurs, motifs, courbes et formes complexes. Vous pouvez ainsi remarquer qu'il est possible de faire beaucoup en décrivant les données avec des formes (dessins).
Illustrator, MacDraw, les logiciels CAD et les autres programmes d'illustration encodent les données en utilisant des formes.
Photoshop, MacPaint et les autres logiciels de traitement d'images enregistrent leurs données sous forme d'images binaires -- ce qui demande beaucoup plus d'espace d'emmagasinage.
C'est donc beaucoup plus efficace d'encoder les données en utilisant des formes plutôt que des images (données brutes). Mais cela ne fonctionne bien que si vous êtes en mesure de décortiquer un problème (image) en des formes très distinctes. Beaucoup d'images ne peuvent pas être décrites facilement en utilisant des formes simples. Ainsi les programmes d'illustration encodent les données très efficacement, mais ces données doivent être créées à l'intérieur du programme même. Bien sûr, d'autres types de compression de données existent pour les images.
Lorsqu'il est impossible de compresser les données à partir de ses parties ou éléments communs, il faut rechercher des motifs. Ce n'est pas habituellement aussi efficace que la compression de forme, cependant certaines images ont tellement de détails, que c'est la seule solution pour les compresser.
Voyons d'abord la base de la compression de motifs.
Encodons l'échantillon suivant :
Supposons que cette image possède une taille de 20 caractères (avec des lettres uniquement dans les premières positions). Sous forme de texte, on aurait besoin que de 3 caractères (octets) pour l'encodage (un octet pour chacune de lettres F-A-X) -- mais ça ne fonctionne que si on connaît a priori la police utilisée. Si on ne connaît pas la police utilisée, alors on doit encoder le tout en image. L'encodage des données brutes demanderait 240 octets (1 bit pour chaque pixel), ce n'est pas très efficace. Si on ne peut pas encoder en utilisant la ressemblance des formes, pourquoi ne pas encoder en utilisant la ressemblance dans les motifs de données ?
Si on cherche des ressemblances de motifs, on remarque qu'il y a beaucoup de blanc. Balayons cette image pixel par pixel, tout comme si on lisait une page de texte (en commençant dans le coin supérieur gauche et en lisant chaque ligne horizontalement). On remarque qu'il y a de longues suites de blancs (avant d'atteindre un pixel noir), utilisons cette caractéristique.
Plutôt que d'encoder l'image en données brutes, nous allons emprunter le bit le plus significatif d'un octet, afin de l'utiliser pour définir si les 7 bits suivants sont des données brutes ou une «suite» de blancs (le nombre de bits blanc, jusqu'à une possibilité de 127+7 bits blancs (134 au total).
L'encodage de l'image sous forme de données brutes donnerait «000000000000000000...001» en binaire. Cependant notre technique de compression nous permet de dire «il y a 127 zéros (0), puis un 1». C'est une façon beaucoup plus efficace d'encoder les données.
Au début de notre «suite» on note que la première ligne est blanche, alors on encode un octet avec son bit le plus significatif à 0, ce qui nous permet d'indiquer qu'on a une suite de 134 pixels blancs. On a besoin d'un octet supplémentaire pour encoder la suite des 27 pixels blancs restants (afin d'atteindre le prochain pixel noir). Les trois prochains octets sont encodés avec les données de l'image, l'encodage devient un peu moins efficace car nous n'avons que 7 bits par octet pour emmagasiner les données brutes (puisque nous utilisons le bit le plus significatif pour indiquer s'il s'agit d'une suite de blancs). Donc, l'encodage des données brutes de l'image est 13% moins efficace pour ces octets, c'est un compromis acceptable puisqu'on gagne beaucoup en efficacité lors de l'encodage des suites de blancs. En utilisant notre méthode d'encodage, nous n'avons eu besoin que de deux octets, alors que 20 octets auraient été nécessaires pour encoder les données brutes -- nous avons donc été 10 fois plus efficace. Plus longues sont les suites de blancs et meilleure sera l'efficacité de notre méthode d'encodage (compression).
Cette technique est appelée «Run Length Encoding» ou RLE, elle recherche les suites ayant un même motif. On pourrait pousser un peu plus loin et se demander comment encoder des suites composées d'autres types de motifs (telles que des bits alternant entre noir et blanc, et ainsi de suite), vous avez saisi.
En passant, c'est à peu de chose près la technique utilisée par les télécopieurs.
Bien sûr, la technique RLE peut être utilisée pour compresser le texte, à condition que le texte à encoder comporte de longues suites d'un même caractère. Sinon, il n'y a pas vraiment de gain en efficacité.
Il y a d'autres façons de compresser le texte.
Le type le plus populaire de compression de texte est l'encodage Huffman. En gros, cette technique cherche les caractères les plus utilisés et les encode en utilisant le moins de bits possible. Le compromis est que les caractères rarement utilisés nécessiteront plus de bits pour l'encodage. Cependant, si vous pouvez prédire assez bien la fréquence d'utilisation des caractères, vous pourrez obtenir une bonne efficacité de compression (2:1). Appliquée à d'énorme quantité de texte, cela peut représenter beaucoup d'espace d'emmagasinage préservé.
Cette technique d'encodage à taille variable construit un arbre à plusieurs branches, le bout de chaque branche contient une lettre, plus la branche est courte, plus l'encodage sera petit. Voici un exemple d'arbre pour l'alphabet :
Ainsi un «e» ou un «t» (des lettres fréquemment utilisées) ne nécessitent que trois bits d'encodage. Le niveau suivant nécessite 4 ou 5 bits, un bit s'ajoute à chaque niveau, jusqu'à la lettre «z» ou «q» qui nécessitent 10 bits d'encodage.
Ce concept (fréquent = plus petit; complexe = plus gros) remonte loin dans l'histoire, tellement loin que je n'essaierai même pas de deviner d'où il vient. Mais quelques milliers d'années auparavant, l'écriture chinoise utilisaient certains éléments de ce concept. La majorité des caractères les plus utilisés sont simples à écrire (quelques traits). Ils se sont simplifiés car les gens se lassaient d'écrire des caractères complexes presque tout le temps, alors ils ont «compressé» l'écriture des traits. Une autre application de ce concept se retrouve dans le code morse. La lettre la plus fréquemment utilisée en anglais est le «e», alors en morse elle est la plus facile à envoyer (un «bip» court); la lettre «q» est la plus longue à envoyer (deux «bip« longs, un «bip» court, un «bip» long).
Si vous pouvez encoder les caractères les plus fréquemment utilisés avec un encodage à taille variable, alors pour un texte donné, nous devrions être capables d'encoder selon les mots les plus utilisés également. On doit simplement construire des tables renfermant des centaines de mots courants et utiliser les index de ces tables pour la compression. Ces index sont habituellement construits dynamiquement, en examinant les données et en construisant une table basée sur CE texte. Évidemment, moins il y a de répétitions de mots dans le texte, moins efficace sera la compression.
Plusieurs variantes de l'algorithme L/Z ont été brevetées, et elles exigent des royautés pour être utilisées. C'est ce qui a causé tant de remous autour du format de fichier GIF (Graphics Interchange Format) de Compuserve quelques années auparavant. Les programmeurs n'étaient pas enchantés d'apprendre qu'ils devaient payer des royautés.
Même si les techniques Huffman et L/Z sont habituellement utilisées pour compresser du texte, le même concept peut être appliqué à d'autres structures telles que les graphiques, le son ou les structures composites.
On a vu qu'il existe plusieurs techniques de compression de données. Parmi celles qui n'ont pas été mentionnées concernant les graphiques, notons : GIF, JPEG (Joint Picture Expert Group), MPEG (Motion Picture Expert Group), les compressions basées sur le Fractal (utilisant des algorithmes répétitifs complexes) et plusieurs autres encore. Pour le son : AIFF, WAV; le QuickTime d'Apple supporte plusieurs formats de fichiers et de types de compression.
Rappelez-vous, toutes les techniques de compression de données font fondamentalement la même chose -- elles recherchent des ressemblances dans les données et les encodent plus efficacement parce que ces ressemblances ne sont enregistrées qu'une seule fois.