Comment fonctionne la compression des fichiers ?

  • Anthony Heddings

    @anthonyheddings

  • 14 août 2018, 6 :40am EDT

Les ingénieurs en logiciel ont toujours développé de nouvelles façons d’intégrer beaucoup de données dans un petit espace. C’était vrai lorsque nos disques durs étaient minuscules, et l’avènement d’Internet n’a fait que rendre la chose plus critique. La compression des fichiers joue un rôle important pour nous connecter, en nous permettant d’envoyer moins de données sur la ligne afin d’avoir des téléchargements plus rapides et d’adapter plus de connexions sur les réseaux occupés.

Alors, comment ça marche ?

Répondre à cette question impliquerait d’expliquer des mathématiques très compliquées, certainement plus que ce que nous pouvons couvrir dans cet article, mais vous n’avez pas besoin de comprendre précisément comment cela fonctionne mathématiquement pour comprendre les bases.

Les bibliothèques les plus populaires pour la compression de texte s’appuient sur deux algorithmes de compression, utilisant les deux en même temps pour atteindre des taux de compression très élevés. Ces deux algorithmes sont « LZ77 » et le « codage de Huffman ». Le codage Huffman est assez compliqué, et nous n’entrerons pas dans les détails ici. Il s’agit essentiellement d’utiliser des mathématiques complexes pour attribuer des codes binaires plus courts aux lettres individuelles, ce qui permet de réduire la taille des fichiers. Si vous voulez en savoir plus, consultez cet article sur le fonctionnement du code ou cet explicateur de Computerphile.

Publicité

LZ77, en revanche, est relativement simple et c’est ce dont nous allons parler ici. Il cherche à supprimer les mots en double et à les remplacer par une « clé » plus petite qui représente le mot.

Prenez par exemple ce court morceau de texte :

L’algorithme LZ77 regarderait ce texte, réaliserait qu’il répète « howtogeek » trois fois, et le changerait en ceci :

Puis, lorsqu’il voudrait relire le texte, il remplacerait chaque instance de (h) par « howtogeek », ce qui nous ramènerait à la phrase originale.

On appelle une compression comme celle-ci « sans perte » – les données que vous mettez sont les mêmes que celles que vous récupérez. Rien n’est perdu.

Publicité

En réalité, LZ77 n’utilise pas une liste de clés, mais remplace plutôt la deuxième et la troisième occurrence par un lien en arrière dans la mémoire :

Alors maintenant, quand il arrive à (h), il va regarder en arrière vers « howtogeek » et lire cela à la place.

Si vous êtes intéressé par une explication plus détaillée, cette vidéo de Computerphile est assez utile.

Maintenant, il s’agit d’un exemple idéalisé. En réalité, la plupart des textes sont compressés avec des clés aussi petites que quelques caractères. Par exemple, le mot « the » serait compressé même lorsqu’il apparaît dans des mots comme « there », « their » et « then ». Avec du texte répété, vous pouvez obtenir des taux de compression fous. Prenez ce fichier texte avec le mot « howtogeek » répété 100 fois. Le fichier texte d’origine pèse trois kilo-octets. Une fois compressé, cependant, il ne prend que 158 octets. C’est une compression de près de 95 %.

Publicité

Now évidemment, c’est un exemple assez extrême puisque nous venons d’avoir le même mot répété à plusieurs reprises. Dans la pratique générale, vous obtiendrez probablement autour de 30-40% de compression en utilisant un format de compression comme ZIP sur un fichier qui est principalement du texte.

Cet algorithme LZ77 s’applique à toutes les données binaires, d’ailleurs, et pas seulement au texte, bien que le texte soit généralement plus facile à compresser en raison du nombre de mots répétés que la plupart des langues utilisent. Une langue comme le chinois pourrait être un peu plus difficile à compresser que l’anglais, par exemple.

Comment fonctionne la compression d’images et de vidéos?

La compression vidéo et audio fonctionne très différemment. Contrairement au texte où vous pouvez avoir une compression sans perte, et où aucune donnée n’est perdue, avec les images, nous avons ce qu’on appelle la « Compression avec perte » où vous perdez quelques données. Et plus vous compressez, plus vous perdez de données.

C’est ce qui conduit à ces JPEG à l’aspect horrible que les gens ont téléchargés, partagés et capturés d’écran plusieurs fois. Chaque fois que l’image est compressée, elle perd des données.

Publicité

Voici un exemple. Il s’agit d’une capture d’écran que j’ai prise et qui n’a pas du tout été compressée.

J’ai ensuite pris cette capture d’écran et je l’ai passée plusieurs fois dans Photoshop, en l’exportant à chaque fois en tant que JPEG de faible qualité. Voici le résultat.

Ça a l’air plutôt mauvais, non ?

Eh bien, ce n’est qu’un scénario catastrophe, l’exportation à 0 % de qualité JPEG à chaque fois. À titre de comparaison, voici un JPEG de qualité 50 %, qui est presque impossible à distinguer de l’image PNG source, à moins de l’agrandir et de l’examiner de près.

Le PNG de cette image faisait 200 Ko, mais ce JPEG de qualité 50 % ne fait que 28 Ko.

