Salut et bienvenue dans ce nouvel épisode du podcast de Code Garage.
Je m'appelle Nicolas Brondin-Bernard et aujourd'hui, on va parler de la compression de données.
On va faire une espèce d'introduction avec un algorithme de base pour la compression
de données qui s'appelle l'algorithme RLE.
Alors je ne vais pas vous la prendre.
L'objectif d'un algorithme de compression de données, c'est de prendre une donnée d'entrée,
texte, image, audio, vidéo, peu importe, et de lui appliquer un certain nombre d'opérations
pour en ressortir une donnée plus légère.
Mais il y a plusieurs choses à savoir sur ces algorithmes.
Certains algorithmes sont plus adaptés pour compresser des données avec une typologie
spécifique.
Et surtout, si l'algorithme de compression n'est pas adapté, il peut avoir l'effet
inverse et faire grossir une donnée.
Alors l'algorithme d'aujourd'hui qu'on va étudier RLE, c'est un très bon exemple
de ça donc c'est parfait.
Mais surtout, on divise ces algos de compression en deux grandes familles.
Il y a les algos avec perte, lossie, et sans perte, qu'on appelle lossless.
Alors principalement, les algorithmes avec perte, ça va plutôt être pour déficier
multimédia, plutôt image, son vidéo, etc.
Parce que ça va être utilisé par un humain et on peut se permettre de perdre un petit
peu d'information, de perdre en qualité, en résolution, etc.
Mais il y a des données pour lesquelles on ne peut absolument perdre aucune information.
Si c'est du texte, imaginez, vous stockez un fichier texte, vous le compressez et derrière,
vous retrouvez la même chose mais en fait avec des mots qui manquent.
Bon, ce serait impossible.
Donc voilà, ça, il faut aussi choisir son algorithme de compression en fonction de la
donnée qu'on va compresser.
Donc celui qu'on va découvrir aujourd'hui, il est particulièrement adapté aux images,
à certaines images, et cet algorithme, il s'appelle donc RLE.
Alors RLE, ça signifie Run, Length, Encoding.
Donc en français, on peut le traduire par codage, par plage.
Et il est souvent l'un des premiers algorithmes de compression donnée qu'on étudie parce
que c'est un des plus simples à comprendre, à mettre en place et qu'il est réellement
utilisé dans certains, dans certains autres algorithmes de compression.
Alors, d'abord, c'est un algorithme qui est lossless.
Comme je l'ai dit juste avant, RLE, c'est un algorithme où il n'y a pas de perte,
aucune donnée n'est perdue pendant la compression.
Donc vous allez pouvoir compresser trois fois de suite la même donnée, la qualité
en sortie ne bougera pas.
Si ça vous semble contre-intuitif, dites-vous simplement que pendant une compression lossless,
on troque un petit peu d'espace mémoire contre un peu de puissance de calcul pour
l'encodage et le décodage.
Alors qu'est-ce qui fait l'algorithme en lui-même ?
Et bien en réalité, le fonctionnement de RLE, il consiste à parcourir toute une
ressource du début à la fin et de regrouper les plages de données qui se répètent
en indiquant à chaque fois le nombre d'occurrences de la donnée, le nombre de fois qu'il se
répète.
Donc je vais vous donner des exemples avec du texte parce qu'on se le comprend beaucoup
mieux, c'est beaucoup plus facile de se le représenter.
Mais évidemment, en réalité, on l'utilise sur des bits de fichiers.
Donc on va en parler aussi après.
Si je vous prends par exemple un message qui serait quelqu'un qui crirait dans un fichier
texte évidemment, Hello World avec plein de O pour Hello et plein de O aussi pour World.
Et bien ce fichier-là, il va prendre l'espace de 24 caractères à l'origine et on va le
compresser en RLE.
Donc qu'est-ce qu'on va faire ?
Et bien en fait, on va venir prendre pour chaque lettre le nombre d'occurrences à
laquelle apparaît à la suite.
A la lettre apparaît à la suite.
Donc ce qui va nous donner notre fichier de sortie, ça va être donc 1H, 1E, 2L, pour
l'instant on reconnaît le début de Hello.
Il n'y a pas un seul O mais 8O dans notre fichier, 1W, 8O encore, 1R, 1L, 1D.
Donc ici, la donnée d'entrée, notre Hello World contenait 24 caractères et après la
compression RLE, même si on a ajouté les chiffres, des chiffres devant qui sont le
nombre d'occurrences des lettres, et bien comme on a réduit, après il y a juste une
fois la lettre, en réalité on a réduit à 18 caractères avec la compression.
Ça nous donne une réduction de 25% de la taille de la donnée.
Alors évidemment, si on réfléchit un petit peu sur un texte classique, le RLE devient
inefficace, voire contre-productif, parce que si vous écrivez normalement Hello World,
ça devient 1H, 1E, 2L, 1O, 1W, 1O, 1R, 1L, 1D.
Et donc, la donnée en sortie a grossi de 80% par rapport à la donnée d'entrée.
Mais alors, quelle situation est-ce qu'on peut utiliser RLE ?
Eh bien RLE, il est efficace sur des données qui se répètent énormément.
Donc moins la variance entre chaque morceau de la donnée peut être élevée, plus elle est basse,
plus la compression pourra être importante. Les images, par exemple, ont souvent plus de
chances d'avoir des pixels contigués de la même valeur que les lettres dans un texte,
dans un langage naturel. Par exemple, si on prend une image de ciel bleu,
vous avez plus de chances d'avoir des pixels bleus exactement de la même teinte sur peut-être
une ligne, ou sur quelques pixels les uns à côté des autres. Et pour les images en noir et blanc,
RLE, il a encore plus de chances d'être efficace parce que la variance d'un pixel à l'autre,
elle est au maximum de 255 niveaux de gris contre 255 puissance 3 pour le RGB d'une photo en couleur.
Si on prend, si vous représentez une image par exemple d'une photo de la Lune,
mais où on voit tout l'espace qui est complètement noir, la photo a été prise
complètement noir, on a simplement une demi-lune qui ressort, qui est éclairée sur ce truc-là,
sur cette photo. Normalement, par exemple, toute la première ligne en haut de la photo
devrait être représentée par 8 bits, alors on prend au niveau de gris, et être répété 1920
fois pour une photo en full HD, ce qui pour simplement la toute première ligne de la photo
prendrait au total 1,8 kHz juste pour une ligne complètement noire sans compression. Avec le RLE,
cette première ligne épaisse seulement 11 bits pour stocker le chiffre 1920 et 8 bits pour la
valeur du niveau de gris, en l'occurrence 0 puisque c'est complètement noir, ce qui nous donne un total
de 19 bits, donc 19 bits comparé à 1,8 kHz, c'est 97 fois plus léger que l'original.
Évidemment, c'est super impressionnant pour les applets de couleur, mais dès qu'on va arriver
au centre de l'image, l'efficacité du RLE sera moins grande, et ce sera le cas avec la plupart des
images réelles. Donc il est possible d'avoir de très bons résultats sur des illustrations par
exemple, parce que les applets de couleur sont plus fréquents. L'algorithme RLE,
c'est un algorithme assez spécifique, mais en réalité il est souvent utilisé comme
algorithme supplémentaire par exemple par-dessus d'autres algorithmes de compression avec perte.
C'est le cas du JPEG par exemple. On a d'abord une première compression avec perte,
vous le savez, quand vous compressez un peu mal un JPEG avec une trop petite résolution ou une trop
grande compression, il va vous faire des espèces de carrés. Mais par contre, quand on reprend ces
applets qui ont été faites par les carrés et qu'on remet un algorithme RLE par-dessus,
ça va encore réduire la taille. Parce qu'en réalité, on a fait baisser la variance globale
au prix à la plume. C'est cet épisode, j'espère qu'il vous aura appris quelque chose, j'espère
qu'il vous a été utile. C'était vraiment une petite introduction à la compression donnée,
avec un algorithme qui est très simple. Alors si jamais vous avez un petit peu de mal à visualiser
quand je vous parlais des lettres, des chiffres, etc. n'hésitez pas, je vous mets dans les notes
de l'épisode l'article d'origine que j'ai écrit avec la version textuelle de toutes
ces explications. Vous avez aussi la photo de la lune avec le noir, etc. Donc ça sera peut-être
plus facile si vous n'avez jamais du mal à vous représenter mentalement en écoutant
cet épisode, le lien de l'article et dans les notes de l'épisode. Sur ce, je vous dis à la
semaine prochaine pour un prochain épisode de Code Garage, où directement rendez-vous sur
code-garage.fr pour retrouver d'abord tous les épisodes du podcast, mais aussi tous les articles
de blogs. On a plus de 400 articles sur le blog et aussi tous les cours complets pour apprendre
guide SQL, pour apprendre à devenir freelance. Bref, tous les cours qu'il vous faut en tant que dev pour
continuer à progresser est disponible seulement pour 19 euros 4 en 19 par mois. Voilà, vous avez
accès à tous, aux exercices, au projet, etc. Moi je vous dis à la semaine prochaine pour un prochain
épisode. Salut !