Un demi de compression

Publié le 26 octobre 2017 par Gee dans Tu sais quoi ?
Inclus dans le livre Grise Bouille, Tome III

Ça faisait longtemps qu’on avait pas un peu causé de binaire, de fichiers, de tout ça… alors c’est parti, attaquons-nous à cet élément central de l’informatique moderne : la compression !

(Et au fait, si tu es du côté de Paris ce week-end, je serai en dédicace à la librairie À Livr’Ouvert samedi après-midi, passe donc me voir, ça fait toujours plaisir 🙂 )

Un demi de compression

PWIVIOUSLY*, ON GREASE BOOYAH :

Une image extraite de l'article « Des zéros et des uns ». Un fichier, c'est une suite de bits auquel on va donner un sens selon une norme prédéfinie : le format (par exemple HTML, MP3, WAV, JPEG, etc.). Gee montre une suite de 0 et de 1 formant le chiffre « 0100 0001 » et dit : « Ça, c'est un octet, soit 8 bits, qui vaut 65 en écriture décimale.  C'est un peu la molécule de notre maison. » Un schéma précise ce que cet octet signifie selon le contexte. Si on le trouve dans un texte brut, c'est un A majuscule.  Dans une image noir et blanc, c'est un pixel gris foncé.  Si c'est dans un fichier audio, c'est la valeur de la vibration sonore à un instant précis. »

Voir l'article Des zéros et des uns.

Reprenons.

💡 Avec des zéros et des uns, on peut donc enregistrer n'importe quelle information (texte, son, image, etc.). Seulement, on veut stocker beaucoup de choses et les octets sont en nombre limités.

Gee précise : « Bah oui, même un disque dur de 1 Tio, soit 1 099 511 627 776 octets, ça reste limité.

▶️ Du coup, stocker chaque information de manière « brute » est rarement une solution acceptable : on va chercher à réduire la place nécessaire pour stocker une information. Ça s'appelle la compression.

Le Geek, en train de galérer pour faire tenir toutes ses affaires dans une petite valise : « Allez ! Rentre là-dedans ! » Une flèche indique : « Compression de données appliquée à la valise : un t-shirt bien plié prend moins de place.  Ce sont les mêmes fringues à l'arrivée, mais selon comment on les stocke, on peut en mettre plus ou moins dedans. »

Par exemple, pour stocker des textes, on peut simplement associer à chaque caractère (chaque lettre, chiffre ou signe de ponctuation) une suite de bits de taille fixe.

C'est l'idée derrière la table ASCII :

Un dessin d'une table anthropomorphisée, sur des skis, qui dit : « Tout schuss ! » Le dessin est rayé/barré avec force.

En code ASCII, chaque caractère prend 1 octet (soit 8 bits*) :

Un extrait de table ASCII. Le caractère « . » vaut 0010 1110, le « 0 » vaut 0011 0000, le « A » vaut 0100 0001, etc.

7 bits à la base, mais on l'a étendue à 8 bits par la suite.

Un texte encadré dit : « Ceci est une phrase sans accent parce que le code ASCII est americain et que du coup, il ne contient pas les caracteres accentues. » Gee regarde le texte en expliquant : « Cette phrase composée de 131 caractères “pèse” donc 131 octets, soit 1048 bits.

Comment réduire ce poids ?

Trois fichiers sont anthropomorphisés. Un fichier ZIP s'exclame, enthousiaste : « Programme minceur pour l'été ! Perdez du poids et rentrez enfin dans votre carte micro-SD taille 36 Mio ! » Un fichier BMP est en train de pleurer et est consolé par un fichier PNG : « Encore le diktat de la minceur !  Viens, BMP, ne les écoute pas ! »

💡 Tout d'abord, remarquons que 8 bits permettent de représenter 256 valeurs (28) et donc de différencier 256 caractères… oui, mais notre phrase utilise beaucoup moins de caractères !

Le même texte que dans l'image d'avant, avec une liste des caractères utilisés : « A, C, I, S, l'espace, a, c, d, e, h, i, l, m, n, o, p, q, r, s, t, u, la virgule et le point ». Gee commente : « 23 caractères, il nous faut donc 5 bits au minimum pour les différencier.  4 bits ne permettent de représenter que 16 valeurs différentes (2 puissance 4). On passe à 32 (2 puissance 5) en utilisant 5 bits.

