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.