Dans cette section, nous allons nous intéresser à la compression des données. La compression consiste à réduire la taille d'un message ou d'un fichier de manière à occuper moins d'espace de stockage ou à réduire le temps de transmission.

! Remarque

Lorsqu'on écrit des messages sur une messagerie instantanée telle que WhatsApp ou Telegram, il n'est pas rare d'utiliser un langage abrégé pour gagner du temps à l'écriture. On écrit par exemple slt au lieu de salut ou cc au lieu de coucou.

Ce qu'on appelle le langage SMS est une forme de compression des données par l'adoption d'un langage abrégé. À la base, cette technique était en partie motivée par les limites de caractères par SMS sur les téléphones portables.

Il existe deux grandes familles de techniques de compression :

• La compression avec pertes, qui consiste à supprimer de l'information du message original pour réduire sa taille. Cette technique est souvent utilisée pour compresser des images, des vidéos ou des fichiers audio. Un fichier ainsi compressé perd en qualité, mais le gain de place est souvent très important et la perte de qualité est souvent imperceptible.
• La compression sans pertes, une technique de compression générale qui permet de compresser n'importe quel type de fichier sans perte d'information. Quand on créé une archive ZIP, on utilise une technique de compression sans pertes pour réduire la taille des fichiers contenus dans l'archive.

Dans cette section, nous allons commencer par nous intéresser à la compression sans pertes et à l'algorithme de Huffman.

Compression sans pertes

Les techniques de compression sans pertes cherchent à réduire la taille d'un fichier sans perdre d'information. Nous allons maintenant voir une technique de compression sans pertes très utilisée : la compression par codage de Huffman. Dans cette section, nous l'étudierons dans le contexte de la compression de données textuelles.

L'algorithme de Huffman

Le codage de Huffman se base sur le fait que certains caractères sont plus généralement plus fréquents que d'autres dans un texte. Par exemple, dans un texte en français, la lettre e est généralement beaucoup plus fréquente que la lettre k. Or, avec un encodage traditionnel, tel que ASCII, on utilise généralement le même nombre de bits pour coder chaque caractère, qu'il soit fréquent ou non. Idéalement, il faudrait utiliser moins de bits pour coder les caractères les plus fréquents et plus de bits pour coder les caractères les moins fréquents.

Le codage de Huffman est une technique de compression qui se base sur la construction d'un code binaire à longueur variable. Dans ce code, les caractères les plus fréquents sont représentés par des mots de code courts tandis que les caractères les moins fréquents sont représentés par des mots de code plus longs.

Nous avons vu que certains codes à longueurs variables, comme le code Morse, peuvent être ambigus si on ne met pas de séparateur entre les mots. Pour garantir qu'une suite de mots de codes puisse être décodée sans ambiguïté et ce même en l'absence de séparateur entre les mots, le code construit par la technique de Huffman est un code préfixe.

Pour rappel, un code est un code préfixe si aucun mot de code n'est le préfixe d'un autre mot de code. En d'autres termes, aucun mot de code ne peut être obtenu en ajoutant des symboles à la fin d'un autre mot de code. Cette propriété garanti qu'une suite de mots de code peut être décodée sans ambiguïtés.

Construction d'un arbre de Huffman

Observons maintenant comment construire un code de Huffman. Le but est de trouver quel mot de code (suite de bits) attribuer à chaque caractère possible. La méthode est basée sur la construction d'un arbre binaire dont les feuilles sont les caractères à représenter. Les caractères les plus fréquents sont placés le plus près possible de la racine de l'arbre tandis que les caractères les moins fréquents sont placés le plus loin possible. Le chemin de la racine à une feuille donne le mot de code du caractère. Plus le chemin est long, plus le mot de code est long.

Pour construire cet arbre binaire, on procède de la manière suivante :

1. On crée un nœud pour chaque caractère à encoder. À chaque nœud, on attribue un poids proportionnel à la fréquence d'apparition du caractère.
2. On ordonne les nœuds par ordre croissant de poids dans une liste de nœuds à traiter.
3. On forme un nouvel arbre binaire en prenant les deux nœuds premiers nœuds de la liste (ceux de poids les plus faibles) et en les regroupant sous un nouveau nœud. Le poids de ce nouveau nœud est la somme des poids des deux nœuds regroupés.
4. On déplace ce nouveau nœud à sa place dans la liste ordonnée des nœuds à traiter en fonction de son poids.
5. On répète les étapes 3 et 4 jusqu'à ce que tous les nœuds soient regroupés dans un seul arbre.

Une fois l'arbre construit, on peut déterminer le mot de code associé à un caractère en parcourant l'arbre de la racine jusqu'à la feuille correspondante. À chaque étape, on ajoute un bit au mot de code :

• Si on descend à gauche, on ajoute un 0 à la fin du mot de code.
• Si on descend à droite, on ajoute un 1 à la fin du mot de code.

Encodage et décodage

Une fois un code de Huffman construit, on peut l'utiliser pour encoder un texte. Pour cela, on remplace chaque caractère du texte par son mot de code. Pour décoder un texte, on parcourt le texte de gauche à droite en suivant le chemin dans l'arbre de Huffman correspondant au mot de code.

À noter que pour décoder un message, il faut avoir accès au code de Huffman, sans quoi il est impossible de retrouver le message original. Généralement, ce code est donc envoyé en même temps que le message encodé. La taille occupée par la description du code est souvent négligeable par rapport à la taille du message encodé.