Publicité

Alors, comment fait-on pour gagner autant d’espace ? Eh bien, l’algorithme JPEG est une prouesse d’ingénierie. La plupart des images stockent une liste de chiffres, chaque chiffre représentant un seul pixel.

Le JPEG ne fait rien de tout cela. Au lieu de cela, il stocke les images en utilisant ce qu’on appelle une transformée en cosinus discrète, qui est une collection d’ondes sinusoïdales ajoutées ensemble à des intensités variables. Il utilise 64 équations différentes, mais la plupart d’entre elles ne sont pas utilisées. C’est ce que fait le curseur de qualité pour le JPEG dans Photoshop et d’autres applications d’image : choisir le nombre d’équations à utiliser. Les apps utilisent ensuite le codage Huffman pour réduire encore plus la taille du fichier.

Ceci donne aux JPEG un taux de compression incroyablement élevé, qui peut réduire un fichier qui ferait plusieurs mégaoctets à quelques kilooctets, selon la qualité. Bien sûr, si vous l’utilisez trop, vous vous retrouvez avec ceci :

Cette image est horrible. Mais des quantités mineures de compression JPEG peuvent avoir un impact significatif sur la taille du fichier, et cela rend le JPEG très utile pour la compression d’images sur les sites Web. La plupart des images que vous voyez en ligne sont compressées pour économiser sur les temps de téléchargement, en particulier pour les utilisateurs mobiles avec de mauvaises connexions de données. En fait, toutes les images sur How-To Geek ont été compressées pour rendre le chargement des pages plus rapide, et vous ne l’avez probablement jamais remarqué.

Compression vidéo

Les vidéos fonctionnent un peu différemment des images. On pourrait penser qu’il suffit de compresser chaque image de la vidéo en utilisant le JPEG, et c’est certainement ce qu’ils font, mais il y a une meilleure méthode pour la vidéo.

Publicité

Nous utilisons quelque chose appelé « compression inter-images », qui calcule les changements entre chaque image et ne stocke que ceux-ci. Ainsi, par exemple, si vous avez un plan relativement fixe qui prend plusieurs secondes dans une vidéo, beaucoup d’espace est économisé parce que l’algorithme de compression n’a pas besoin de stocker tous les éléments de la scène qui ne changent pas. La compression inter-images est la principale raison d’être de la télévision numérique et de la vidéo sur Internet. Sans elle, les vidéos feraient des centaines de gigaoctets, soit plus que la taille moyenne des disques durs en 2005, au moment du lancement de YouTube.

En outre, comme la compression intertrame fonctionne mieux avec des vidéos essentiellement stationnaires, c’est pourquoi les confettis ruinent la qualité des vidéos.

Note : le GIF ne fait pas cela, ce qui explique pourquoi les GIF animés sont souvent très courts et petits, mais ont tout de même une taille de fichier assez importante.

Publicité

Une autre chose à garder à l’esprit concernant la vidéo est son débit binaire – la quantité de données autorisée par seconde. Si votre débit binaire est de 200 kb/s, par exemple, votre vidéo aura l’air assez mauvaise. La qualité augmente à mesure que le débit augmente, mais après quelques mégaoctets par seconde, vous obtenez des rendements décroissants.

Voici une image zoomée tirée d’une vidéo d’une méduse. Celle de gauche est à 3Mb/s, et celle de droite à 100Mb/s.

Une augmentation de 30x de la taille du fichier, mais pas beaucoup d’augmentation de la qualité. En général, les vidéos YouTube se situent autour de 2-10Mb/s en fonction de votre connexion, car tout ce qui est plus ne serait probablement pas remarqué.

Cette démo fonctionne mieux avec des vidéos réelles, donc si vous voulez vérifier par vous-même, vous pouvez télécharger les mêmes vidéos de test de débit utilisées ici.

Compression audio

La compression audio fonctionne de manière très similaire à la compression de texte et d’image. Là où le JPEG supprime les détails d’une image que vous ne verrez pas, la compression audio fait de même pour les sons. Vous n’aurez peut-être pas besoin d’entendre le grincement du médiator de la guitare sur la corde si la guitare réelle est beaucoup, beaucoup plus forte.

Publicité

Le MP3 utilise également le débit binaire, allant de 48 et 96 kbps (le bas de gamme) à 128 et 240kbps (assez bon) à 320kbps (audio haut de gamme), et vous n’entendrez probablement la différence qu’avec un casque (et des oreilles) exceptionnellement bon.

Il existe également des codecs de compression sans perte pour l’audio – le principal étant le FLAC – qui utilise le codage LZ77 pour fournir un son entièrement sans perte. Certaines personnes ne jurent que par la qualité audio parfaite du FLAC, mais avec la prévalence du MP3, il semble que la plupart des gens ne puissent pas faire la différence ou s’en moquent.

Anthony Heddings
Anthony Heddings est l’ingénieur résident du cloud pour LifeSavvy Media, un rédacteur technique, un programmeur et un expert de la plateforme AWS d’Amazon. Il a écrit des centaines d’articles pour How-To Geek et CloudSavvy IT qui ont été lus des millions de fois.Lire la bio complète  »