Discussion :

[dourouc05]

zlib est une bibliothèque de compression très largement utilisée dans bon nombre d’applications : les consoles de jeu les plus récentes (PlayStation 3 et 4, Xbox 360 et One, notamment), mais aussi le noyau Linux, les systèmes de gestion des versions comme SVN ou Git ou le format d’image PNG. Sa première version publique a été publiée en 1995 par Jean-Loup Gailly et Mark Adler en implémentant la technique DEFLATE. Son succès est notamment dû à l’absence de brevets logiciels (ce qui a principalement un intérêt aux États-Unis) sur ses algorithmes, mais aussi à des débits en compression et décompression relativement élevés pour une utilisation en ressources assez faible et un bon taux de compression.

Fonctionnement de zlib

Au niveau algorithmique, DEFLATE utilise des techniques éprouvées des années 1990, principalement un dictionnaire (selon l’algorithme LZ77) et un codage de Huffman. Le principe d’un dictionnaire est de trouver des séquences de mots répétées dans le fichier à compresser et de les remplacer par un index dans un dictionnaire. Le codage de Huffman fonctionne avec un arbre pour associer des codes courts à des séquences de bits très fréquentes. Ces deux techniques s’associent pour former la technique de compression standard actuelle.

Concurrents modernes

Cependant, depuis le développement de ces techniques, la recherche au niveau de la compression sans perte a fait de grands progrès. Par exemple, LZMA (l’algorithme derrière 7-Zip et XZ) exploite des idées similaires (plus la probabilité de retrouver des suites de bits dans le fichier à compresser, plus la manière compressée de l’écrire doit être courte), mais avec une dépendance entre différentes séquences de bits (chaîne de Markov), ainsi qu’un codage arithmétique. Le résultat est un taux de compression souvent bien meilleur que DEFLATE, mais le processus de compression est bien plus lent, tout en gardant une décompression rapide et sans besoins extravagants en mémoire. LZHAM est aussi basé sur les mêmes principes avec des améliorations plus modernes et vise principalement une bonne vitesse de décompression (au détriment de la compression).

Cependant, pour un usage plus courant, les débits en compression et décompression sont aussi importants l’un que l’autre, avec un aussi bon taux de compression que possible. Par exemple, pour des pages Web d’un site dynamique, le serveur doit compresser chaque page indépendamment, puisque le contenu varie d’un utilisateur à l’autre. Plusieurs bibliothèques de compression sont en lice, comme LZ4 (qui se propose comme une bibliothèque très généraliste, comme zlib, mais très rapide en compression et décompression), Brotli (proposé par Google pour un usage sur le Web) ou encore BitKnit (proposé par RAD pour la compression de paquets réseau — cette bibliothèque est la seule non libre dans cette courte liste). Ces deux dernières se distinguent par leur âge : elles ont toutes deux été annoncées en janvier 2016, ce qui est très récent.

Une première comparaison concerne la quantité de code de chacune de ces bibliothèques : avec les années, zlib a accumulé pas loin de vingt-cinq mille lignes de code (dont trois mille en assembleur), largement dépassé par Brotli (pas loin de cinquante mille lignes, dont une bonne partie de tables précalculées). Les deux derniers, en comparaison, sont très petits : trois mille lignes pour LZ4 ou deux mille sept cents pour BitKnit (en incluant les commentaires, contrairement aux autres !).

Tentative de comparaison

Rich Geldreich, spécialiste de la compression sans perte et développeur de LZHAM, propose une méthodologie pour comparer ces bibliothèques : au lieu d’utiliser un jeu de données standard, mais sans grande variété (comme un extrait de Wikipedia, c’est-à-dire du texte en anglais sous la forme de XML), il propose un corpus de plusieurs milliers de fichiers (ce qui n’a rien de nouveau, Squash procédant de la même manière) et présente les résultats de manière graphique. Cette visualisation donne un autre aperçu des différentes bibliothèques.

Ce graphique montre, sur l’axe horizontal (logarithmique), les débits en décompression (plus un point est à droite, plus la décompression est rapide) et, sur l’axe vertical (logarithmique aussi), le taux de compression (plus il est élevé, plus le fichier a été réduit en taille). Chaque couleur correspond à un algorithme : vert pour zlib, noir pour LZHAM, rouge pour Brotli, bleu pour BitKnit et jaune pour LZ4.

Deux nuages de points sortent du lot : LZ4, tout à droite, est extrêmement rapide en décompression, tout l’opposé de LZHAM, qui propose néanmoins de bien meilleurs taux de compression. zlib montre un comportement assez étrange : le débit de décompression n’augmente plus à partir d’un certain point, contrairement aux autres bibliothèques. L’auteur propose des comparaisons plus spécifiques des taux de compression de chaque bibliothèque en fonction des fichiers.

Et donc ?

