Aller au contenu
Encyclopédie informatique Édition 2026

La compression de données

Partie 3 sur 4

Niveau de lecture :
Vidéo de cette partieenviron une minute et demie, avec voix et texte à l’écran

5Le codage de Huffman

En 1952, David Huffman, alors étudiant au Massachusetts Institute of Technology (MIT), a proposé une méthode statistique qui attribue un mot de code binaire aux différents symboles à compresser (des pixels ou des caractères, par exemple). Au lieu de coder chaque lettre sur 8 bits, comme dans le codage ASCII (voir les caractères), il donne aux lettres un nombre de bits variable.

L’idée est celle du télégraphe de Morse : la lettre « e », très fréquente, se code par un seul point, alors que le « q », rare, demande quatre signes. Dans le codage de Huffman, la longueur de chaque mot de code n’est pas identique pour tous les symboles : les symboles les plus fréquents (ceux qui apparaissent le plus souvent) sont codés avec de petits mots de code, tandis que les symboles les plus rares reçoivent de plus longs codes binaires. On parle de codage à longueur variable (en anglais VLC, pour variable-length code). Il est dit préfixé parce qu’aucun code n’est le début (le préfixe) d’un autre : c’est ce qui permet de lire une suite de bits sans séparateur et de savoir où chaque lettre se termine. Ainsi, la suite finale de mots codés est en moyenne plus courte qu’avec un codage de taille constante.

5.1La construction de l’arbre

Le codeur de Huffman crée un arbre ordonné à partir de tous les symboles et de leur fréquence d’apparition. Les branches sont construites de façon récursive (en répétant la même opération), en partant des symboles les moins fréquents. La recette tient en cinq étapes :

  1. on compte les fréquences d’apparition de chaque symbole et on les classe par ordre croissant ;
  2. on retire les deux symboles de plus faible fréquence de la liste ;
  3. on les rattache à un nœud (un point de l’arbre) dont le poids vaut la somme de leurs fréquences ; on affecte la valeur 1 à l’une des branches et 0 à l’autre (on donne souvent la branche 1 au symbole de plus faible poids, mais la convention inverse est tout aussi correcte tant qu’elle est constante) ;
  4. on replace ce nœud dans la liste comme un nouveau symbole, et on recommence ;
  5. on s’arrête quand il ne reste qu’un seul nœud, appelé la racine.

Le code de chaque symbole correspond à la suite des valeurs de branche rencontrées le long du chemin entre la racine et ce symbole (ou, dans certaines présentations, entre le symbole et la racine, lu à l’envers). Plus un symbole est profond dans l’arbre, plus son mot de code est long.

5.2Un exemple pas à pas

On propose souvent la phrase « COMMENT_CA_MARCHE », où le trait bas figure l’espace. Comptons ses lettres : C apparaît 3 fois (dans COMMENT, CA et MARCHE), M 3 fois (deux dans COMMENT, une dans MARCHE), A 2 fois, E 2 fois, l’espace 2 fois, puis O, N, T, R et H une fois chacune, soit 17 caractères. Certains tableaux de fréquences donnent un 2 pour la lettre C, ce qui est une erreur de comptage (3 + 3 + 2 + 2 + 2 + 5 = 17). L’exemple reste excellent, mais nous allons en traiter un plus petit, afin de montrer chaque étape.

Soit le mot « ABRACADABRA », de 11 lettres. Les fréquences sont : A = 5, B = 2, R = 2, C = 1, D = 1. On applique la recette :

  1. C (1) et D (1) sont les plus rares : on les réunit en un nœud de poids 2 ;
  2. il reste A (5), B (2), R (2) et ce nœud (2) : on réunit B et ce nœud en un nœud de poids 4 ;
  3. il reste A (5), R (2) et ce nœud (4) : on réunit R et ce nœud en un nœud de poids 6 ;
  4. il reste A (5) et ce nœud (6) : on les réunit sous la racine, de poids 11.
ARBRE DE HUFFMAN POUR « ABRACADABRA » (11 LETTRES) racine 11 A : 5 6 0 1 R : 2 4 0 1 B : 2 2 0 1 C : 1 D : 1 0 1 Codes obtenus A → 0 (5 fois) R → 10 (2 fois) B → 110 (2 fois) C → 1110 (1 fois) D → 1111 (1 fois) Total : 5×1 + 2×2 + 2×3 + 4 + 4 = 23 bits contre 33 bits à 3 bits par lettre et 88 bits à 8 bits par lettre. La lettre la plus fréquente reçoit le code le plus court ; aucun code n’est le début d’un autre.
Figure 2. L’arbre de Huffman de « ABRACADABRA ». La lettre la plus fréquente est à une seule marche de la racine : son code est le plus court.

