Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Faut-il mettre zlib à la retraite ?
Des concurrents plus modernes comme Brotli et BitKnit font mieux sur tous les critères

Le , par dourouc05

90PARTAGES

14  0 
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.

Une erreur dans cette actualité ? Signalez-le nous !

Avatar de Ngork
Membre éprouvé https://www.developpez.com
Le 10/03/2016 à 21:32
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é !
4  0 
Avatar de eclesia
Rédacteur https://www.developpez.com
Le 05/03/2016 à 14:09
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.
2  0 
Avatar de dourouc05
Responsable Qt & Livres https://www.developpez.com
Le 05/03/2016 à 16:20
Citation Envoyé par sazearte Voir le message
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.

Citation Envoyé par eclesia Voir le message
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/0...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…
2  0 
Avatar de Bktero
Modérateur https://www.developpez.com
Le 06/03/2016 à 17:13
Merci pour l'article, je l'ai trouvé bien écrit
1  0 
Avatar de redcurve
Membre éclairé https://www.developpez.com
Le 05/03/2016 à 13:16
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
0  0 
Avatar de RyzenOC
Inactif https://www.developpez.com
Le 05/03/2016 à 13:40
Es ce que sa existe des algo de compressions/décompressions exploitant une architecture multi-coeur, voir le gpu ?
0  0 
Avatar de Logicielz
Futur Membre du Club https://www.developpez.com
Le 07/03/2016 à 15:36
Un article très bien écrit Bravo !! j'aimerais bien voir ici un article plus détaillé sur les algorithmes de compression/decompression
0  0 
Avatar de TokenDirect
Nouveau Candidat au Club https://www.developpez.com
Le 08/03/2016 à 2:56
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.
0  0 
Avatar de a028762
Membre confirmé https://www.developpez.com
Le 11/03/2016 à 9:06
Merci pour cet article instructif ...
et pédagogique, ce qui pour un sujet comme la compression est de l'art.
0  0