Mis à jour le mercredi 12 juillet 2017
  • 10 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Respirez… Compressez !

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Nous avons vu dans les chapitres précédents qu’une même chose peut être dite de manière plus ou moins rapide, et l’intérêt de la compression : gagner de l’espace de stockage, et du temps de transmission si on veut envoyer les données. Parfois, si l’on veut vraiment compresser une information, on peut se permettre de perdre un peu de qualité, en modifiant quelques pixels sur une image par exemple, sans que cela ne perturbe la lecture de l’information, voire même sans que cela ne soit vraiment visible. Mais pour le texte, impossible d’appliquer le même raisonnement ! Par exemple si j’écris “cailler”, que je le compresse, et que quand je le décompresse j’obtiens “tailler”, alors oui c’est presque le même résultat, mais ça ne suffit pas.

De même si le message est “Transférer 100 euros de mon compte à celui de Florent” et qu’après compression/décompression ça donne “Transférer 900 euros de mon compte à celui de Florent” je vais être moyennement contente (Florent par contre…). Pourtant, dans les deux exemples ci-dessus,  il n’y a qu’un caractère qui diffère à chaque fois.

Tout ça pour illustrer le fait que, sur le texte, la compression “avec perte” c’est juste hors de question. Heureusement, il existe aussi des méthodes pour compresser le texte dites “sans pertes” qui permettent de retrouver exactement le message original (et en particulier de ne pas se faire vider son compte en banque :-°).

Le codage de Huffman

Revenons à nos 0 et nos 1. Pour coder un caractère en binaire, nous savons que nous pouvons utiliser la table ASCII. Mais peut-on faire mieux pour minimiser la taille d’un message ? C’est le moment d’essayer vous même ce projet Scratch ! A vous d’associer un code à chaque lettre (sans oublier le signe espace) pour minimiser la taille du message codé.

Vous avez testé le projet ? Suffisamment pour trouver le code le plus efficace et obtenir le meilleur score possible ? Vérifions cela dans la prochaine vidéo !

Mais sur les exemples de la vidéo, il y a parfois plusieurs lettres ou “petits arbres intermédiaires” qui portent la même valeur, dans ce cas on choisit lesquels pour les assembler ? 

En fait on fait comme on veut, ça donnera des arbres différents (et c’est pour ça qu’avec le fichier compressé il faut donner l’arbre pour que les gens puissent le décompresser), mais équivalents du point de vue de la longueur du texte compressé.

Quatre arbres possibles pour le texte BEBELABELLE

Sur le projet Scratch, les codes proposés ont bien été créés en faisant un arbre de Huffman. Du coup, vous allez pouvoir retrouver un codage à 84 bits en triant les lettres par fréquence d’apparition, puis en donnant les codes les plus petits aux lettres les plus fréquentes et, ô miracle (ou plutôt ô science), ça fonctionne !

Et sur de “vrais” textes plus longs, ça fonctionne bien ?

Oui bien sûr ! Sur un texte en français, on peut obtenir avec cette méthode des taux de compression de l’ordre de 40%.

Sur le texte intégral de Cyrano de Bergerac (d’Edmond Rostand, pour briller en société), on a environ 240 mille caractères, ce qui ferait en ASCII 1,9 millions de bits. Avec le codage de Huffman, cela ne fait plus qu’1,2 millions de bits – plus la table de codage – soit 37% en moins ! Et sur le texte du Malade imaginaire (de Molière) on monte à 42% pour un texte de 127 mille caractères au départ. Pas mal non ?

Le retour de pixel-paravent

Rappelez-vous : dans pixel-paravent on transmettait un à un les bits (0 ou 1, noir ou blanc) pour que son interlocuteur puisse refaire un dessin sans le voir. Oui mais bon maintenant qu’on a parlé de compression, on peut bien l’appliquer à ce jeu.

Chouette, on va appliquer l’algorithme de Huffman aux pixels !!!

 Vous y tenez ? OK. Voyons ce que ça donne. On a donc deux caractères différents, 0 et 1, et on va les représenter de la manière la plus compacte possible, par exemple en prenant… 0 et 1.

Ah oui mince là on ne gagne rien du tout. On ne peut pas compresser nos images alors ?

Et non Huffman ne nous aide pas pour des images aussi simples…

Par contre quand on a seulement deux caractères différents, on a toutes les chances d’avoir souvent plusieurs caractères identiques qui se suivent, comme une longue liste de 0 (pour une zone blanche de notre image) ou de 1. Et du coup, au lieu de dire 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 on pourrait dire “onze 1 six 0”, exactement comme lorsqu’on a compressé notre liste sous Scratch. C’est même assez naturel, on le fait souvent quand on doit transmettre un grand nombre, de regrouper des chiffres pareils.