En lisant l’arbre de la racine vers chaque lettre, on obtient les codes : A = 0, R = 10, B = 110, C = 1110, D = 1111. Le mot ABRACADABRA s’écrit donc 0 110 10 0 1110 0 1111 0 110 10 0, soit 23 bits. Les mêmes 11 lettres en ASCII coûtent 88 bits, et même avec un code de longueur fixe adapté à cinq symboles (3 bits chacun) il en faudrait 33. Le gain par rapport au code fixe est d’environ 30 %.

On vérifie que le code est bien préfixé : 0 n’est le début d’aucun autre code (tous les autres commencent par 1) ; 10 n’est le début ni de 110, ni de 1110, ni de 1111, qui commencent par 11 ; et ainsi de suite. Pour décoder 0 1 1 0 1 0 ..., on lit bit après bit : 0 donne A ; on lit 1, 1, 0 : c’est B ; on lit 1, 0 : c’est R. Aucune ambiguïté, sans séparateur.

5.3Forces et limites

Les compressions fondées sur ce codage donnent de bons taux, en particulier pour les images monochromes, comme les fax. Le codage de Huffman (combiné à du RLE : il compte d’abord les longueurs de plages, puis donne des codes courts aux longueurs fréquentes) est notamment utilisé dans les recommandations T4 et T5 de l’ITU-T, c’est-à-dire de l’Union internationale des télécommunications, qui décrivent la transmission des télécopies. On le retrouve aussi à l’intérieur de JPEG et de MP3 (partie 7).

Ses limites tiennent à trois points. Il faut connaître les fréquences : soit on les calcule avant en lisant tout le fichier (méthode semi-adaptative), soit on utilise une variante qui met l’arbre à jour au fil des données. Il faut transmettre l’arbre avec les données, pour que le décodeur puisse le reconstruire, ce qui coûte quelques octets. Enfin, il code chaque symbole sur un nombre entier de bits (un symbole très fréquent ne descend jamais sous un bit), ce qui l’éloigne légèrement de la limite théorique de l’entropie. Les méthodes plus récentes dites de codage arithmétique et de codage ANS (asymmetric numeral systems, « systèmes de numération asymétriques », vers 2009) lèvent cette limite, et équipent aujourd’hui des compresseurs comme zstd.

Pour s’exercer

Exercice 4 : construire un arbre de Huffman

Fréquences : E = 4, T = 2, S = 1, I = 1. Construisez l’arbre et donnez un jeu de codes. Combien de bits pour les huit lettres ?

Voir la réponse

On réunit S (1) et I (1) en un nœud de poids 2 ; puis T (2) et ce nœud (2) en un nœud de poids 4 ; puis E (4) et ce nœud (4) sous la racine. Codes possibles : E = 0, T = 10, S = 110, I = 111. Total : 4×1 + 2×2 + 1×3 + 1×3 = 14 bits, contre 16 bits à 2 bits par lettre et 64 bits en ASCII. Le jeu de codes n’est pas unique : on peut échanger 0 et 1, mais les longueurs restent les mêmes.

Exercice 5 : vérifier un code préfixé

Les codes A = 0, B = 01, C = 11 forment-ils un code préfixé ? Que se passe-t-il à la lecture de 011 ?

Voir la réponse

Non : 0 (A) est le début de 01 (B). La suite 011 se lit « A puis C » (0, 11) ou « B puis 1 » : il y a ambiguïté, et le décodage est impossible sans séparateur. C’est précisément ce que la propriété de préfixe évite.

6Les méthodes à dictionnaire : LZ77, LZ78 et LZW

Huffman exploite la fréquence des lettres. Mais les textes répètent aussi des suites de lettres : des mots, des expressions, des balises. Les méthodes à dictionnaire remplacent ces suites par un numéro ou un renvoi. Elles sont le fruit des travaux de deux chercheurs israéliens, Abraham Lempel et Jacob Ziv.

6.1Un peu d’histoire

