Après avoir passé une partie de ma journée (celle d’hier, l’écriture c’est toujours long) à optimiser les images de mon site, je me suis dit que ça serait pas une bêtise que d’expliquer un peu ce qu’est la compression de données et comment cela fonctionne.

# Définition

La compression de données ou codage de source est l’opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations, ou des informations voisines, en utilisant un algorithme de décompression. C’est une opération de codage qui raccourcit la taille (de transmission, de stockage) des données au prix d’un travail de compression. Celle-ci est l’opération inverse de la décompression.

L’objectif est donc ici de diminuer le volume de données. Malheureusement, rien n’est jamais gratuit et il faudra compenser en dépensant des ressources de calcul pour créer le document compressé et pour pouvoir reconstituer les données de départ. Bien évidemment, c’est une tâche dans laquelle les ordinateurs excellent, ce n’est donc en général pas un problème, mais on verra par la suite qu’il est possible que cela empêche l’utilisation de la ressource. Il est également envisageable de se séparer d’une partie des données, ce qui, selon les cas, n’est pas vraiment un problème.

# Avec ou sans perte

# Compression sans perte

On a de la peine à faire de la compression de masse (ou de poids d’ailleurs) dans la vie physique, en revanche on sait très bien faire de la compression de volume. Un très bon exemple est lorsque vous rangez votre sac de couchage dans son sac de compression. L’objectif désiré est de récupérer le même sac de couchage en arrivant sur notre lieu de camping le soir, la seule chose qu’on a fait c’est d’enlever au maximum l’air qui était coincé entre les fibres du sac de couchage, et il y en a beaucoup, c’est pour cela qu’il vous tiendra au chaud toute la nuit.
Le voyage dans le sac à dos ne lui a donc rien fait perdre, on s’est juste arrangé pour qu’il prenne le moins de place possible.

# Dans le numérique

Avec les documents numériques, la compression sans perte est extrêmement utilisée pour le texte, mais il existe également des algorithmes qui permettent de réduire la taille d’une image, d’un fichier audio et donc forcément d’une vidéo, cette dernière étant constituée d’une suite d’image et d’une ou plusieurs pistes audio.

Il n’existe aucun algorithme pouvant compresser tous les types de fichier, il est donc nécessaire de choisir le bon algorithme sous peine de se retrouver avec un fichier plus gros à l’arrivée.

# Compression avec perte

La compression avec perte est, en général, plus dérangeante. Si vous décidez de prendre votre livre de chevet en vacances, disons Le capital au XXI^e siècle, de Thomas Piketty, vous êtes bien ennuyé·e de devoir transporter ses presque mille pages. Alors vous pouvez essayer de faire de la compression sans perte et d’enlever tout l’air qui traine entre les pages, malheureusement à priori vous n’allez pas gagner grand-chose… Il ne vous reste qu’une solution, vous séparer d’une partie du livre. Vous pouvez vous séparer d’une page sur deux, de la première ou deuxième moitié du livre, de la moitié du livre, coupé en largeur ou en hauteur, voir même vous pouvez supprimer une lettre sur deux.

Les différentes solutions proposées ici sont plus ou moins handicapantes (perdre la deuxième moitié de ce livre, si vous ne l’avez pas encore commencé, n’est pas forcément un problème sauf si vous avez deux mois de vacances), mais toutes les options vont, à un moment, vous empêcher de lire le livre. C’est une compression avec perte, ou destructrice.

# Dans le numérique

La compression destructrice est utilisée quasiment exclusivement pour les données “perceptibles”, à savoir qui seront interprétées par nos sens, majoritairement les données visuelles et auditives.

On part du principe que si la perte d’information n’est pas handicapante pour son appréciation, alors c’est un bon algorithme. Un très bon exemple est d’enlever tous les sons que l’humain n’entend pas sur un fichier audio. Bien que le son d’un saxophone, par exemple, ne sera pas le même avant et après la compression, un humain ne devrait pas pouvoir faire la différence. C’est donc souvent une bonne solution.

# En informatique

J’avais déjà effleuré le sujet dans mon article sur la numération en informatique, en particulier pendant la partie sur la numération binaire. Ce qu’il faut retenir c’est qu’en informatique, tout n’est qu’une suite de 0 et de 1. On décide ensuite d’une manière d’écrire des caractères plus complexes.

# ASCII

Par exemple, une des normes de codage des caractères est la norme ASCII, ou code américain normalisé pour l’échange d’information. C’est l’une des normes les plus influentes, bien que presque plus utilisée de nos jours à cause de sa limitation.

