Deflate

Deflate est un format de compression de données sans perte qui couple l'algorithme LZ77 et le codage de Huffman. Il fut défini à l'origine par Phil Katz pour la version 2 de son archiveur PKZIP, et fut plus tard défini dans la RFC 1951 en 1996, par Jean-Loup Gailly et Mark Adler.

Deflate n'est soumis à aucun brevet, ce qui a conduit à son utilisation dans les formats gzip et PNG, en plus du format zip auquel il était au départ destiné, à l'époque où le brevet sur l'algorithme LZW (utilisé dans le format GIF) n'avait pas encore expiré.

deflate désigne aussi une méthode d'encodage de contenus HTTP (en) (aux côtés de gzip ou br), le format de fichier utilisé est alors celui de zlib (RFC 1950)^[1].

Détails

Structure par blocs

Deflate prescrit une structure par blocs de données dont les trois premiers bits donnent le type.

Le premier bit est 1 si le bloc est le dernier bloc du fichier, et 0 sinon.

Les deux bits suivants indiquent comment les données sont encodées, selon trois types possibles indiqués pas les marqueurs 00, 01 et 10. Le marqueur 11 n'est pas utilisé.

Les blocs compressés n'ont pas de limite de taille : un caractère de l'alphabet donne un signal de fin de bloc. Un fichier contenant un seul bloc compressé contenant tout le fichier source est donc possible.

Bloc non compressé

Ce bloc contient les données brutes qui seront recopiées directement dans le fichier décompressé.

Ce bloc est indiqué par le marqueur 00 et contient dans ses deux premiers octets un entier non signé sur 16 bits donnant la longueur LEN du bloc, et dans les deux suivants le complément à un de cet entier. Les LEN octets suivants forment le bloc^[2].

La longueur de ce type de bloc est donc limitée à 64 Kio (limite d'un entier non signé sur 16 bits).

Blocs compressés

Les données sont considérées par octet et d'abord compressées avec l'algorithme LZ77 : les caractères désignent soit un octet brut soit une référence à des données déjà existantes précédemment dans le fichier. Cette référence est sous la forme d'un couple (longueur de la référence, distance à la référence) où la distance est inférieure à 32768 octets (soit 32 Kio) et la longueur dans l'intervalle d'entiers [3, 258]. Ces bornes permettent de définir deux alphabets sur lesquels l'encodage par arbres de Huffman a lieu.

Code de Huffman standard

Le marqueur 01 indique un bloc encodé par un arbre de Huffman standard défini dans la RFC 1951.

On considère deux alphabets : d'une part les entiers 0 à 285, et un autre alphabet contenant les entiers de 0 à 29. Les alphabets des octets bruts et des longueurs sont fusionnés dans le premier alphabet. Cela veut dire que pour un octet brut est attribué directement le code qui correspond à sa valeur en entier de 0 à 255, le code 256 correspond à la fin du bloc et les codes suivants correspondent à des longueurs, par exemple 257 pour une longueur de 3. Pour certains codes la longueur n'est pas unique, c'est pour cela qu'on utilise des bits supplémentaires pour la déterminer. Par exemple, pour coder la longueur 25 est utilisé 270 à qui on ajoute deux bits, ici 10 codant le chiffre 2 car ${\displaystyle 25=23+2}$. De même pour la distance, on lui attribue un code qui correspond à la tranche à laquelle elle appartient, puis on utilise éventuellement des bits supplémentaires pour coder sa valeur. Le nombre de bits supplémentaires attendu est spécifié dans la section 3.2.5.

Une fois cette première étape passée, on modifie les codes précédemment obtenus en code de Huffman. Pour les codes correspondant aux octets bruts et aux longueurs, on leur attribue un code allant de 7 à 9 bits, puis on ajoute les éventuels bits supplémentaires. Par exemple, le code 270 sera représenté par 0001110 (7 bits) alors que le code 280 sera représenté par 11000000 (8 bits), cela permet de minimiser le nombre de bits utilisés pour les codes les plus fréquents. On remarquera que les codes 286 et 287 ont une attribution de code de Huffman, bien que ces codes ne figureront jamais dans les données compressées. Pour la distance, on utilise comme code de Huffman le code précédemment obtenu concaténé avec les éventuels bits supplémentaires. On peut alors juxtaposer le code de Huffman de la longueur, ses éventuels bits supplémentaires puis celui de la distance avec ses bits supplémentaires, on obtient alors le code compressé du couple (longueur de la référence, distance à la référence) .

Code de Huffman adapté

Le marqueur 10 indique un bloc encodé par un arbre de Huffman fourni dans le fichier, qui est lui même encodé suivant un format prescrit par Deflate. Ce type de bloc est désigné pour l'utilisation de codage Huffman adaptatif lors de la compression, ce qui permet d'avoir un encodage adapté à sa source.

Limitations

Deflate ne définit qu'un format de données compressées. Ce n'est en particulier pas un format de fichier : il est ainsi recommandé dans la section 6 de coupler les données Deflate avec un code correcteur d'erreurs pour former une archive, comme c'est le cas pour gzip.

Deflate64

Il s'agit d'une variante de Deflate qui utilise un dictionnaire plus grand (64 ko au lieu de 32 ko), des codes longueurs de 16 bits (pour des longueurs de 3 à 65536 octets), et des codes distances de 14 bits (30-31). Le taux de compression est légèrement amélioré en comparaison avec Deflate.

PKZIP prend en charge Deflate64 à partir de la version 2.50. Ce format a été créé par PKWARE et est inclus dans la spécification ZIP (méthode de compression 9), bien qu'il ne soit pas décrit en détail et soit considéré comme un format propriétaire par PKWARE (qui revendique Deflate64 comme marque de commerce).

Deflate64 est pris en charge par plusieurs produits (7-zip, Info-ZIP) mais pas par zlib, en raison de son aspect propriétaire et des faibles améliorations qu'il apporte.