Comment fonctionne vraiment la compression de fichiers : Huffman Coding, LZ77 et DEFLATE expliqués

Tout développeur a travaillé avec des fichiers compressés. Vous dézippez un paquet, servez une réponse encodée en gzip, ou exportez un PNG — et la compression opère en coulisses. Mais la question que la plupart des tutoriels esquivent est : pourquoi ça marche ? Pourquoi peut-on prendre un fichier texte de 500 Ko et le réduire à 180 Ko sans perdre un seul octet, mais ne peut-on pas comprimer davantage un fichier ZIP ?

La réponse réside dans la théorie de l'information et une poignée d'algorithmes élégants. Cet article parcourt la mécanique réelle : de l'entropie de Shannon aux arbres de Huffman, en passant par le format DEFLATE qui sous-tend ZIP, gzip et PNG.

Pourquoi les fichiers sont compressibles

Les fichiers sont compressibles parce qu'ils contiennent de la redondance — des motifs, des répétitions et des séquences prévisibles qui transportent moins d'information que leur nombre brut d'octets ne le suggère.

Prenons un exemple simple. La chaîne AAAAAAAAAA (dix A) occupe 10 octets en ASCII. Mais le contenu informationnel est trivial : vous pourriez la décrire parfaitement comme « dix A ». Un algorithme de compression fait exactement cela — il remplace des données verbeuses et redondantes par une description plus courte.

Les fichiers réels regorgent de ce type de redondance :

• Le texte en français réutilise sans cesse des mots courants et des combinaisons de lettres. « que », « tion », « ment » apparaissent bien plus souvent que « xqz ».
• Le code source a une structure profondément répétitive : function, return, const, des niveaux d'indentation, des lignes vides.
• Les images bitmap contiennent de longues séquences horizontales de pixels identiques ou presque identiques — surtout dans les zones de couleur unie.
• Les fichiers de journaux répètent des horodatages, des noms d'hôtes et des codes d'état des milliers de fois.

Plus les données sont redondantes, plus elles sont compressibles. Moins elles sont redondantes — plus elles sont aléatoires — plus il devient difficile de les comprimer.

L'entropie : la limite absolue de la compression

Le papier de Claude Shannon de 1948, A Mathematical Theory of Communication, a introduit une façon précise de mesurer le contenu informationnel : l'entropie, mesurée en bits.

L'entropie de Shannon répond à la question : de combien de bits avez-vous réellement besoin, en moyenne, pour représenter un symbole de cette source de données ?

La formule pour une source avec des symboles s₁, s₂, ..., sₙ et des probabilités p₁, p₂, ..., pₙ est :

H = -Σ pᵢ × log₂(pᵢ)

Voici ce que cela signifie en pratique. Supposons que vous ayez un fichier contenant uniquement deux caractères : A (apparaissant 90 % du temps) et B (apparaissant 10 % du temps).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 bit par symbole

Un encodage naïf utilise 1 bit par symbole (0 pour A, 1 pour B). Mais l'entropie indique que le minimum théorique est de 0,469 bit par symbole — moins de la moitié. Un bon algorithme de compression s'approche de cette limite.

Considérons maintenant un fichier vraiment aléatoire où chaque valeur d'octet (0–255) apparaît avec une probabilité égale (1/256 chacune) :

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 bits par octet

Huit bits par octet — entropie maximale. Il n'y a aucune redondance à exploiter. C'est pourquoi vous ne pouvez pas comprimer davantage un fichier ZIP : il est déjà proche de l'entropie maximale. Chaque bit transporte de l'information ; il ne reste aucun motif à éliminer.

Le codage par longueur d'exécution : la forme la plus simple

Avant d'aborder les algorithmes plus complexes, le codage par longueur d'exécution (RLE) illustre clairement l'idée centrale.

Le RLE remplace une suite de symboles répétés par un compteur et le symbole :

Original :  AAABBBBBCCDDDDDD
RLE :       3A 5B 2C 6D

Original : 16 caractères. Encodé : 8 caractères. Réduction de 50 %.

Le RLE est utilisé dans la transmission par fax (CCITT Groupe 3/4), les fichiers BMP et comme sous-étape dans des formats plus complexes. Sa faiblesse est évidente : il se comporte mal avec des données sans longues séquences répétées. La chaîne ABABABAB n'a aucune séquence, donc le RLE la rend plus grande en ajoutant des compteurs de 1 partout.