Lempel et Ziv ont créé en 1977 (d’où son nom) le compresseur LZ77. Il fut d’abord employé pour l’archivage : les formats ZIP, ARJ et LHA, très répandus à l’époque des disquettes, descendent de lui. En 1978, ils proposent LZ78, qui change de principe : au lieu de renvoyer vers un passage déjà lu, il construit un dictionnaire explicite. On présente parfois LZ78 comme « spécialisé dans la compression d’images » ; en réalité c’est un compresseur général, qui s’applique à tout type de données binaires.

En 1984, Terry Welch, ingénieur de la société Sperry (devenue ensuite Unisys), le modifia pour l’utiliser dans des contrôleurs de disques durs ; son initiale vint se rajouter à l’abréviation LZ pour donner LZW. C’est un des algorithmes les plus populaires de l’histoire de l’informatique, notamment utilisé dans les formats d’image TIFF et GIF.

6.2L’idée de LZW

LZW est un algorithme très rapide, aussi bien en compression qu’en décompression. Il est basé sur la multiplicité des occurrences de séquences de caractères dans la chaîne à encoder : plus une suite revient, plus elle sera économisée. Son principe consiste à substituer des motifs par un code d’affectation (un indice, un numéro), en construisant au fur et à mesure un dictionnaire.

Le dictionnaire est initialisé avec les 256 valeurs de la table ASCII (les 256 octets possibles, voir les caractères). Le fichier à compresser est découpé en chaînes d’octets ; chacune de ces chaînes est comparée au dictionnaire, et ajoutée si elle n’y figure pas encore. On remarque que, pour des images monochromes codées sur un bit par point, cette compression est peu efficace : il faut en effet que les suites aient une longueur suffisante en octets pour qu’un numéro soit plus court que la suite remplacée.

Pendant la compression, l’algorithme parcourt le flot d’informations en le codant ; il cherche la plus longue suite déjà présente dans le dictionnaire, émet son numéro, puis ajoute au dictionnaire cette suite prolongée d’une lettre. Si une chaîne est plus petite que le plus grand mot du dictionnaire, alors elle est transmise telle quelle sous forme de son numéro.

La figure 3 déroule l’algorithme sur un exemple volontairement minuscule : la chaîne « ABABABA », avec un dictionnaire de départ réduit à deux lettres, A = 1 et B = 2 (au lieu de 256).

LZW SUR « ABABABA » : DICTIONNAIRE DE DÉPART A=1, B=2 étape 1 on lit A puis B : « AB » est inconnu on émet 1 (A) ; on ajoute AB = 3 étape 2 on lit B puis A : « BA » est inconnu on émet 2 (B) ; on ajoute BA = 4 étape 3 AB connu, puis « ABA » est inconnu on émet 3 (AB) ; on ajoute ABA = 5 étape 4 AB, puis ABA : tout est connu, fin on émet 5 (ABA) Résultat : 1 2 3 5 — quatre codes au lieu de sept lettres. Le dictionnaire n’est pas envoyé : le décodeur le reconstruit en lisant les codes dans le même ordre. Cas particulier : le code 5 arrive avant d’être défini ; le décodeur le déduit (AB + première lettre de AB = ABA).
Figure 3. LZW sur « ABABABA » : quatre codes au lieu de sept lettres, sans transmettre le dictionnaire.

6.3La décompression : un dictionnaire qui se reconstruit seul

La force de LZW tient à sa décompression. Lors de la décompression, l’algorithme reconstruit le dictionnaire dans le sens inverse ; ce dernier n’a donc pas besoin d’être stocké ni transmis avec les données. Le décodeur part du même dictionnaire initial, lit un numéro, écrit la suite correspondante, et ajoute au dictionnaire la même entrée que l’encodeur avait ajoutée (la suite précédente suivie de la première lettre de la suite courante).

Reprenons l’exemple : on lit 1 : A. On lit 2 : B, et on ajoute AB = 3. On lit 3 : c’est AB, et on ajoute BA = 4. On lit 5 : ce numéro n’existe pas encore ! C’est le cas particulier de LZW : le code est celui de l’entrée que l’encodeur vient de créer. Le décodeur sait qu’elle est formée de la suite précédente (AB) suivie de sa propre première lettre (A) : c’est ABA. On retrouve ABABABA. Cette astuce permet de ne rien transmettre d’autre que les codes.