131 caractères de 5 bits nous donneraient donc 655 bits, soit 82 octets (un gain de 38 % par rapport à la taille en ASCII sur 8 bits).

Une femme passe par l'entrebaillement d'une porte et s'exclame : « Qu'est-ce que tu fous ? Tu bosses, à cette heure-ci ? » Son compagnon, concentré sur une feuille à son bureau, répond : « Nan, je refais les calculs de la BD de Gee…  S'il s'est planté, comment j'vais lui mettre la honte sur les rézozozios ! » Le smiley commente, taquin : « Ne niez pas, je sais que ça vous démange, bande de petits sacripants ! »

▶️ On peut aussi remarquer que les caractères ne sont pas tous autant utilisés les uns que les autres :

Gee regarde une table d'occurrences, où on voit que l'espace est utilisée 23 fois, le « e » 22 fois, le « c » 12 fois, le « a » 10 fois, etc., jusqu'aux points, virgules, « m », « S », « A » et « h » qui ne sont utilisés qu'une fois chacun. Gee commente : « Les 4 caractères les plus utilisés représentent plus de la moitié de la phrase !  Du coup, ça paraît idiot d'utiliser autant de bits pour encoder le « e » que le « . » qui n'apparaît qu'une seule fois. »

💡 Imaginons alors que nous utilisions l'arbre suivant à la fois pour encoder et décoder des caractères.

On part de la racine : à chaque fois que l'on tourne à gauche, on met un 0 ; à chaque fois qu'on tourne à droite, on met un 1.

Quand on atteint une feuille, on atteint un caractère et on a donc le code correspondant au caractère.