Et même on peut pousser plus loin. On sait forcément qu’on va donner une suite de 1 puis une suite de 0 et ainsi de suite. Du coup on peut arrêter de dire que ce sont des uns puis des zéros, et transformer “onze 1 six 0 trois 1 dix-huit 0” en “onze, six, trois, dix-huit”. Pour cela il faut juste s’assurer de trois choses :

  • Avant de commencer le récepteur de notre message doit savoir si on va commencer par des zéros ou des 1 (il suffit de décider une fois pour toutes par quoi on commence)

  • Il ne faut pas s’arrêter en fin de ligne. Si une ligne finit par des 1 et la suivante commence par des 1, il faut les mettre dans un seul groupe.

  • Du coup, comme on ne nous dit pas où se finit une ligne, on doit absolument transmettre la taille de l’image à l’avance (nombre de lignes de pixels et nombre de colonnes).

Pour le faire avec des enfants, il est intéressant de les laisser trouver comment compresser l’info, avant de les guider, éventuellement, vers la solution ci-dessus (ou de suivre la leur si elle est intéressante). Des extensions possibles (si on a plus de temps où pour les participant-e-s qui iraient plus vite que les autres) : se poser la question de ce qu’il se passerait si on “oubliait” un des trois points ci-dessus.

La compression, une solution universelle ?

Mais c’est génial tout ça : on prend un texte, n’importe lequel, on le compresse, il devient plus petit ? Et du coup si le texte compressé, je le “re-compresse”, il devient encore plus petit ?

En fait non, tous les textes ne deviennent pas plus petits en passant dans un algorithme de compression. Et ce n’est pas que les algorithmes ne sont pas bons, c’est qu’il est totalement impossible de réaliser un algorithme de compression capable de rendre tous les textes plus petits, sans perdre de l’information. Ce qui nous sauve, c’est que justement on ne compresse pas n’importe quel texte, mais des “vrais” textes qui ont des propriétés particulières, par exemple certaines lettres plus fréquentes que d’autres, et des groupes de lettres plus fréquents aussi. Et du coup en pratique la compression est vraiment efficace.

Et vous, vous regardez des vidéos sur Internet ?

Compression, décompression… Vous maîtrisez maintenant tout ça, et vous savez même réaliser des programmes dans Scratch qui le font pour vous (si, si !). Dans votre usage quotidien, comment cela se manifeste-t-il ? Eh bien par exemple, quand vous rendez vos devoirs sur OpenClassrooms, et que vous mettez tous vos fichiers dans une archive zip, ce n’est rien d’autre qu’une compression de tous vos fichiers !

Quand vous regardez une vidéo sur Youtube (ou autre), vous constatez peut-être des changements de qualité de l’image ? Essayez cette vidéo par exemple : https://youtu.be/k74FZnf9GT0.

Si vous cliquez sur les paramètres de la vidéo (le petit engrenage), il y a une sous-rubrique “Qualité” sur laquelle vous pouvez cliquer. Changez la valeur, de 720p à 144p : vous constaterez que la compression altère l’image.

Lorsque vous écoutez de la musique aussi, si elle est numérisée, vous pouvez avoir des qualités audio différentes ; un fichier mp3 par exemple est un fichier audio compressé, on y a enlevé toutes les fréquences inaudibles pour l’oreille humaine.

Bien sûr, on a traité principalement d’images et de textes dans ce cours, mais vous avez compris que le principe est le même pour tous types de fichiers. Par exemple, pour la musique, vous auriez aussi pu encoder des sons avec Scratch sous forme de listes de notes, et compresser ces listes pour gagner de la place. Un prochain défi peut-être ? ;)

En résumé

  • La compression avec pertes autorise un peu de perte de qualité par rapport aux données originales. Elle est utilisée en général pour les images et le son, mais n’est pas envisageable pour le texte.

  • La compression sans perte garantit de retrouver, quand on décompresse, la donnée originale, sans aucune modification.

  • Le codage de Huffman permet de compresser sans perte un texte et il est le plus efficace des algorithmes qui associent un code à une lettre.

  • Il est utilisé comme ingrédient de base de nombreux algorithmes de compression.

  • Il ne peut pas exister d’algorithme de compression sans perte qui réussirait à compresser TOUS les fichiers possibles.

  • L’activité pixel-paravent permet d’expérimenter la compression de manière simple et ludique avec les enfants.

Exemple de certificat de réussite
Exemple de certificat de réussite