Cette faiblesse est précisément ce qui pousse vers des approches plus sophistiquées.

Huffman Coding : des codes plus courts pour les symboles fréquents

En ASCII standard, chaque caractère reçoit 8 bits quelle que soit sa fréquence d'apparition. Le codage de Huffman rompt cette hypothèse. Les symboles fréquents reçoivent des codes plus courts ; les symboles rares reçoivent des codes plus longs. La longueur moyenne des codes diminue et le fichier rétrécit.

Construire un arbre de Huffman

Prenons la chaîne AABBBCCCC (9 caractères). Comptons les fréquences :

Étape 1. Placez chaque symbole dans un nœud feuille pondéré par sa fréquence.

[A:2]  [B:3]  [C:4]

Étape 2. Fusionnez répétitivement les deux nœuds de moindre poids en un nœud parent dont le poids est leur somme, jusqu'à ce qu'il ne reste qu'un seul arbre.

Fusionnez [A:2] et [B:3] → parent [AB:5] :

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

Fusionnez [C:4] et [AB:5] → racine [ABC:9] :

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Étape 3. Attribuez des codes en parcourant l'arbre : arête gauche = 0, arête droite = 1.

Calcul des économies de bits

Avec les codes de Huffman, encoder AABBBCCCC coûte :

A × 2 occurrences × 2 bits = 4 bits
B × 3 occurrences × 2 bits = 6 bits
C × 4 occurrences × 1 bit  = 4 bits
Total = 14 bits

Avec l'ASCII fixe à 8 bits :

9 caractères × 8 bits = 72 bits

14 bits contre 72 bits — une réduction de 81 % sur cet exemple jouet. Les gains réels sont moindres, mais le principe tient. Le texte en français se comprime typiquement à 4–5 bits par caractère avec Huffman seul, contre 8 au départ.

L'idée clé : les codes de Huffman sont sans préfixe. Aucun code n'est un préfixe d'un autre, ce qui signifie qu'un décodeur peut reconstruire sans ambiguïté le flux original sans séparateurs. La structure de l'arbre elle-même est stockée dans l'en-tête du fichier compressé afin que le décodeur puisse la reconstruire.

LZ77 et LZ78 : exploiter les séquences répétées

Le codage de Huffman travaille sur les fréquences individuelles des symboles. Mais il passe à côté d'une classe plus large de redondance : les séquences répétées. Le mot « function » dans le code source représente 8 octets à chaque apparition. Si vous pouviez remplacer la deuxième occurrence et les suivantes par un pointeur vers la première, vous économiseriez considérablement.

C'est exactement ce qu'Abraham Lempel et Jacob Ziv ont décrit dans leurs papiers de 1977 et 1978, donnant naissance à LZ77 et LZ78.

LZ77 : compression par fenêtre glissante

LZ77 maintient une fenêtre glissante — un tampon de données vues récemment. Au fur et à mesure que l'encodeur traite de nouvelles données, il regarde en arrière dans la fenêtre pour trouver la plus longue correspondance avec ce qui vient ensuite. S'il en trouve une, il émet une référence arrière (décalage, longueur) au lieu des octets littéraux.

Considérons l'encodage de la chaîne :

abcabc

Traitement de abc : pas d'historique préalable, on émet les littéraux a, b, c.

Traitement du second abc : l'encodeur regarde en arrière et trouve abc débutant 3 positions plus tôt, de longueur 3. Il émet la référence arrière (décalage=3, longueur=3) au lieu de trois octets littéraux.

Le décodeur, en voyant (3, 3), recule de 3 positions dans son tampon de sortie et copie 3 octets — reconstruisant abc parfaitement.

Dans une implémentation réelle, la recherche de correspondances est limitée par la taille de la fenêtre (gzip utilise une fenêtre de 32 Ko). Une fenêtre plus longue trouve plus de correspondances mais coûte davantage en mémoire et en temps de recherche.

La référence arrière (décalage, longueur) fait typiquement 2–3 octets. Remplacer une séquence répétée de 10 octets par une référence de 2 octets économise donc 8 octets. Plus la correspondance est longue, meilleur est le ratio.

LZ78 et LZW

