Compression Deflate

Deflate (parfois écrit DEFLATE ou Flate) est un algorithme de compression de données sans perte, devenu un standard universel.

Son principe combine deux techniques : l'algorithme LZ77 pour repérer et éliminer les redondances, suivi d'un codage Huffman pour représenter les données de manière plus compacte.

Décrit formellement dans la RFC 1951, il est la pierre angulaire de formats omniprésents comme ZIP, PNG ou la compression HTTP.

La compression Deflate s'effectue en trois étapes séquentielles :

— Analyse LZ77 (par fenêtre glissante) : Examiner les données avec un tampon de recherche pour identifier les séquences de caractères qui se répètent. Remplacer ces séquences par une référence courte (une distance et une longueur) pointant vers leur première occurrence.

— Codage Huffman : Compresser une seconde fois la sortie de l'étape LZ77 (les caractères bruts, les longueurs et les distances) en assignant des codes binaires de longueur variable. Les symboles les plus fréquents reçoivent les codes les plus courts.

— Structuration en blocs : Organiser le tout en une série de blocs de données compressées. Chaque bloc possède un en-tête indiquant le type de codage Huffman utilisé (statique, dynamique ou non compressé).

La décompression est le processus inverse de la compression, et Deflate la rend très efficace :

— Lire l'en-tête du bloc pour déterminer comment les données sont encodées (notamment le type de table Huffman).

— Reconstruire les arbres de Huffman (si le bloc utilise des tables dynamiques) à partir des informations stockées dans le flux.

— Lire et décoder le flux de données : Utiliser les arbres de Huffman pour convertir les bits en séquences de symboles (caractères bruts, longueurs et distances).

— Appliquer LZ77 en sens inverse : Pour chaque référence (distance, longueur) lue, copier la séquence correspondante depuis les données déjà décompressées (le tampon de sortie) pour reconstituer le fichier original.

Bloc non compressé (BTYPE=00) : Les données sont stockées telles quelles, avec un peu de remplissage pour s'aligner sur les octets. Utile quand un segment de données est déjà compressé ou aléatoire (donc non compressible).

Bloc compressé avec les tables de Huffman statiques (BTYPE=01) : Utilise des arbres de Huffman prédéfinis, optimisés pour des données textuelles génériques. Économise l'espace de ne pas avoir à transmettre les tables.

Bloc compressé avec les tables de Huffman dynamiques (BTYPE=10) : Transmet les arbres de Huffman optimisés spécifiquement pour les données du bloc juste avant les données. C'est le plus flexible et offrant généralement la meilleure compression.

Il est crucial de distinguer l'algorithme de compression de ses encapsulations :

— Deflate (RFC 1951) : C'est l'algorithme de compression brut, le contenu lui-même.

— Zlib (RFC 1950) : C'est un format d'emballage léger conçu pour les flux de données en mémoire. Il ajoute un petit en-tête et un checksum Adler-32 pour vérifier l'intégrité des données compressées.

— GZIP (RFC 1952) : C'est un format de fichier plus complet, conçu pour la compression de fichiers individuels. Il ajoute un en-tête contenant le nom du fichier original, son horodatage, et utilise un checksum CRC-32 plus robuste pour vérifier l'intégrité des données originales après décompression.

En résumé : GZIP et Zlib utilisent tous les deux l'algorithme Deflate pour compresser le cœur des données, mais ils l'emballent différemment selon l'usage.

Un flux Deflate brut n'a pas de marqueur universel.

Il est donc difficile de trouver le début du flux en partant à la recherche de la structure d'un premier bloc Deflate (les premiers bits indiquent BFINAL et BTYPE).

En pratique, on rencontre rarement un flux Deflate nu. Il est presque toujours encapsulé dans un conteneur comme un fichier ZIP, PNG, ou dans un flux HTTP.

Le plus simple est donc de vérifier l'en-tête du format conteneur (ZIP, PNG, etc.) qui lui, est facilement identifiable.

Deflate a été conçu au tout début des années 1990 par Phil Katz pour remplacer les algorithmes sous brevet utilisés dans les premières versions de PKZIP.

Sa normalisation dans les RFC date de 1996, ce qui a facilité son adoption dans les formats ZIP, PNG et même HTTP (Content-Encoding: deflate), entre autres.