Compression avec pertes

Avant de conclure cette section, attardons-nous un instant sur les techniques de compression avec pertes. Contrairement aux techniques de compression sans pertes (dont fait partie l'algorithme de Huffman), les techniques de compression avec pertes ne permettent pas de retrouver exactement les données originales. Elles sont donc utilisées dans des domaines où une perte d'information est acceptable, comme par exemple pour la compression d'images ou de sons. En effet, dans ce genre de domaines, une perte d'information n'est pas forcément gênante voire même perceptible par nos sens.

Compression d'images

Les techniques de compression avec pertes sont nombreuses et variées. Elles varient aussi beaucoup en terme de complexité. Dans cette section, nous allons commencer par nous intéresser à un exemple de compression avec perte très simple : la diminution du nombre de couleurs d'une image. Cette technique est utilisable dans de nombreux formats d'images, comme par exemple le format PNG, le format GIF ou encore le format BMP.

L'idée est très simple : si l'on réduit le nombre de couleurs utilisées par une image, il est possible d'utiliser moins de bits pour représenter la couleur de chaque pixel, et donc de réduire la taille du fichier. Dans la section précédente sur les couleurs, nous avons vu que l'on représente généralement les couleurs en RGB avec 8 bits par composante, soit 24 bits par pixel. Ces 24 bits permettent de représenter des millions de couleurs différentes. Or, en réduisant le nombre de couleurs utilisables, on peut réduire le nombre de bits nécessaires pour les représenter. Par exemple. si l'on réduit le nombre de couleurs à 256, on peut représenter chaque couleur avec seulement 8 bits au lieu de 24, soit 3 fois moins de bits par pixel. En effet, 8 bits permettent de représenter exactement 2⁸ = 256 valeurs différentes.

Reste ensuite à déterminer à quelles couleurs correspondent les différentes suites de bits. Pour cela, on utilise généralement une palette de couleurs, surtout lorsque le nombre de couleurs utilisables est relativement faible. La palette est une table qui indique pour chacune des couleurs utilisables, la valeur RGB de la couleur à utiliser et son mot de code. Cette table est ensuite stockée dans le fichier image en plus des pixels.

La technique de réduction du nombre de couleurs est très efficace sur les images qui ne contiennent pas beaucoup de couleurs différentes. Par contre, elle est beaucoup moins efficace sur les images qui contiennent beaucoup de couleurs différentes, comme les photographies.

Certains formats d'images permettent de réduire la taille du fichier en utilisant d'autres techniques de compression avec pertes. Le format JPEF par exemple, permet de compresser une image en réduisant sa qualité selon le principe suivant : L'image est découpée en blocs de 8x8 pixels, chacun de ces blocs est décrit plus ou moins précisément en fonction de la qualité choisie par une superposition de motifs. Les motifs ayant le moins d'impact sur le résultat final peuvent être supprimés. Cette technique est très efficace sur les photographies, c'est pourquoi le format JPEG est très utilisé pour de telles images. Les détails techniques de cette méthode de compression sont malheureusement assez complexes et ne sont pas abordés dans ce cours.

Si vous souhaitez en apprendre plus sur la méthode de compression JPEG, vous pouvez consulter cette page truffée d'animations qui explique le principe de la transformée de Fourier et de la compression JPEG dans plus de détails.

Compression audio

Il existe également des méthodes de compression avec pertes pour les fichiers audio. Par exemple, dans le format MP3, il est possible de compresser un fichier en supprimant les fréquences sonores élevées, parfois moins perceptibles par l'oreille humaine (surtout avec l'âge).

Dans le format MP3, la compression est paramétrable. En réglant le débit binaire (en anglais bitrate, le nombre de bits par seconde de son), il est possible de choisir le niveau de compression et donc la qualité du fichier audio. Suivant le débit binaire choisi, le fichier audio décrira plus ou moins précisément le signal sonore, incluant plus ou moins de fréquences sonores.

Le débit binaire est généralement exprimé en kilobits par seconde (kb/s). Pour rappel, un kilobit est égal à 1000 bits. Plus le débit binaire est élevé, plus le fichier audio sera de bonne qualité. En contrepartie, le fichier sera plus lourd. Le débit binaire le plus élevé supporté par le format MP3 est de 320 kb/s, alors que le débit binaire le plus faible est de 32 kb/s. Constatez la différence de qualité dans l'exemple ci-dessous.

En éliminant les hautes fréquences d'un signal audio, on peut ainsi réduire la quantité d'information à stocker. Parfois, à cause des limites de l'audition humaine, cette perte de qualité ne sera pas perceptible.

Dans cette section, nous avons vu le principe de la compression de données et les deux grandes familles de techniques de compression : la compression avec pertes et la compression sans pertes.

Pour la compression sans pertes, nous avons étudier l'algorithme de Huffman. Cet algorithme permet de concevoir un code adapté à la représentation de textes où les caractères n'ont pas tous la même fréquence d'apparition. En attribuant des mots de code courts aux caractères les plus fréquents, on peut obtenir un code plus efficace qu'un code binaire à longueur fixe.

Pour la compression avec pertes, nous avons vu diverses techniques, dont la réduction du nombre de couleurs. Dans ce genre de technique, on altère l'information originale pour réduire le nombre de bits nécessaires à sa représentation.

Cette section termine notre chapitre sur la représentation de l'information. Dans la page suivante, nous conclurons ce chapitre par un résumé des notions importantes.