Groupe de travail Réseau |
P. Deutsch, Aladdin Enterprises |
Request for Comments : 1951 |
mai 1996 |
Catégorie : Information |
Traduction Claude Brière de L'Isle |
Spécification du format de données compressées DEFLATE, version 1.3
Statut de ce mémoire
Le présent mémoire apporte des informations pour la communauté de l'Internet. Le présent mémoire ne spécifie aucune sorte de norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction.
Note de l'IESG :
L'IESG ne prend aucune position sur la validité des déclarations de droits de propriété intellectuelle contenues dans le présent document.
Notices
Copyright (c) 1996 L. Peter Deutsch
Permission est accordée de copier et distribuer le présent document pour tout objet et sans charges, y compris sa traduction dans d'autres langues et son incorporation dans des compilations, pourvu que la notice de copyright et la présente notice soient reproduites, et que tout changement substantiel ou suppression par rapport à l'original soit clairement indiqué.
Un pointeur sur la plus récente version et sa documentation en format HTML se trouve à l'URL <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
Résumé
La présente spécification définit un format de données compressées sans perte qui compresse les données en utilisant une combinaison de l'algorithme LZ77 et du codage de Huffman, avec une efficacité comparable aux meilleures méthodes de compression de propos général actuellement disponibles. Les données peuvent être produites ou consommées, même pour un flux de données d'entrée de longueur arbitraire présentées en séquence, en utilisant seulement une mémorisation intermédiaire de taille définie a priori. Le format peut être mis en œuvre directement d'une façon non couverte par les brevets.
Table des Matières
1.5 Définitions des termes et conventions utilisées
1.6 Changements par rapport aux versions précédentes
2. Généralités sur la représentation compressée
3.1 Conventions générales dans les diagrammes ci-dessous
3.2.1 Synopsis du codage de préfixe et de Huffman
3.2.2 Utilisation du codage Huffman dans le format "deflate"
3.2.3 Détails du format de bloc
3.2.4 Blocs non compressés (BTYPE=00)
3.2.5 Blocs compressés (codes de longueur et de distance)
3.2.6 Compression avec des codes de Huffman fixes (BTYPE=01)
3.2.7 Compression avec des codes de Huffman dynamiques (BTYPE=10)
4. Détails de l'algorithme de compression
6. Considérations pour la sécurité
L'objet de la présente spécification est de définir un format de données compressées sans perte qui :
* est indépendant du type de CPU, du système d'exploitation, du système de fichiers, et du jeu de caractères, et qui peut donc être utilisé pour les échanges ;
* peut être produit ou consommé, même pour un flux de données d'entrée arbitrairement long présenté en séquence, en utilisant seulement une quantité limitée a priori de mémorisation intermédiaire, et peut donc être utilisé dans les communications de données ou structures similaires telles que des filtres Unix ;
* compresse les données avec une efficacité comparable aux meilleures méthodes de compression d'utilité générale actuellement disponibles, et en particulier considérablement meilleure que le programme "compress" ;
* peut être mis en œuvre directement sans être couvert par des brevets, et donc peut être pratiqué librement ;
* est compatible avec le format de fichier produit par l'utilisateur actuellement largement utilisé gzip, ce qui fait que les décompresseurs conformes seront capables de lire les données produites par le compresseur gzip existant.
Le format de données défini par la présente spécification n'essaye pas de :
* permettre un accès aléatoire aux données compressées ;
* compresser les données spécialisées (par exemple, des graphiques matriciels) aussi bien que les meilleurs algorithmes spécialisés actuellement disponibles.
Un simple argument de comptage montre qu'aucun algorithme de compression sans perte ne peut compresser tout ensemble de données d'entrée possible. Pour le format définit ici, le plus mauvais cas d'expansion est 5 octets par bloc de 32 k octet, c'est-à-dire, une augmentation de taille de 0,015 % pour de grands ensembles de données. Le texte français se compresse habituellement d'un facteur de 2,5 à 3 ; les fichiers exécutables compressent habituellement un peu moins ; les données graphiques telles que les images matricielles peuvent se compresser beaucoup plus.
La présente spécification est destinée à être utilisée par ceux qui mettent en œuvre des logiciels de compression de données en format "deflate" et/ou décompressent les données à partir d'un format "deflate".
Le texte de la spécification suppose des bases en programmation au niveau du bit et des autres représentations des primitives de données. La familiarité avec la technique de codage de Huffman peut aider mais n'est pas nécessaire.
La présente spécification décrit une méthode de représentation d'une séquence d'octets comme une séquence (généralement plus courte) de bits, et une méthode pour empaqueter la dernière séquence de bits en octets.
1.4 Conformité
Sauf indication contraire ci-dessous, un décompresseur conforme doit être capable d'accepter et décompresser tout ensemble de données qui se conforme à toutes les spécifications présentées ici ; un compresseur conforme doit produire des ensembles de sonnées qui se conforment à toutes les spécifications présentés ici.
1.5 Définitions des termes et conventions utilisées
Octet : 8 bits mémorisés ou transmis comme une unité. Pour la présente spécification, un octet est exactement 8 bits, même sur les machines qui mémorisent un caractère sur un nombre de bits différent de huit. Voir ci-dessous, pour la numérotation des bits au sein d'un octet.
Chaîne : une séquence arbitraire d'octets.
1.6 Changements par rapport aux versions précédentes
Il n'y a pas eu de changement technique au format deflate depuis la version 1.1 de cette spécification. Dans la version 1.2, la terminologie a été modifiée. La version 1.3 est une conversion de la spécification au style des RFC.
2. Généralités sur la représentation compressée
Un ensemble de données compressées consiste en une série de blocs, correspondant aux blocs successifs des données d'entrée. Les tailles des blocs sont arbitraires, sauf que les blocs non compressibles sont limités à 65 535 octets.
Chaque bloc est compressé en utilisant une combinaison de l'algorithme LZ77 et du codage Huffman. Les arborescences de Huffman pour chaque bloc sont indépendantes de celles des blocs précédents ou suivants ; l'algorithme LZ77 peut utiliser une référence ou une chaîne dupliquée qui survenait dans un bloc précédent, jusqu'à 32 k octets d'entrée avant.
Chaque bloc consiste en deux parties : une paire d'arbres de code Huffman qui décrit la représentation de la partie de données compressées et une partie de données compressées. (Les arbres de Huffman eux-mêmes sont compressés en utilisant le codage de Huffman.) Les données compressées consistent en une série d'éléments de deux types : les octets littéraux (de chaîne qui n'ont pas été détectées comme dupliquées au sein des 32 k octets d'entrée précédents), et les pointeurs sur des chaînes dupliquées, où un pointeur est représenté comme une paire <longueur, distance en arrière>. La représentation utilisée dans le format "deflate" limite les distances à 32 k octets et les longueurs à 258 octets, mais ne limite pas la taille d'un bloc, excepté pour les blocs non compressibles,dont la limite est notée ci-dessus.
Chaque type de valeur (littéraux, distances, et longueur) dans les données compressées est représentée en utilisant un code de Huffman, en utilisant un arbre de code pour les littéraux et les longueurs et un arbre de code séparé pour les distances. Les arbres de code pour chaque bloc apparaissent en forme compacte juste avant les données compressées qui forment ce bloc.
3.1 Conventions générales dans les diagrammes ci-dessous
Une boîte comme ceci :
+---+
| | <-- la barre verticale peut être absente
+---+
représente un octet ;
une boîte comme ceci :
+==============+
| |
+==============+
représente un nombre variable d'octets.
Les octets mémorisés au sein d'un ordinateur n'ont pas un "ordre binaire", car ils sont toujours traités comme une unité. Cependant, un octet considéré comme un entier entre 0 et 255 a un bit de poids fort et un bit de moindre poids, et comme on écrit les nombres avec le chiffre de poids fort à gauche, on écrit aussi les octets avec le bit de poids fort à gauche. Dans les diagrammes ci-dessous, on numérote les bits d'un octet de telle sorte que le bit 0 soit le bit de moindre poids, c'est-à-dire que les bits sont numérotés comme suit :
76543210 |
Dans un ordinateur, un nombre peut occuper plusieurs octets. Tous les nombres sur plusieurs octets dans le format décrit ici sont mémorisés avec l'octet de moindre poids en premier (à la plus faible adresse de mémoire). Par exemple, le nombre décimal 520 est mémorisé sous la forme de :
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + octet de poids fort = 2 x 256
+ octet de moindre poids = 8
Le présent document ne traite pas la question de l'ordre dans lequel les bits d'un octet sont transmis sur un support à séquence binaire, car le format des données final décrit ici est orienté octet – et non orienté sur le bit. Cependant, on décrit le format de bloc compressé ci-dessous comme une séquence d'éléments de données de diverses longueurs binaires, et non comme une séquence d'octets. On doit donc spécifier comment empaqueter ces éléments de données en octets pour former la séquence finale d'octets compressée :
* Les éléments de données sont empaquetés en octets dans l'ordre croissant des numéros de bit au sein de l'octet, c'est-à-dire, en commençant par le bit de moindre poids (LSB, least significant bit) de l'octet.
* Les éléments de données autres que les codes de Huffman sont empaquetés en commençant par le bit de moindre poids de l'élément de données.
* Les codes de Huffman sont empaquetés en commençant par le bit de poids fort (MSB, most significant bit) du code.
En d'autres termes, si on veut imprimer les données compressées comme une séquence d'octets, en commençant par le premier octet à la marge *droite* et en continuant vers la *gauche*, avec le bit de poids fort de chaque octet sur la gauche comme d'habitude, on sera capable d'analyser le résultat de droite à gauche, avec les élément de largeur fixe dans l'ordre correct de MSB à LSB et les codes de Huffman dans l'ordre binaire inversé (c'est-à-dire, avec le premier bit du code dans la position relative de LSB).
Le codage de préfixe représente des symboles tirés d'un alphabet connu à priori par des séquences binaires (codes), un code pour chaque symbole, d'une manière telle que différents symboles puissent être représentés par des séquences binaires de différentes longueurs, mais un analyseur peut toujours analyser sans ambiguïté une chaîne codée symbole par symbole.
On définit un code de préfixe comme une arborescence binaire dans laquelle les deux bords descendants de chaque nœud qui n'est pas d'extrémité sont marqués 0 et 1 et dans laquelle les nœuds d'extrémité correspondent un à un (sont étiquetés) avec les symboles de l'alphabet ; le code pour un symbole est alors la séquence de 0 et de 1 sur les bords qui vont de la racine à l'extrémité étiquetée avec ce symbole. Par exemple :
/\ Symbole Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
Un analyseur peut décoder le prochain symbole à partir d'un flux d'entrées codé en descendant l'arborescence à partir de la racine, en choisissant à chaque pas le bord correspondant au prochain bit d'entrée.
Étant donné un alphabet avec une fréquence de symboles connue, l'algorithme de Huffman permet la construction d'un code de préfixe optimal (ou code qui représente les chaînes avec ces fréquences de symbole en utilisant le moins de bits de tous les codes de préfixe possibles pour cet alphabet). Un tel code est appelé un code de Huffman. (Voir le chapitre 5 de la référence [1], références pour des informations complémentaires sur les codes de Huffman.)
Noter que dans le format "deflate", les codes de Huffman pour les divers alphabets ne doivent pas excéder certaines longueurs de code maximales. Cette contrainte complique l'algorithme pour calculer les longueurs de code à partir des fréquences de symboles. Là aussi, pour des précisions, voir le chapitre 5 de la référence [1].
Les codes de Huffman utilisés pour chaque alphabet dans le format "deflate" ont deux règles supplémentaires :
* Tous les codes d'une longueur binaire données ont des valeurs lexicographiques consécutives, dans le même ordre que les symboles qu'ils représentent ;
* Les codes lexicographiquement plus courts précèdent les codes plus longs.
On peut recoder l'exemple précédent pour suivre cette règle comme suit, en supposant que l'ordre de l'alphabet est ABCD :
Symbole |
Code |
A |
10 |
B |
0 |
C |
110 |
D |
111 |
C'est-à-dire que 0 précède 10 qui précède 11x, et 110 et 111 sont lexicographiquement consécutifs.
Cette règle étant donnée, on peut définir le code de Huffman pour un alphabet juste en donnant les longueurs binaires des codes pour chaque symbole de l'alphabet dans l'ordre ; c'est suffisant pour déterminer les codes réels. Dans notre exemple, le code est complètement défini par la séquence des longueurs binaires (2, 1, 3, 3). L'algorithme suivant génère les codes comme des entiers, destinés à être lus à partir du bit de plus fort poids. Les longueurs de code sont initialement dans tree[I].Len ; les codes sont produits dans tree[I].Code.
1) Compter le nombre de codes pour chaque longueur de code. Soit bl_count[N] le nombre de codes de longueur N, N ≥ 1.
2) Trouver la valeur numérique du plus petit code pour chaque longueur de code :
code = 0;
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}
3) Allouer des valeurs numériques à tous les codes, en utilisant des valeurs consécutives pour tous les codes de même longueur avec les valeurs de base déterminées à l'étape 2. Les codes qui ne sont jamais utilisés (qui ont une longueur binaire de zéro) ne doivent pas se voir allouer de valeur.
for (n = 0; n <= max_code; n++) {
len = tree[n].Len;
if (len != 0) {
tree[n].Code = next_code[len];
next_code[len]++;
}
}
Exemple :
Considérons l'alphabet ABCDEFGH, avec les longueurs binaires (3, 3, 3, 3, 3, 2, 4, 4). Après l'étape 1, nous avons :
N |
bl_count[N] |
2 |
1 |
3 |
5 |
4 |
2 |
L'étape 2 calcule des valeurs next_code suivantes :
N |
next_code[N] |
1 |
0 |
2 |
0 |
3 |
2 |
4 |
14 |
L'étape 3 produit les valeurs de code suivantes :
Symbole |
Longueur |
Code |
A |
3 |
010 |
B |
3 |
011 |
C |
3 |
100 |
D |
3 |
101 |
E |
3 |
110 |
F |
2 |
00 |
G |
4 |
1110 |
H |
4 |
1111 |
Chaque bloc de données compressées commence par 3 bits d'en-tête qui contiennent les données suivantes :
premier bit BFINAL
2 bits suivants BTYPE
Noter que les bits d'en-tête ne commencent pas nécessairement à une limite d'octet, car un bloc n'occupe pas nécessairement un nombre entier d'octets.
BFINAL n'est mis à un que si et seulement si c'est le dernier bloc de l'ensemble de données.
BTYPE spécifie comment les données sont compressées, comme suit :
00 – pas de compression
01 – compressées avec des codes de Huffman fixes
10 – compressées avec des codes de Huffman dynamiques
11 - réservé (erreur)
La seule différence entre les deux cas de compression est la façon dont les codes de Huffman sont définis pour les alphabets littéral/longueur et distance.
Dans tous les cas, l'algorithme de décodage pour les données réelles est le suivant :
do
lire l'en-tête de bloc à partir du flux entrant.
si il est mémorisé sans compression
sauter tous les bits restants dans l'octet partiellement traité actuel
lire LEN et NLEN (voir au paragraphe suivant)
copier les octets de données LEN en sortie
autrement
si il est compressé avec des codes de Huffman dynamiques
lire la représentation des arbres de code (voir au paragraphe suivant ci-dessous)
faire une boucle (jusqu'à la reconnaissance du code de fin de bloc)
décoder la valeur littéral/longueur à partir du flux d'entrée
si la valeur est < 256
copier la valeur (octet littéral) en flux de sortie
autrement
si valeur = fin de bloc (256)
rompre la boucle
autrement (valeur = 257..285)
décoder la distance à partir du flux d'entrée
reculer les octets de distance dans le flux de sortie, et copier les octets de longueur à partir de cette position sur le flux de sortie.
fin de boucle tant que ce n'est pas le dernier bloc
Noter qu'une référence de chaîne dupliquée peut se référer à une chaîne d'un bloc précédent ; c'est-à-dire que la distance en arrière peut traverser une ou plusieurs limites de bloc. Cependant, une distance ne peut pas se référer au delà du commencement du flux de sortie. (Une application utilisant un dictionnaire pré-établi peut éliminer une partie du flux de sortie ; une distance peut quand même se référer à cette partie du flux de sortie.) Noter aussi que la chaîne référencée peut chevaucher la position actuelle ; par exemple, si les deux derniers octets décodés ont les valeurs X et Y, une référence de chaîne avec <length = 5, distance = 2> ajoute X,Y,X,Y,X au flux de sortie.
Nous allons maintenant spécifier chaque méthode de compression tout à tour.
Tous les bits d'entrée jusqu'à la limite d'octet suivante sont ignorés. Le reste du bloc comporte les informations suivantes :
0 1 2 3 4...
+----+----+----+----+=====================================+
| LEN | NLEN |... LEN octets de données littérales.|
+----+----+----+----+=====================================+
LEN est le nombre d'octets de données dans le bloc. NLEN est le complément à un de LEN.
Comme noté plus haut, les blocs de données codés dans le format "deflate" consistent en séquences de symboles tirés de trois alphabets conceptuellement distincts : soit des octets littéraux, d'après les valeurs d'octet de l'alphabet (0 à 255), soit des paires <longueur, distance arrière>, où la longueur est tirée de (3 à 258) et la distance est tirée de (1 à 32 768). En fait, l'alphabet littéral et l'alphabet de longueur sont fusionnés en un seul alphabet (0 à 285), où les valeurs 0 à 255 représentent les octets littéraux, la valeur 256 indique la fin de bloc, et les valeurs 257 à 285 représentent des codes de longueur (éventuellement en association avec des bits supplémentaires qui suivent le code de symbole) comme suit :
Code |
Bits sup. |
Longueurs |
Code |
Bits sup. |
Longueurs |
Code |
Bits sup. |
Longueurs |
257 |
0 |
3 |
267 |
1 |
15,16 |
277 |
4 |
67-82 |
258 |
0 |
4 |
268 |
1 |
17,18 |
278 |
4 |
83-98 |
259 |
0 |
5 |
269 |
2 |
19-22 |
279 |
4 |
99-114 |
260 |
0 |
6 |
270 |
2 |
23-26 |
280 |
4 |
115-130 |
261 |
0 |
7 |
271 |
2 |
27-30 |
281 |
5 |
131-162 |
262 |
0 |
8 |
272 |
2 |
31-34 |
282 |
5 |
163-194 |
263 |
0 |
9 |
273 |
3 |
35-42 |
283 |
5 |
195-226 |
264 |
0 |
10 |
274 |
3 |
43-50 |
284 |
5 |
227-257 |
265 |
1 |
11,12 |
275 |
3 |
51-58 |
285 |
0 |
258 |
266 |
1 |
13,14 |
276 |
3 |
59-66 |
Les bits supplémentaires devraient être interprétés comme un entier automatique mémorisé avec le bit de plus fort poids en premier, par exemple, les bits 1110 représentent la valeur 14.
Code |
Bits sup. |
Dist. |
Code |
Bits sup. |
Distance |
Code |
Bits sup. |
Distance |
0 |
0 |
1 |
10 |
4 |
33-48 |
20 |
9 |
1025-1536 |
1 |
0 |
2 |
11 |
4 |
49-64 |
21 |
9 |
1537-2048 |
2 |
0 |
3 |
12 |
5 |
65-96 |
22 |
10 |
2049-3072 |
3 |
0 |
4 |
13 |
5 |
97-128 |
23 |
10 |
3073-4096 |
4 |
1 |
5,6 |
14 |
6 |
129-192 |
24 |
11 |
4097-6144 |
5 |
1 |
7,8 |
15 |
6 |
193-256 |
25 |
11 |
6145-8192 |
6 |
2 |
9-12 |
16 |
7 |
257-384 |
26 |
12 |
8193-12288 |
7 |
2 |
13-16 |
17 |
7 |
385-512 |
27 |
12 |
12289-16384 |
8 |
3 |
17-24 |
18 |
8 |
513-768 |
28 |
13 |
16385-24576 |
9 |
3 |
25-32 |
19 |
8 |
769-1024 |
29 |
13 |
24577-32768 |
Les codes de Huffman pour les deux alphabets sont fixés, et ne sont pas représentés explicitement dans les données. Les longueurs des codes de Huffman pour l'alphabet littéral/longueur sont :
Valeur littérale |
Bits |
Codes |
0 – 143 |
8 |
00110000 à 10111111 |
144 – 255 |
9 |
110010000 à 111111111 |
256 – 279 |
7 |
0000000 à 0010111 |
280 – 287 |
8 |
11000000 à 11000111 |
Les longueurs de code sont suffisantes pour générer les codes réels, comme décrit ci-dessus ; les codes sont données dans le tableau pour que ce soit évident. Les valeurs littéral/longueur 286-287 ne vont en réalité jamais survenir dans les données compressées, mais elles participent à la construction du code.
Les codes de distance 0 à 31 sont représentés par des codes de 5 bits (longueur fixe) avec des bits supplémentaires possibles comme indiqué dans le tableau du paragraphe 3.2.5, ci-dessus. Noter que les codes de distance 30-31 ne vont en réalité jamais survenir dans les données compressées.
Les codes de Huffman pour les deux alphabets apparaissent dans le bloc immédiatement après le bits d'en-tête et avant les données compressées réelle, d'abord le code littéral/longueur et ensuite le code de distance. Chaque code est défini par une séquence de longueurs de code, comme exposé au paragraphe 3.2.2, ci-dessus. Pour une compacité encore supérieure, les séquences de longueur de code elles-mêmes sont compressées en utilisant un code de Huffman. L'alphabet pour les longueurs de code est le suivant :
0 – 15 : Représente les longueurs de code de 0 à 15
16 : Copie 3 à 6 fois la précédente longueur de code. Les 2 bits suivants répètent la longueur(0 = 3, ... , 3 = 6)
Exemple : Codes 8, 16 (+2 bits 11), 16 (+2 bits 10) va se développer en 12 longueurs de code de 8 (1 + 6 + 5)
17 : Répète une longueur de code de 0 pour 3 à 10 fois. (3 bits de longueur)
18 : Répète une longueur de code de 0 pour 11 à 138 fois (7 bits de longueur)
Une longueur de code de 0 indique que le symbole correspondant dans l'alphabet littéral/longueur ou distance ne va pas survenir dans le bloc, et ne devrait pas participer à l'algorithme de construction de code de Huffman donné plus haut. Si un seul code de distance est utilisé, il est codé en utilisant un bit de un, et non pas des bits à zéro ; dans ce cas, il y a une seule longueur de code de un, avec un code inutilisé. Un code de distance de bits à zéro signifie qu'il n'y a pas de codes de distance utilisés du tout (les données sont toutes en littéral).
On peut maintenant définir le format du bloc :
5 bits : HLIT, numéro des codes littéral/longueur - 257 (257 - 286)
5 bits : HDIST, numéro des codes de distance - 1 (1 - 32)
4 bits : HCLEN, numéro des codes de longueur de code - 4 (4 - 19)
(HCLEN + 4) x 3 bits : longueurs de code pour l'alphabet des longueurs de code données juste ci-dessus, dans l'ordre : 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
Ces longueurs de code sont interprétées comme des entiers de 3 bits (0-7) ; comme ci-dessus, une longueur de code de 0 signifie que le symbole correspondant (littéral/longueur ou longueur de code de distance) n'est pas utilisé.
HLIT + 257 : longueurs de code pour l'alphabet littéral/longueur, codé en utilisant le code de Huffman de longueur de code
HDIST + 1 : longueurs de code pour l'alphabet de distance, codé en utilisant le code de Huffman de longueur de code
Les données compressées réelles du bloc, codées en utilisant les codes de Huffman littéral/longueur et distance
Le symbole littéral/longueur 256 (fin des données), codé en utilisant le code de Huffman littéral/longueur
Les codes de répétition de longueur de code peuvent aller de HLIT + 257 aux longueurs de code HDIST + 1. En d'autres termes, toutes les longueurs de code forment une seule séquence de HLIT + HDIST + 258 valeurs.
Un compresseur peut encore limiter les gammes de valeurs spécifiées au paragraphe précédent tout en restant conforme ; par exemple, il peut limiter la gamme des pointeurs arrières à une valeur inférieure à 32 k. De même, un compresseur peut limiter la taille des blocs de telle sorte qu'un bloc compressible tienne en mémoire.
Un décompresseur conforme doit accepter la gamme complète des valeurs possibles définies au paragraphe précédent, et doit accepter des blocs de taille arbitraire.
4. Détails de l'algorithme de compression
Bien que l'intention du présent document soit de définir le format de compression de données "deflate" sans référence à un algorithme de compression particulier, son format est en relation avec les formats de compression produits par LZ77 (Lempel-Ziv 1977, voir la référence [2] ci-dessous) ; comme de nombreuses variantes de LZ77 sont brevetées, il est fortement recommandé que celui qui met en œuvre un compresseur suive l'algorithme général présenté ici, qui est connu pour être libre de tout brevet. Les matériaux de cette section ne font pas partie de la définition de la spécification par eux-mêmes, et un compresseur n'a pas besoin de les respecter pour être conforme.
Le compresseur termine un bloc lorsqu'il détermine que commencer un nouveau bloc avec des arbres frais serait utile, ou quand la taille du bloc remplit la mémoire tampon de bloc du compresseur.
Le compresseur utilise un tableau de hachage de chaînes pour trouver des chaînes dupliquées, en utilisant une fonction de hachage qui fonctionne sur des séquences de 3 octets. À un moment quelconque de la compression, soit XYZ les trois prochains octets d'entrée à examiner (pas nécessairement tous différents, bien sûr). D'abord, le compresseur examine la chaîne de hachage pour XYZ. Si la chaîne est vide, le compresseur écrit simplement X comme octet littéral et avance d'un octet dans les entrées. Si la chaîne de hachage n'est pas vide, ce qui indique que la séquence XYZ (ou, si on n'a pas de chance, trois autres octets avec la même valeur de fonction de hachage) est survenue récemment, le compresseur compare toutes les chaînes sur la chaîne de hachage XYZ avec la séquence réelle de données d'entrée qui commence au point examiné, et choisit la plus longue correspondance.
Le compresseur cherche les chaînes de hachage commençant par les chaînes les plus récentes, pour favoriser les courtes distances et tire donc parti du codage de Huffman. Les chaînes de hachage sont reliées séparément. Il n'y a pas de suppression à partir des chaînes de hachage ; l'algorithme élimine simplement les correspondances qui sont trop vieilles. Pour éviter les pires situations, les très longues chaînes de hachage sont tronquées arbitrairement à une certaine longueur, déterminée par un paramètre temporel.
Pour améliorer la compression globale, le compresseur diffère facultativement le choix des correspondances ("correspondance paresseuse") : après avoir trouvé une correspondance de longueur N, le compresseur cherche une plus longue correspondance commençant au prochain octet d'entrée. Si il trouve une plus longue correspondance, il tronque la correspondance précédente à une longueur de un (produisant ainsi un seul octet littéral) puis émet la plus longue correspondance. Autrement, il émet la correspondance d'origine, et comme décrit ci-dessus, avance de N octets avant de continuer.
Les paramètres temporels contrôlent aussi cette procédure de "correspondance paresseuse". Si le taux de compression est plus important, le compresseur tente une seconde recherche complète sans considération de la longueur de la première correspondance. Dans le cas normal, si la correspondance actuelle est "assez longue", le compresseur réduit la recherche d'une correspondance plus longue, ce qui accélère donc le traitement. Si la vitesse doit être plus importante, le compresseur n'insère de nouvelles chaînes dans le tableau de hachage que lorsque aucune correspondance n'a été trouvée, ou quand la correspondance n'est pas "trop longue". Cela dégrade le taux de compression mais économise du temps dans la mesure où il y a à la fois moins d'insertions et moins de recherches.
[1] Huffman, D. A., "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the Institute of Radio Engineers, septembre 1952, Volume 40, Number 9, p. 1098-1101.
[2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, Vol. 23, No. 3, p. 337-343.
[3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources, available in ftp://ftp.uu.net/pub/archiving/zip/doc/
[4] Gailly, J.-L., and Adler, M., GZIP documentation and sources, available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/
[5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix encoding." Comm. ACM, 7,3 (mars 1964), p. 166-169.
[6] Hirschberg and Lelewer, "Efficient decoding of prefix codes," Comm. ACM, 33,4, avril 1990, p. 449-459.
6. Considérations pour la sécurité
Toute méthode de compression implique la réduction des redondances dans les données. Par conséquent, toute corruption des données aura vraisemblablement des conséquences graves et sera difficile à corriger. D'un autre côté, le texte non compressé sera probablement toujours lisible en dépit de la présence de quelques octets corrompus.
Il est recommandé que les systèmes qui utilisent ce format de données fournissent un moyen de valider l'intégrité des données compressées. Voir la référence [3], par exemple.
Un code source pour une mise en œuvre en langage C d'un compresseur et décompresseur conforme à "deflate" est disponible dans le paquetage zlib à ftp://ftp.uu.net/pub/archiving/zip/zlib/.
Les marques commerciales citées dans ce document sont la propriété de leurs détenteurs respectifs.
Phil Katz a conçu le format deflate. Jean-Loup Gailly et Mark Adler ont écrit le logiciel qui s'y rapporte, décrit dans la présente spécification. Glenn Randers-Pehrson a converti ce document au format RFC et HTML.
L. Peter Deutsch
Aladdin Enterprises
203 Santa Margarita Ave.
Menlo Park, CA 94025
téléphone : (415) 322-0103 (AM only)
fax : (415) 322-1734
mél : <ghost@aladdin.com>
On peut envoyer les questions sur le contenu technique de cette spécification par courriel à :
Jean-Loup Gailly <gzip@prep.ai.mit.edu> and
Mark Adler <madler@alumni.caltech.edu>
Les commentaires rédactionnel sur cette spécification sont à envoyer par courriel à :
L. Peter Deutsch <ghost@aladdin.com> and
Glenn Randers-Pehrson <randeg@alumni.rpi.edu>