Cette comparaison montre que les différentes bibliothèques ne sont pas toujours meilleures les unes que les autres, tout dépend du contenu du fichier, de sa taille, des ressemblances par rapport aux estimations des concepteurs (plus particulièrement dans le cas d’algorithmes qui ne s’adaptent pas dynamiquement au contenu et préfèrent utiliser des tables prédéfinies, ce qui évite de transmettre une série d’informations).

Notamment, Brotli est prévu pour le Web : il fonctionne particulièrement bien sur des données textuelles. Tout comme zlib, il utilise des tables précalculées, ce qui lui donne un avantage sur des fichiers plus petits. Au contraire, BitKnit fonctionne très bien sur du contenu binaire, bien plus courant pour les données de jeux vidéo. Ces deux bibliothèques ont donc chacune leurs points forts selon les domaines d’application prévus et y sont meilleures que zlib.

Source : zlib in serious danger of becoming obsolete.
Ce contenu a été publié dans Informatique théorique et algorithmique par dourouc05.

[redcurve]

Dans le cadre de l’implémentation d'un système de fichier distribué, j'ai eu l'occasion d'utiliser LZ4 et je confirme les perfs juste énormissime de cet algo

[RyzenOC]

Es ce que sa existe des algo de compressions/décompressions exploitant une architecture multi-coeur, voir le gpu ?

[eclesia]

En réalité les formats de compression évoluent relativement peu.
Les principes et algorithmes utilisés sont toujours les memes depuis les années 90 : huffman,rle,lzx,prediction,dct

Il n'y a pas de nouveautés, juste du 'tuning'. je constate la meme chose avec les formats audio et video meme avec les derniers : opus,jfif,vp9. C'est de l'amélioration souvent au prix de la complexité ou de table précalculé longue comme le bras, mais aucune révolution.

C'est déprimant d'implémenter des variantes pour chaque format sans y voir un réel progrès.

[dourouc05]

Es ce que sa existe des algo de compressions/décompressions exploitant une architecture multi-coeur, voir le gpu ?

Pour le parallèle, pas mal d'outils le font, comme 7Zip ou XZ. Au niveau du GPU, tu as pas mal de compression des textures pour exploiter au mieux la bande passante, des algorithmes déjà intégrés au niveau du matériel (https://developer.nvidia.com/astc-te...or-game-assets). Certains exploitent les GPU (et pas forcément les circuits de compression) pour de la compression, mais ça a plutôt l'air d'être du niveau de la recherche (http://on-demand.gputechconf.com/gtc...using-gpus.pdf), avec le même genre de techniques.

C'est de l'amélioration souvent au prix de la complexité ou de table précalculé longue comme le bras, mais aucune révolution.