LZ78 construit un dictionnaire explicite des motifs rencontrés plutôt que d'utiliser une fenêtre glissante. LZW (Lempel-Ziv-Welch), un dérivé, est devenu célèbre en tant qu'algorithme derrière la compression GIF et l'utilitaire compress d'Unix. LZW encode les motifs comme des indices de dictionnaire uniques, faisant croître le dictionnaire à la volée pendant l'encodage et le décodage.

DEFLATE : LZ77 plus Huffman Coding

DEFLATE, défini dans la RFC 1951, combine LZ77 et le codage de Huffman en séquence :

1. Passe LZ77 : Remplace les séquences répétées par des références arrière (décalage, longueur). La sortie est un flux de littéraux et de références arrière.
2. Passe Huffman : Applique le codage de Huffman à ce flux. Les littéraux fréquents reçoivent des codes courts ; les valeurs de référence arrière rares reçoivent des codes plus longs.

Les deux techniques s'attaquent à différents types de redondance. LZ77 élimine les répétitions longue portée. Le codage de Huffman élimine ensuite la redondance basée sur la fréquence dans ce qui reste. Ensemble, ils atteignent des taux de compression qu'aucun des deux seuls ne pourrait atteindre.

Les données DEFLATE sont organisées en blocs. Chaque bloc peut utiliser l'un de trois modes :

• Sans compression — pour les données où la compression expandrait la sortie (données déjà aléatoires)
• Codes Huffman fixes — une table de codes préétablie, économisant la surcharge du stockage d'un arbre personnalisé
• Codes Huffman dynamiques — un arbre personnalisé optimisé pour ce bloc spécifique, stocké dans l'en-tête du bloc

Le mode dynamique est utilisé pour la plupart des données compressibles. L'encodeur analyse le bloc, construit un arbre Huffman optimal, le stocke au début du bloc, puis encode les données en utilisant cet arbre.

Où DEFLATE vit dans les formats de fichiers réels

ZIP

Les fichiers ZIP stockent chaque entrée indépendamment avec son propre flux compressé DEFLATE. Cette compression par entrée signifie que vous pouvez extraire un seul fichier d'un ZIP sans décompresser toute l'archive. Le format ZIP supporte également un mode « stocké » (sans compression) pour les fichiers déjà compressés.

gzip

gzip enveloppe un seul flux DEFLATE avec un en-tête (nombre magique, OS, heure de modification) et une somme de contrôle CRC32. C'est le format de compression standard pour HTTP Content-Encoding: gzip et pour les archives .tar.gz. L'extension .gz est toujours un seul flux DEFLATE.

PNG

PNG utilise DEFLATE (via zlib) pour comprimer ses données de pixels. Avant la compression, PNG applique une étape de filtrage : il transforme chaque ligne de pixels en différences par rapport à une prédiction (codage delta). Cela augmente considérablement les séquences et répétitions que LZ77 peut exploiter, améliorant sensiblement la compression. Pour les captures d'écran et les diagrammes typiques, PNG se comprime à 20–50 % de la taille des données de pixels brutes. Les outils de compression d'images qui exportent en PNG reposent sur cette chaîne de traitement.

zlib

zlib est un format d'enrobage autour de DEFLATE — il ajoute un en-tête de deux octets et une somme de contrôle Adler-32. Les flux PDF utilisent zlib/DEFLATE pour comprimer le contenu embarqué (la compression PDF réduit la taille du fichier en recompressant ou en supprimant ces flux). HTTP, WebSockets et de nombreux protocoles réseau utilisent également zlib.

JPEG : une approche différente

Il vaut la peine de s'arrêter ici car JPEG utilise une stratégie de compression totalement différente — une qui perd délibérément des données.

JPEG applique une Transformée en Cosinus Discrète (DCT) à des blocs de 8×8 pixels. La DCT convertit les valeurs de pixels en composantes de fréquence (semblable à une transformée de Fourier). Les composantes haute fréquence — les détails fins — sont ensuite quantifiées de manière agressive (arrondies à des valeurs plus grossières ou abandonnées entièrement). Les coefficients restants sont encodés avec le codage de Huffman, mais c'est l'étape de quantification avec perte qui rend JPEG bien plus petit que PNG pour les photographies.