On lit parfois : « il travaille sur des bits et non sur des octets, il ne dépend donc pas de la manière dont le processeur code les informations ». L’affirmation est approximative : les implémentations réelles lisent des octets, et émettent des codes dont la largeur grandit (9 bits au départ, puis 10, 11, jusqu’à 12 bits pour GIF) à mesure que le dictionnaire se remplit. Quand le dictionnaire est plein (4 096 entrées pour GIF), on le vide et on repart, ou on le fige.

6.4Le brevet de LZW et la naissance de PNG

La méthode de compression LZW a été brevetée par la société Unisys. À partir de 1994, celle-ci a exigé des redevances de la part des éditeurs de logiciels qui écrivaient des fichiers GIF, ce qui a provoqué une vive polémique sur le Web. C’est pour échapper à ce brevet que fut créé, en 1995, le format d’image PNG. On lit parfois que « l’algorithme LZ77, libre de droit, est utilisé dans les images PNG » : c’est juste dans l’esprit (PNG repose sur la famille LZ77, que le brevet ne concernait pas), mais la méthode exacte est Deflate (partie 7), qui ajoute un codage de Huffman. Les brevets sur LZW ont expiré en 2003 aux États-Unis et en 2004 ailleurs : le GIF est devenu libre de redevances. L’épisode reste une leçon de propriété intellectuelle appliquée à l’informatique (voir l’informatique en général).

6.5LZ77 : renvoyer vers ce qu’on vient de lire

LZ77 procède différemment. Au lieu de construire un dictionnaire séparé, il utilise comme dictionnaire les derniers kilooctets déjà lus (une « fenêtre glissante »). Quand il rencontre une suite qui figure dans la fenêtre, il émet un renvoi de la forme « reculez de N caractères et recopiez L caractères ». Dans la phrase « il pleut, il pleut encore », la deuxième occurrence de « il pleut » devient un renvoi : « reculez de 9, recopiez 8 ». Le décodeur, qui reconstruit le texte au fur et à mesure, retrouve la suite exacte. LZ77 n’a pas besoin de stocker de dictionnaire non plus, et se prête bien aux fichiers où des motifs reviennent à courte distance.

Pour s’exercer

Exercice 6 : jouer à LZW

Avec le dictionnaire A = 1, B = 2, compressez « AABAAB » en LZW. Donnez la sortie et les entrées ajoutées.

Voir la réponse

On lit A, puis AA : inconnu → on émet 1 (A), on ajoute AA = 3. On lit A puis AB : inconnu → on émet 1, on ajoute AB = 4. On lit B puis BA : inconnu → on émet 2, on ajoute BA = 5. On lit A puis AA : connu (3) ; puis AAB : inconnu → on émet 3 (AA), on ajoute AAB = 6. Reste B → on émet 2. Sortie : 1 1 2 3 2, soit 5 codes pour 6 lettres. (La petite taille de l’exemple limite le gain.)

Sécurité de l’information

Le coin cyber

C.1Les « bombes » de compression

Une archive peut être construite pour se décompresser en un volume gigantesque à partir de quelques kilooctets, dans le but de saturer le disque ou la mémoire du programme qui l’ouvre : on parle de bombe de décompression. Les antivirus, les serveurs de messagerie et les logiciels qui lisent des fichiers envoyés par des inconnus s’en protègent en limitant la taille obtenue, le nombre de niveaux d’archives imbriquées et le rapport de décompression. Si vous développez un service qui accepte des archives, imposez ces limites.

C.2La taille d’un message compressé peut trahir son contenu

Les méthodes à dictionnaire compressent mieux ce qui se répète. En 2012 et 2013, les attaques nommées CRIME et BREACH ont montré qu’on peut deviner un secret en observant la taille de messages compressés puis chiffrés. Le bon réflexe, pour qui administre un site : ne pas compresser les réponses qui mêlent un secret et du texte choisi par un visiteur, et garder les logiciels à jour.

C.3Réduire le nombre de formats acceptés

Chaque format de fichier pris en charge ajoute un décodeur, donc des erreurs possibles. Un site qui accepte des formats anciens ou rares multiplie les occasions de faille, alors que presque personne ne s’en sert. Le bon réflexe : n’autoriser que les formats dont vous avez besoin, et désactiver les autres dans vos logiciels et vos serveurs.