De ce que j'ai pu voir, au niveau des progrès, c'est plutôt des modèles probabilistes de la source de plus haut ordre, c'est-à-dire la prise en compte des dépendances entre symboles (deuxième ordre pour Brotli : https://en.wikipedia.org/wiki/Brotli), avec des techniques plus évoluées pour l'adaptabilité (comme https://fgiesen.wordpress.com/2015/0...distributions/). N'oublie pas non plus de citer le codage arithmétique, avec quelques variantes plus récentes (https://fgiesen.wordpress.com/2014/02/02/rans-notes/).

Maintenant, je partage le même constat : les principes de base n'ont pas évolué, on garde toujours les mêmes idées, mais on torture un peu pour que ça marche mieux dans un contexte ou l'autre. En même temps, on s'approche déjà des limites théoriques (théorème de Shannon), d'où le besoin de s'adapter plus fortement aux données à compresser…

[Bktero]

Merci pour l'article, je l'ai trouvé bien écrit

[Logicielz]

Un article très bien écrit Bravo !! j'aimerais bien voir ici un article plus détaillé sur les algorithmes de compression/decompression

[TokenDirect]

Ca serait pas mal une petite comparaison avec zstd.
http://www.zstd.net
Ca semble l'algorithme le plus prometteur du moment, mais il n'est meme pas cite.

[Ngork]

Un article intéressant qui pose de bonnes questions, mais qui ne couvre pas tout le périmètre et ne tient pas compte de l'existant :

Le format zip est le format du conteneur par défaut de nombreux formats de fichiers comme les fichiers bureautiques ODT, DOCX, ODS, XLSX, ... ou les images PNG.
Il y a la simplicité de mise en oeuvre de l'API de la zlib dans un logiciel plus complexe ayant besoin en interne d'une méthode aisée de compression/décompression !
Il y a aussi l'équilibre entre vitesse et taux de compression/décompression de la zlib : c'est la mieux équilibrée des 4 bibliothèques mentionnées ici, elle est rapide sans être une bête de course, elle compresse à un taux très satisfaisant sans prendre deux plombes et décompresse là encore à une vitesse suffisante pour une utilisation à la volée !

Alors, oui, LZ4 notamment est impressionnant de vitesse mais son taux de compression n'est pas terrible par rapport à la zlib.
Quant aux deux petits nouveaux, ne sont-ils pas un peu jeunes pour les comparer à la zlib et même à lz4 ?

Je ne pense pas que la zlib soit proche de la retraite, car elle représente une bibliothèque répandue et intégrée au format de nombreux fichiers, bien réputée, facile d'emploi et équilibrée entre vitesse et puissance, même si pour certains besoins particuliers, les bibliothèques plus récentes présentent des atouts évidents pour un usage très ciblé !

[a028762]

Merci pour cet article instructif ...
et pédagogique, ce qui pour un sujet comme la compression est de l'art.

[dourouc05]

Au niveau algorithmique, la compression de données sans perte (à la ZIP, RAR, TAR.GZ, 7Z) n’a plus beaucoup évolué ces dernières années : il s’agit toujours d’un assemblage de dictionnaires, de code de Huffman, de codage arithmétique, de modèle statistique. Il n’empêche : ces techniques, bien maîtrisées, peuvent toujours s’améliorer petit à petit et donner des outils de compression redoutablement efficaces, comme Google Brotli, arrivé sur le marché début 2016.

Bien maîtrisées, ces techniques peuvent… faire d’énormes progrès ! C’est ainsi que RAD Games a annoncé de nouveaux outils de compression (propriétaires et payants) qui fonctionnent nettement mieux que la concurrence (principalement libre), en fonction du critère de comparaison. Au niveau de l’implémentation, rien de vraiment neuf, si ce n’est un soin tout particulier apporté par de fins connaisseurs du domaine de la compression, avec et sans pertes.

La société peut maintenant se targuer de proposer un outil de compression dont la principale caractéristique est une décompression extrêmement rapide (de trois à cinq fois plus que zlib) avec des taux de compression du même ordre que LZMA (en étant dix à trente fois plus rapide que ce dernier), nommé Kraken. Il donne aussi du fil à retordre à LZ4 : ce dernier reste le plus rapide sur tous les types de documents, mais Kraken s’en rapproche fortement tout en gardant une compression nettement meilleure que LZ4.

Deux dérivés (disponibles depuis cet été) de cet outil sont plus spécialisés, en compressant moins, mais en décompressant (beaucoup) plus vite : Mermaid offre une compression moyenne (du même ordre que ZIP), tout en étant extrêmement rapide en décompression (de sept à douze fois plus que zlib, c’est-à-dire plus de deux fois plus rapide que Kraken) ; Selkie, au contraire, abandonne encore un peu de compression (entre ZIP et LZ4), pour dépasser LZ4 d’un facteur de presque deux (la décompression est très proche d’une copie en mémoire, ce qui est un tour de force technique pour une compression non triviale).

Les chiffres du terrain

Les chiffres donnés sont les officiels, reste encore à les confirmer par des extérieurs. Les comparaisons parfaitement équitables sont difficiles à obtenir, puisque les outils de compression ne sont pas si faciles à obtenir.
En comparant le ratio de compression avec les débits, ces trois outils sont collés du côté des hauts débits (même si Kraken n’y est que peu présent). Zlib occupe une place intermédiaire.

Ces algorithmes sont moins optimisés en temps pour la compression, il n’empêche qu’ils présentent de bons résultats. Ils sont nettement plus éloignés de leurs meilleurs concurrents (comme LZ4… ou zlib).

Du côté algorithmique ?

Ces outils étant propriétaires, difficile d’aller lire leur code source pour comprendre les améliorations proposées. Cependant, certains s’avancent et proposent des pistes qui auraient permis d’atteindre ces nouveaux sommets. Le décodage très rapide pourrait venir d’une utilisation très judicieuse de la hiérarchie mémoire des processeurs actuels : autant de données que possible sont stockées dans les caches du processeur afin de limiter les accès à la mémoire vive (qui sont extrêmement lents).

Une tout autre piste suit la théorie des langages formels, en tentant de construire une grammaire dont le seul mot accepté est le fichier à compresser : les promesses de l’algorithme GLZ sont d’atteindre des taux de compression dignes des algorithmes de prédiction par reconnaissance partielle (la probabilité de rencontrer un symbole — par exemple, un octet — dépend d’un certain nombre de symboles déjà lus) tout en gardant la rapidité des algorithmes de la famille LZ (qui fonctionnent avec des dictionnaires). Les grammaires ainsi générées ont pour particularité d’avoir une entropie faible, c’est-à-dire qu’elles se compressent très bien par d’autres algorithmes.

Toutefois, il semblerait que ces pistes n’aient pas été suivies pour le développement de ces algorithmes. Peut-être nourriront-elles la prochaine génération d’outils de compression ? Cependant, les compromis subsisteront probablement : la révolution d’un algorithme qui compresse très vite et très bien et qui décompresse au moins aussi vite n’est pas encore en vue.

Sources : site officiel d’Oodle, nouveautés d’Oodle 2.3.0 (dont images), Kraken compressor , Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios With LZ-Class Decompression Speed, RAD’s ground breaking lossless compression product benchmarked (dont images).
Voir aussi : le blog de Charles Bloom, développeur de Kraken, Mermaid et Selkie.
Ce contenu a été publié dans Informatique théorique et algorithmique par dourouc05.