La contrepartie : JPEG ne peut pas reconstruire parfaitement les pixels originaux. PNG le peut. C'est la distinction sans perte/avec perte explorée en profondeur dans notre article sur la conversion de fichiers avec et sans perte.

Pour une photographie, un JPEG à la qualité 80 peut utiliser 10 % des octets qu'un PNG sans perte nécessiterait. Pour une capture d'écran avec des couleurs unies et des bords nets, PNG gagne généralement parce que les artefacts DCT sont visibles et que DEFLATE comprime très bien les régions plates.

Pourquoi vous ne pouvez pas comprimer davantage un fichier ZIP

C'est une source fréquente de confusion. Si la compression fonctionne en trouvant des motifs, pourquoi comprimer un fichier déjà compressé ne donne-t-il presque rien ?

Parce que DEFLATE fait correctement son travail. Un flux DEFLATE bien compressé a l'air statistiquement aléatoire — par conception. Les références arrière et les codes Huffman éliminent les motifs prévisibles. Ce qui reste est proche de la limite d'entropie des données.

Faites passer un second compresseur dessus et il ne trouvera ni séquences (LZ77 ne trouve pas de longues correspondances) ni biais de fréquence (Huffman voit une distribution de symboles presque uniforme). L'entropie est déjà à 7,9+ bits par octet. Il n'y a plus rien à exploiter.

C'est aussi pourquoi vous ne devriez jamais comprimer des médias déjà compressés. Emballer un JPEG dans un ZIP vous coûte la surcharge du ZIP sans aucun bénéfice en taille. La même chose s'applique aux MP3, MP4, HEIC — tous sont des formats compressés qui sont déjà proches de leur plafond d'entropie.

Comparaison des algorithmes

Tout assembler

La chaîne allant des données brutes aux octets compressés ressemble à ceci pour un fichier compressé en gzip :

1. Entrée : Flux d'octets bruts (par ex. un fichier texte)
2. LZ77 : Scanne les références arrière avec une fenêtre glissante de 32 Ko, produisant un flux de littéraux et de paires (décalage, longueur)
3. Codage de Huffman : Construit deux arbres — un pour les littéraux/longueurs, un pour les décalages — et encode la sortie de LZ77
4. Blocs DEFLATE : Empaquette les arbres Huffman et les données encodées dans un ou plusieurs blocs
5. Enveloppe gzip : Préfixe l'en-tête gzip, ajoute le CRC32 et la taille du fichier original
6. Sortie : Fichier .gz, typiquement 30–70 % plus petit pour une entrée compressible

La décompression s'effectue strictement en sens inverse : analyse de l'en-tête gzip, lecture et reconstruction des arbres Huffman depuis les en-têtes de blocs, décodage du flux Huffman vers les jetons LZ77, application des références arrière pour reconstruire le flux d'octets original. La décompression est toujours plus rapide que la compression car le travail difficile (recherche des meilleures correspondances, construction des arbres optimaux) n'est effectué qu'une seule fois.

Points clés à retenir

• Les fichiers sont compressibles parce qu'ils contiennent de la redondance — des motifs répétés et des fréquences de symboles biaisées.
• L'entropie de Shannon fixe le plancher absolu : les données vraiment aléatoires ne peuvent pas être compressées car chaque bit transporte déjà de l'information.
• RLE gère la répétition grossièrement. Le codage de Huffman gère le biais de fréquence élégamment. LZ77 gère la répétition de séquences longue portée.
• DEFLATE enchaîne LZ77 et Huffman en séquence, ce qui lui permet de surpasser l'un ou l'autre algorithme seul. C'est le moteur dans ZIP, gzip, PNG et les flux PDF compressés avec zlib.
• JPEG adopte une approche fondamentalement différente : quantification DCT avec perte suivie de Huffman sans perte, échangeant la précision des pixels contre une réduction de taille spectaculaire.
• Comprimer un fichier compressé ne sert à rien car une bonne compression produit une sortie d'entropie quasi maximale.

Comprendre ces algorithmes est utile quand vous choisissez un format, diagnostiquez des fichiers anormalement volumineux ou déboguez un pipeline de compression. La prochaine fois que vous utiliserez la compression PDF, extrairez un fichier ZIP ou exporterez un PNG pour la compression d'images, vous saurez exactement ce que le logiciel fait à vos bits.