Le smiley commente : « Alors déjà, un arbre avec la racine en haut, ça sent le truc d'informaticien qui a pas tout compris à la botanique… » On voit, dans l'arbre, que les caractères fréquents sont proches de la racine et ont donc un code court (00 pour l'espace, 110 pour le « e », 1111 pour le « c », 1011 pour le « a »). Les caractères rares sont loins de la racine et ont un code long (0101100 pour la virgule, 0101101 pour le point, etc.).

Pour le décodage, c'est simple : quand on lit le fichier, on part de la racine et les 0 et les 1 indiquent quelle direction prendre. Quand on atteint une feuille, on a lu un caractère, et on repart d'en haut.

▶️ Chaque caractère peut donc avoir un code binaire de taille différente (plus il est haut dans l'arbre, plus le code est court).

Et comme on a mis les caractères qui apparaissent souvent plutôt vers le haut de l'arbre…

PAF !

Le smiley demande, en souriant : « Ça fait des Chocapics ? »

Gee précise : « Le “e” ne prend plus que 3 bits au lieu de 5, et ses 22 apparitions ne coûtent donc plus que 66 octets au lieu de 110 !  À l'opposé, le point prend 7 bits au lieu de 5, mais comme il n'apparaît qu'une fois, ce n'est pas grave. »

Au total, notre texte n'occupe plus que 514 bits (au lieu des 655 en utilisant un codage régulier sur 5 bits, soit un gain de 22 %).

▶️ Eh bien figurez-vous qu'on peut facilement généraliser cela à tous les textes français : en effet, on sait statistiquement que le « e » apparaît beaucoup plus que le « z » ou le « w » dans notre langue.

Gee, derrière un plateau de jeu, raconte : « Petite anecdote : les fréquences d'apparition (utiles pour la compression) sont aussi utilisées pour déterminer les valeurs des lettres au Scrabble. » La phrase « Waouh, c'est dingue » est écrite avec les lettres du Scrabble. On voit que le W, avec une fréquence de 0,1 %, vaut 10 points ; le A, avec une fréquence de 7 %, vaut 1 point, tout comme le O de fréquence 5 %, le U de fréquence 4 %, etc. ; le H, de fréquence 1 %, vaut 4 points ; le C, de fréquence 3 % vaut 3 points, et le D de fréquence 3 % aussi en vaut seulement 2. Gee précise donc : « À une vache près, hein, c'est pas une science exacte. »

Bien sûr, pour le Scrabble comme pour la compression, les fréquences (et donc les valeurs) varient selon la langue.

⚠️ En réalité, pour la compression, en général, on ne présuppose pas d'une langue ou d'une autre : on construit dynamiquement l'arbre le plus adapté à ce que l'on veut compresser.

La Geekette regarde la valise du Geek qui déborde et dit : « Dis donc, ce pull qui déborde de partout, c'est pas optimal, non ? » Le Geek, bras croisés : « Oui, mais ça permet à mes 12 t-shirts de prendre le moins de place possible ! » La Geekette : « T'avais mieux rangé tes pulls l'hiver dernier, quand t'en avais pris 5. » Le Geek : « Oui, mais c'est l'été maintenant, je m'adapte. » Le smiley, blasé, commente : « Attention : cette métaphore est en train de devenir foireuse. »

💡 L'arbre que j'ai utilisé ci-dessus ne sort pas de nulle part, il vient du principe du codage de Huffman mis au point en 1952 par David A. Huffman pendant sa thèse au MIT.

On parle d'un codage encore utilisé aujourd'hui dans pratiquement tout ce qui est numérique : Huffman fait partie de ces personnes qui ont bien plus révolutionné l'informatique que des Steve Jobs ou des Bill Gates, mais qu'on connaît beaucoup moins.

Après c'est sûr, un universitaire passionné par les mathématiques des origamis, face à un milliardaire qui fait poser des filets anti-suicide dans ses usines en Chine, ça fait pas le poids.

Huffman, tranquillement installé en train de faire des origamis, dit : « Bah quoi ? C'est cool, les origamis. Quelque part, c'est une forme de compression… » Le Geek, transpirant et galérant en froissant des feuilles de papier, dit : « Surtout quand on les foire… »

Alors rendons hommage à ce grand monsieur (hommage posthume, car il nous a quittés en 1999).

Rick Deckard, de Blade Runner, regarde un origami de licorne en se remémorant les paroles : « Dommage qu'il dût mourir… mais c'est notre lot à tous. » Une flèche indique : « Référence pop forcée de ouf. » En bas, une musique en doubles-croches est dessinée, avec les paroles « Tugududu tugududu tugududu…  OUAAAAAAAH OUAAH OUAAH OUAAAAAAAAHHH… » Une flèche indique : « Vangelis. »

💡 Notez que la plupart des formats de compression que vous connaissez (les ZIP, GZIP, etc.) utilisent un codage légèrement différent de celui de Huffman (codage par dictionnaire), mais qui repose sur le même principe universel dans la compression de données : identifier les informations redondantes et les encoder beaucoup plus succinctement que les informations rares.

Ainsi, on peut stocker la même information (aucune perte) en prenant moins de place en moyenne !

Le Geek fait semblant d'être passionné et demande : « Oh, mais dis-moi, Gee ? Et le format MP3 ? Et le format JPEG ? » Gee, souriant, pose l'épaule sur un autre personnage et dit : « Aaaah, mais je vais laisser Cliff te répondre sur ce point… » Le troisième personnage a des lunettes de soleil et un flingue dans la main et dit, en souriant de toutes ses dents : « C'est simple ! Nous en parlerons…  DANS UN PROCHAIN ÉPISODE ! » Gee commente : « Sacré Cliff Hanger… toujours là quand j'ai besoin de lui… » Note : BD sous licence CC BY SA (grisebouille.net), dessinée le 25 octobre 2017 par Gee.

Publié le 26 octobre 2017 par Gee dans Tu sais quoi ?

🛈 Si vous avez aimé cet article, vous pouvez le retrouver dans le livre Grise Bouille, Tome III.

Soutenir

Ce blog est publié sous licence libre, il est librement copiable, partageable, modifiable et réutilisable. Il est gratuit car financé principalement par vos dons. Sans inscription, vous pouvez très simplement me soutenir :

Pour l'année 2023-2024, 11 079 € ont pour l'instant été collectés sur un objectif annuel de 21 000 € (SMIC brut), soit 53 % de l'objectif :

Sources de revenu

L'année étant entamée à 80 %, il y a actuellement un retard de 5 721 € sur l'objectif.

Avancement de l'année

Vous pouvez également, si vous le souhaitez, passer par une plateforme de financement participatif :