La compression éclair

L’information, çà prend de la place. Il n’y a qu’à voir la taille d’une image affichée sur un écran pour le réaliser. Heureusement, les espaces de stockage ont évolué. S’il y a 40 ans, les stockages dépassaient rarement les Mégaoctets, de nos jours, ils tutoient les Téraoctets, soit un million de fois plus.

C’est donc dès la préhistoire de l’informatique que des recherches ont été menées pour gagner le plus de place sur des espaces de stockages faméliques. Reprenons l’exemple du Seigneur des anneaux. Le livre comporte environ 230 000 mots, soit environ 1200 000 caractères. Si un caractère est stocké sur 1 octet, cela fait 1,2 Mo.

Une disquette des années 80 pouvait stocker le livre. Quelques grammes de plastiques remplaçaient un kilo de papier. Formidable. Mais il est possible de faire mieux, de stocker le même livre sur un espace plus restreint. Ainsi, avec la place économisée, on pourra écrire d’autres informations ou programmes. Mais comment ? 

Première stratégie : le dictionnaire

Un texte est une suite de mots. Certains mots sont répétés le long du texte. Au lieu de répéter ces mots, il est plus efficace de stocker ces mots dans un dictionnaire et de les remplacer dans le texte par une référence. Cela rappelle le thesaurus. Et le calcul est gagnant. 

Si on considère : 

  • qu’un mot fait 5 caractères en moyenne, 
  • qu’il n’y a pas plus de 20 000 mots différents dans notre livre, 
  • qu’une référence dans le dictionnaire fait 2 caractères.

En écrivant tous les mots dans le dictionnaire et en les remplaçant dans le livre par leurs références, notre texte ne tient plus que sur 2/5 de 1,2 Mo soit 480 Ko. Il faut ajouter le poids du dictionnaire, 140 Ko (20 000 x (5 + 2 caractères)). Soit un total de 620 Ko. On a presque divisé par 2 la taille. 

Calculs et stratégies sont simplifiées dans ma démonstration. Les performances sont meilleures en pratique. Il existe différents algorithmes de compression par dictionnaire. Le plus connu est le LZ77 créé par Abraham Lempel et Jacob Ziv en 1977. Avec l’espace gagné, on peut stocker un autre livre. 

Seconde stratégie : la gestion de l’entropie

Comment définir l’entropie ? Quand j’entends ce mot, c’est pour désigner le désordre dans un système. L’idée est de savoir le caractériser pour comprendre sa logique. Un livre, ce sont des mots. Notre compréhension en fait son sens parce que nous avons les clés pour le déchiffrer. 

Il existe une autre vision qui permet de mesurer l’organisation de ces mots. Ce sont ces outils mathématiques qui sont utilisés pour le caractériser et l’écrire différemment dans une formule. Ici, la compression par codage entropique consiste à proposer pour chaque caractère du livre un code binaire unique. 

Dans la table ASCII, un caractère est codé sur 1 octet soit 8 bits. Le caractère ‘A’ est codé ainsi ‘01000001’. On peut calculer 256 signes avec un octet. Il n’y a que 26 lettres dans notre alphabet. Avec 5 bits, on peut donc coder tout notre alphabet. Mais on peut faire mieux.

En regardant le nombre d’apparition de chaque caractère, en appliquant une logique de code instantané, Le caractère le plus utilisé sera codé avec 1 bit, jusqu’à 2 (21) caractères suivants seront codés sur 2 bits, jusqu’à 4 (22) caractères suivants sur 3 bits, … Un dictionnaire stockera ce code. L’algorithme le plus utilisé pour gérer ainsi l’entropie est le codage de Huffman, 1952. 

L’application : le Zip

Avoir des algorithmes, c’est bien. Les mettre en pratique c’est mieux. Le premier format de compression auquel on pense est le Zip. Il se base sur les 2 algorithmes cités précédemment et il est très utilisé dans sa capacité à compresser le texte. Son utilisation est universelle. N’importe quel ordinateur sait lire un fichier Zip.

Il permet de compresser les données sur votre ordinateur. Vous pouvez stocker plus d’informations et leur envois à travers le Internet est plus rapide puisqu’il y a moins de données à envoyer. En moyenne, il divise par 3 un document. On peut donc stocker 3 fois le Seigneur des anneaux sur la même disquette. 

Le Zip a cependant un inconvénient. Son programme a été élaboré pour des machines avec peu de mémoires. Le Zip utilise un dictionnaire de 64 Ko maximum. C’est très peu pour optimiser des archives de plus en plus lourdes. En dépit de son statut universel, les professionnels lui préfèrent d’autres algorithmes qui ont su s’adapter à leur époque. 

Les stratégies de compression ont évolué avec le temps. Si les algorithmes de Lempel-Ziv et de Huffman sont toujours utilisés, leur implémentation s’est adaptée aux évolutions techniques, repoussant d’autant les gains. Dans un contexte professionnel, j’ai réduit à 1 Mo en 7z une archive qui en faisait 20 Mo en zip

Pourquoi faire mieux alors que le matériel a fait des progrès impressionnants ? Parce que le moindre gain sera exploité et mis en avant dans le monde concurrentiel de l’informatique, et cela pour le bénéfice de ses utilisateurs finaux. 

Partager l'article !!

J’ai de la chance !!!