Elle définit une liste de cent-vingt-huit codes, écrit donc sur sept bits¹. Mise à part les trente-deux premiers symboles et le dernier qui ne sont pas imprimables, les symboles de l’ASCII sont les suivants :

 !"#$%&'()*+,-./
0123456789:;<=>?
@ABCDEFGHIJKLMNO
PQRSTUVWXYZ[\]^_
`abcdefghijklmno
pqrstuvwxyz{|}~

Le caractère 0 est par exemple encodé 0110000, donc 48 en base dix, t est encodé 1110100, soit le 116^e, u le 1110101 et donc le 117^e. Évidemment, les caractères qui se suivent dans l’alphabet ou les chiffres se suivent également dans leur notation binaire ou décimale.

Si je veux écrire Bonjour, je m'appelle Greg. en ASCII, je vais me retrouver avec la suite de bits suivante :

1000010 1101111 1101110 1101010 1101111 1110101 1110010 0101100 0100000 1101010 1100101 0100000 1101101 0100111 1100001 1110000 1110000 1100101 1101100 1101100 1100101 0100000 1000111 1110010 1100101 1100111 0101110

Les espaces n’existent pas, c’est uniquement pour plus facilement pouvoir identifier chacun des caractères.

Bref, cet encodage est bien joli, mais maintenant comment est-ce qu’on peut compresser cette donnée? Eh bien on ne peut pas, enfin, pas si on veut garder un encodage ASCII, mais il est bon de se rappeler que quel que soit l’encodage choisit, le document se présente sous la forme d’une suite de bits, et cela que la source soit du texte, une image, un film ou n’importe quelle autre format.

# Le texte

Un algorithme d’encodage fréquemment utilisé est le codage de Huffman. Il consiste à ranger les caractères dans un arbre en fonction de leurs nombres d’occurrences. Pour la démarche détaillée, vous pouvez vous référer à la page Wikipédia sur le codage de Huffman. Pour la même phrase qu’avant, Bonjour, je m'appelle Greg., nous obtenons donc l’arbre suivant.

Il nous faut maintenant noter le poids de chaque branche en partant de la racine, le nœud tout à gauche, jusqu’à la feuille correspondant à la lettre que nous cherchons.
On y voit que la lettre qui apparaît le plus, le e, est encodée par les bits 011 alors qu’un caractère apparaissant qu’une fois, le u par exemple, est encodé 11100, soit sur plus de bits.

Le résultat de cet encodage est le suivant:

11010 1000 11011 1001 1000 11100 1010 11101 010 1001 011 010 11110 11111 0000 1011 1011 011 1100 1100 011 010 0001 1010 011 0010 0011

Nous avons maintenant 107 bits, contre 189 avant, soit une diminution de presque 45 %. Évidemment, il faudrait également encoder en plus l’arbre de Huffman, mais il est aisé de comprendre qu’étant donné que l’arbre a un volume de données presque constant (il augmente en taille uniquement si on rajoute des caractères), son poids devient négligeable avec un grand texte à encoder.
Et pour les malins qui voient déjà arriver un problème lors du décodage, non nous n’avons pas besoin de garder les espaces entre chaque lettre comme je l’ai fait dans mon code, c’était une fois de plus pour la lisibilité. Il n’est pas possible de se tromper, en partant de la racine, lorsqu’on arrive sur une feuille il suffit de recommencer à la racine et de noter la valeur de la feuille. Essayez et vous verrez.

Ce n’est pas l’unique méthode et ce n’est pas la meilleure, il y en a plein de plus compliquées, mais vous avez compris le principe, du moins je l’espère.

En général, on ne prendra jamais une compression destructrice pour du texte, le but primaire étant de pouvoir revenir au format de départ.

# Les images

En informatique, une des grosses sources de volume de données est les images. Il y a donc rapidement eu besoin d’algorithmes de compression pour éviter de stocker trop d’informations.

# Comment sont enregistrées les données?

Premièrement, qu’est-ce qu’une image? La manière la plus simple de se la représenter est une matrice à deux dimensions, chaque case contenant un pixel, ce dernier définit par sa couleur. On doit donc définir comment représenter une couleur, c’est ce qu’on appelle l’espace colorimétrique. Je vais résumer un peu les choses ici, mais des précisions sont disponibles sur l’article Wikipédia

# RGB ou RVB

On entend souvent parler de RGB ou de sa version francophone RVB . Cet espace de couleur définit trois composantes à notre couleur, une rouge, une verte et une bleue. Pour avoir du noir, on met tous les curseurs à zéro et pour avoir du blanc, on met tout au maximum. On parle ici de synthèse additive, on peut le représenter par la superposition de cercles de couleur.

C’est un espace qui décrit bien le fonctionnement de la lumière, mais qui ne fonctionne pas du tout avec l’impression. Si vous avez déjà joué avec de la peinture, vous savez bien que mélanger du vert et du rouge ne donne pas du jaune, et mélanger un peu tout ensemble peinera à donner du blanc.

# CMYK ou CMJN

Ici, nous sommes à l’inverse du RGB, à savoir en synthèse soustractive, composé, comme son nom l’indique CMYK , des couleurs cyan, magenta, jaune et de la “couleur” key, qui est en fait du noir. Cette quatrième couleur n’est pas nécessaire dans le fonctionnement de la synthèse soustractive, c’est l’imprimerie qui a poussé à la rajouter. La superposition des trois couleurs primaires pour faire du noir pose un premier problème, la consommation d’encre. On comprend facilement que s’il suffit de mettre une unique encre noir aux emplacements noirs, plutôt que de mettre de toutes les autres couleurs, on économise beaucoup d’encre. Le second problème est la manière dont l’encre est absorbée par le papier, plus d’encre veut dire plus temps de séchage et potentiellement des problèmes de surcharge.

# L’écriture des couleurs

Quoi qu’il en soit, c’était une petite digression. Si on utilise le RGB, on sait maintenant qu’il faut représenter les valeurs des couleurs rouge, verte et bleue. On peut choisir d’exprimer ces valeurs sur une échelle à un certain nombre de “marches”, par exemple 256, ce qui nous permet de les représenter sur 8 bits donc d’avoir au total 24 bits pour chaque pixel. Il est courant de rajouter un canal supplémentaire pour gérer la transparence, ce qui fait passer le pixel à 32 bits, on appelle ce codage RGBA, pour alpha, le canal alpha étant celui qui détermine l’opacité.

Comme exemple, la couleur de fond de cette page est un gris assez foncé, encodé en RVB est 1C1C1C. C’est de l’hexadécimal, mais vu que vous avez lu mon article sur la numération vous savez donc le convertir en :

• binaire → 001110 001110 001110 ;
• décimal → 28 28 28.

Codé en CMYK, j’obtiens 0 0 0 89, donc aucune couleur et du gris très foncé, sachant que l’échelle va jusqu’à 100 cette fois.

Une autre couleur, un vert-gris que j’utilise pour mettre un peu de couleur, même si c’est rarement le cas. En RVB, 799479, ce qui donne 121 148 121 en décimal. On y voit clairement la composante verte plus élevée que les autres. En CMYK cela donne 18 0 18 42, du cyan et du jaune, pas de magenta et du gris.

# La compression PNG

La compression PNG est un format ouvert et ayant pour but de remplacer le format GIF qui était à l’époque propriétaire. Son algorithme passe par trois étapes :

1. Pré-filtrage
2. Encodage basé sur un dictionnaire
3. Codage de Huffman

Je vais simplifier et traduire une partie de ce que Christophe Erdmann a écrit dans son super article sur le PNG. Je ne peux que vous conseiller sa lecture si vous comprenez l’anglais.

# Pré-filtrage

Le pré-filtrage consiste à remplacer les valeurs absolues de chaque pixel par des valeurs relatives au pixel précédent. Par exemple, si j’ai deux couleurs identiques qui se suivent, la première sera complètement encodée et la seconde sera mise à zéro puisqu’il n’y a aucune différence entre les deux. En général, un pixel n’est pas isolé, surtout sur des dessins ou graphiques. Ce n’est en général pas le cas pour des photos, c’est pourquoi ce format n’est pas recommandé dans ce cas. Cette étape va rendre la compression bien meilleure.

# Encodage basé sur un dictionnaire

L’encodage basé sur un dictionnaire permet d’éviter des répétitions. Si plusieurs éléments sont identiques dans l’image, alors on peut simplement pointer sur la première occurrence et ne pas enregistrer de données supplémentaires.

# Codage de Huffman

Cette dernière étape, nous la connaissons. C’est la même opération qu’avec le texte, le but étant de diminuer la longueur des données souvent enregistrées. Une fois de plus, avec un dessin numérique, il y a plein de répétitions de couleurs et donc un énorme gain potentiel.

# Petite comparaison

Si on part d’une image de 1920 x 1080, la résolution HD standard de nos écrans actuels. Enregistrés dans un format RGB, chaque pixel nécessite donc 24 bits, ou 3 octets. Au total, notre image pèse donc 1920 x 1080 x 3 donc 5 875 200 octets ou 5.9Mo (ou 5.6Mio, mais je ne vais pas m’éterniser sur le sujet maintenant). Faisons donc un test, avec la capture suivante de mon navigateur sur mon site. J’ai réduit la taille de l’image pour l’affichage sur le site mais l’image avec laquelle j’ai fais les calculs ne l’était pas.

Mon image fait 81 492 octets, soit 1.39 % du poids de sa version non compressée. Et tout ça sans aucune perte d’information. Alors il y a un gros aplat gris qui facilite la compression, mais vous voyez ici la puissance de la compression non-destructrice dans certains cas.

# JPEG

Le format JPEG , utilisé dans les images .jpg et .jpeg, est un format de compression destructrice.

En gros, l’image est passée dans un autre espace de couleur, défini par les trois composantes suivantes :

• Y, la valeur en niveau de gris de l’image ;
• Cb, la valeur jaune-bleue de l’image ;
• Cr, la valeur verte-rouge de l’image.

L’image est ensuite découpée en petits blocs carrés, par exemple des blocs de huit pixels de côté, soit soixante-quatre pixels par bloc. Chaque bloc est transformé en une somme d’ondes, ce qui est bien trop complexe pour ce billet, mais qui permet de supprimer une grande partie de l’information sans que cela ait un impact visuel facilement discernable. Le paramètre de qualité que vous voyez lorsque vous enregistrez une image au format JPEG définit quelle proportion de ces coefficients d’onde vont être conservés, à 100% on garde tout et à 0% on garde (presque) rien.

Évidemment il est possible de faire cette étape différemment sur chacune des nouvelles composantes de couleur. L’œil humain est moins sensible aux détails dans les espaces Cb et Cr, c’est donc ici que l’algorithme va beaucoup couper.

Pour celles et ceux qui voudraient creuser le sujet car ce billet commence à devenir beaucoup trop long, vous pouvez lire une partie du livre Data Compression Explained de Matt Mahoney, malheureusement en anglais, en particulier sa partie sur la compression destructrice.

Bref, au final, selon l’exemple de Matt Mahoney, une photo non compressée de 786 Ko va pouvoir être réduite à 23 Ko avec une compression qui, bien que destructrice, sera peu visible à l’œil. Sachant que cette même photo compressée en PNG fait 476 Ko, on voit l’intérêt d’une compression destructrice. Bien évidemment, vu qu’il y a de la perte d’information, il n’est pas possible de revenir à la photo de base. Une fois la compression effectuée, on ne peut plus reconstruire les données manquantes.

# Précision historique

Comme me l’a gentiment fait savoir hyakosm, sur le journal du hacker, une des raisons qui a poussé à changer d’espace colorimétrique, et donc de ne pas rester en RVB, est l’arrivée de la télévision couleur. En effet, pour des questions de rétro-comptabilité, il n’était pas possible d’envoyer des signaux de couleur, rouge, vert et bleu, aux téléviseurs destinés a recevoir uniquement un signal noir-et-blanc. En passant sur un espace colorimétrique qui contient la luminance sur un canal dédié, le Y, les anciens téléviseurs peuvent simplement ne pas s’occuper des composantes de couleur et donc continuer à fonctionner malgré le changement de norme.

Une superbe archive de l’INA explique ce fonctionnement bien mieux que je ne pourrais le faire ici. Je vous conseille donc d’aller la visionner.

# Les autres formats

# Le son

Au même titre que ce que nous voyons, un son est, du moins à notre échelle, une information continue. Pour reprendre l’exemple d’une photo, si vous avec un appareil photo 2 Mpx (mégapixels), il va supprimer une grande partie de l’information au moment même du déclenchement. Vous pouvez vous en rendre compte en prenant la même photo avec un appareil qui aurait un capteur à 30 Mpx. Il sera possible de plus zoomer dans cette seconde image.

Dans tous les cas, nous devons transformer l’information continue en information discrète. Lorsque j’ai décidé d’utiliser 256 valeurs pour chaque couleur, j’aurais pu prendre plus ou moins de valeurs, ce qui aurait eu un impact sur la précision de mon image. C’est identique avec le son, il faut définir la fréquence d’échantillonnage, la fréquence à laquelle nous enregistrons le son. Pour une transmission de la parole, par exemple au téléphone, échantillonner à 7 kHz, (7 000 fois par seconde), est suffisant. Pour de la musique, on utilise en général une fréquence supérieure à 40 kHz, 44,1 kHz pour le format CD et 48 kHz pour le format DVD et télévision numérique. Il est même courant d’enregistrer bien plus haut et de réduire une fois le support final décidé. Rien qu’ici, on parle déjà d’un facteur 7 entre le poids d’un son enregistré pour transmettre de la parole et celui d’un morceau de musique.

Il y a plein de formats, pour donner un simple exemple tiré d’un article de W. A. Production, le même fichier audio encodé différemment donne :

• WAV, format non compressé, 44.1 kHz, encodé sur 16 bits → 50 Mo ;
• FLAC, format compressé sans perte, 44.1 kHz, encodé sur 24 bits (donc plus que le WAV, de meilleure qualité à priori) → 28 Mo ;
• MP3, format compressé avec perte, 44.1 kHz, 320 kbps² (la qualité recommandée pour les MP3 qui ne doit pas faire trop de perte audible) → 11 Mo ;
• MP3, format compressé avec perte, 44.1 kHz, 128 kbps (mauvaise qualité mais meilleure compression) → 4,5 Mo.

# La vidéo

Si on sait compresser du son et de l’image, on peut aisément comprendre qu’il est possible de compresser de la vidéo. Les algorithmes de compression sont en constante évolution. AVI, h264, VP9, x265, AV1, comment s’y retrouver… Ce qu’il faut retenir c’est qu’ici, la compression bien qu’exceptionnelle, occasionne souvent des problèmes sur le périphérique de lecture si ce dernier est trop ancien. Le gain d’espace se fait au détriment d’un besoin supplémentaire en calcul pour recomposer la donnée de départ, donc si le processeur n’arrive pas à faire les calculs suffisamment rapidement, la vidéo ne peut pas être lue.

Un même film peut faire 30-40 Go sur un disque Blu-ray et donner un fichier encodé avec des codecs actuels de moins de 2 Go, sans une énorme perte de qualité.

# Mon expérience

Du coup, qu’est-ce que ça a donné sur mon site? J’avais des images au format JPEG que j’ai transformées en WebP, bien plus récent et souvent beaucoup plus performant. J’ai également transformé une animation au format GIF en WebP animé. J’ai également beaucoup d’images au format SVG, qui est donc vectoriel, ce qui veut dire que pour afficher un cercle il faut dire qu’on veut un cercle, donner son centre et son rayon, éventuellement sa couleur. Ça donne un fichier texte et non pas un fichier image. Ce texte est interprété par le navigateur et affiche ce qui est désiré. Le schéma de synthèse additive est un exemple de fichier SVG.

<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 420 400">
  <rect width="100%" height="100%"/>
  <path fill="#0f0" d="M340 144a130 130 0 1 0-260 0"/>
  <path fill="#00f" d="M80 144a130 130 0 1 0 130 225.2"/>
  <path fill="red" d="M210 369.2A130 130 0 1 0 340 144"/>
  <path fill="#0ff" d="M210 144a130 130 0 0 0-130 0 130 130 0 0 0 65 112.6"/>
  <path fill="#f0f" d="M145 256.6a130 130 0 0 0 65 112.6 130 130 0 0 0 65-112.6"/>
  <path fill="#ff0" d="M275 256.6A130 130 0 0 0 340 144a130 130 0 0 0-130 0"/>
  <path fill="#fff" d="M210 144a130 130 0 0 0-65 112.6 130 130 0 0 0 130 0A130 130 0 0 0 210 144"/>
</svg>

Étant uniquement du texte, c’est extrêmement facilement compressible, le fichier SVG fait 618 octets (oui, c’est déjà pas bien gros), le fichier compressé fait 249 octets.

Au final, les fichiers dont je me sers pour générer mon site faisaient 11.8 Mo hier matin, ils font désormais 3.4 Mo soit une diminution de 71 %. Sans compter le gros fichier animé, je suis passé de 3.71 Mo à 2.27 Mo soit un gain de 39 %.

En plus de ma compression active, comme m’arranger pour donner des images au bon format, tous mes documents textuels sont compressés une fois envoyés sur mon serveur. Si votre navigateur est d’accord, c’est en général le cas, je lui envoie la version compressée du document, ce qui fait gagner beaucoup de bande passante à mon serveur et à votre forfait internet. Avec tous les fichiers compressés, sauf mon avatar qui est au format WebP, ma page d’accueil passe de 30 258 o à 11 536 o, donc un gain de 62 %.

# Conclusion

C’était un peu un prétexte pour parler de compression, j’ai effleuré le sujet, mais j’espère que ça vous permettra de comprendre un peu mieux ce qui se passe sur vos ordinateurs.

Continuez à vous documenter sur le fonctionnement des ordinateurs (les téléphones sont des ordinateurs), c’est un outil qui a d’énormes implications politiques et plus le temps passe, plus nous devrons nous positionner sur sa régulation, pour le respect de notre vie privée et de notre sécurité.