Français
Menu

Qu'est-ce que Codage de Huffman ?

Méthode qui construit, à partir des probabilités des symboles, un code préfixe dont la longueur moyenne de code est la plus petite possible. On construit un arbre en fusionnant de façon répétée les deux symboles (ou nœuds) de plus faibles probabilités en un seul, et l'on attribue 0 et 1 à chaque embranchement pour former les mots de code. Plus un symbole est fréquent, plus son mot de code est court. Il est optimal parmi les codes préfixes qui codent un symbole à la fois, et sa longueur moyenne de code est au moins égale à l'entropie et inférieure à l'entropie + 1 bit. Il est utilisé en combinaison avec d'autres méthodes dans Deflate (ZIP, gzip), JPEG et ailleurs. Huffman l'a publié en 1952.

Nom japonais: ハフマン符号

« Codage de Huffman » apparaît dans 5 questions d'entraînement réparties sur 1 thèmes, dont Bases de la théorie de l'information et du codage.

Domaine: Bases de la théorie de l'information et du codage

Comment le construire

Pour des symboles de probabilités 1/2, 1/4, 1/8 et 1/8, on fusionne d'abord les deux 1/8 en 1/4, puis ce nœud et le 1/4 en 1/2, et enfin ce nœud et le 1/2 restant. En étiquetant par 0 et 1 les branches qui vont de la racine à chaque symbole, on obtient les mots de code 0, 10, 110 et 111, avec une longueur moyenne de code de 1,75 bit, égale à l'entropie. Lorsque chaque probabilité est l'inverse d'une puissance de 2, la longueur moyenne de code coïncide ainsi avec l'entropie.

Les mots de code ne sont pas uniques

Les mots de code changent selon la façon d'attribuer 0 et 1 et selon celle de deux probabilités égales que l'on fusionne en premier. Par exemple, avec les probabilités 0,4 ; 0,2 ; 0,2 ; 0,1 et 0,1, les longueurs de code peuvent être 1, 2, 3, 4, 4 ou 1, 3, 3, 3, 3 ou 2, 2, 2, 3, 3, mais la longueur moyenne de code vaut 2,2 bits dans tous les cas. C'est pourquoi les examens demandent plutôt la longueur moyenne de code que les mots de code eux-mêmes.

Limites et améliorations

Les longueurs de code sont limitées à des nombres entiers de bits : pour une source comportant un symbole de probabilité proche de 1, l'écart avec l'entropie devient donc grand. Coder des symboles binaires un par un demande 1 bit par symbole, quelle que soit leur dissymétrie. Coder les symboles par groupes, ou utiliser une méthode qui ne se limite pas à des bits entiers, comme le codage arithmétique, rapproche la longueur de l'entropie.

S'entraîner : questions sur Codage de Huffman

Une source émet les symboles A, B, C et D indépendamment avec les probabilités 0,4 ; 0,3 ; 0,2 et 0,1, et on la code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole ?

  1. AEnviron 1,85 bit
  2. B1,9 bit
  3. C2 bits
Afficher la réponse et l'explication

Réponse : B. 1,9 bit

Le codage de Huffman fusionne de façon répétée les deux plus petites probabilités. On fusionne d'abord 0,1 et 0,2 en 0,3, puis 0,3 et 0,3 en 0,6, et enfin 0,6 et 0,4 : les longueurs de code sont donc de 1 bit pour A, de 2 bits pour B et de 3 bits pour C et D. La longueur moyenne de code vaut 0,4 × 1 + 0,3 × 2 + 0,2 × 3 + 0,1 × 3 = 1,9 bit.

Une source émet les symboles A à E indépendamment avec les probabilités 0,3 ; 0,25 ; 0,2 ; 0,15 et 0,1, et on la code avec un code de Huffman. Les mots de code peuvent changer selon celle de deux probabilités égales que l'on choisit en premier, mais pas la longueur moyenne de code. Quelle est la longueur moyenne de code par symbole ?

  1. A2,25 bits
  2. B2,4 bits
  3. C3 bits
Afficher la réponse et l'explication

Réponse : A. 2,25 bits

On fusionne d'abord 0,1 et 0,15 en 0,25, puis 0,2 et 0,25 en 0,45, puis les 0,25 et 0,3 restants en 0,55, et enfin 0,45 et 0,55. Les longueurs de code sont de 2 bits pour A, B et C et de 3 bits pour D et E, et la longueur moyenne de code vaut (0,3 + 0,25 + 0,2) × 2 + (0,15 + 0,1) × 3 = 1,5 + 0,75 = 2,25 bits. Pour une source dont les probabilités sont peu déséquilibrées, un code aux longueurs presque égales est plus court qu'un code aux longueurs étagées comme 1, 2, 3, 4, 4.

Questions fréquentes

Que faut-il pour restaurer des données compressées par un code de Huffman ?

Pour restaurer les données, il faut savoir quel mot de code a été attribué à quel symbole (une table de codage, ou la longueur de code de chaque symbole). Les données compressées transportent donc leur table de codage ou utilisent une table convenue à l'avance. Deflate n'envoie que les longueurs de code, et le récepteur reconstruit les mots de code selon la même règle (codes de Huffman canoniques).

Un code de Huffman peut-il réduire n'importe quelles données ?

Non. Si les probabilités des symboles ne sont pas dissymétriques, les données ne se réduisent presque pas. Par exemple, dans des données où les 256 valeurs d'octet sont équiprobables, chaque mot de code fait 8 bits, et la table de codage rend le résultat légèrement plus gros.

« Codage de Huffman » dans les explications

Questions mentionnant « Codage de Huffman » (5)

  1. Une source émet les symboles A, B, C et D indépendamment avec les probabilités 0,4 ; 0,3 ; 0,2 et 0,1, et on la code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole ?
  2. Une source émet les symboles A à E indépendamment avec les probabilités 0,3 ; 0,25 ; 0,2 ; 0,15 et 0,1, et on la code avec un code de Huffman. Les mots de code peuvent changer selon celle de deux probabilités égales que l'on choisit en premier, mais pas la longueur moyenne de code. Quelle est la longueur moyenne de code par symbole ?
  3. Une source émet les symboles A, B et C indépendamment avec les probabilités 0,6 ; 0,3 et 0,1, et son entropie vaut environ 1,30 bit. Quelle valeur est la plus proche de l'efficacité (entropie ÷ longueur moyenne de code) lorsque cette source est codée avec un code de Huffman ?
  4. Une source binaire émet 0 avec la probabilité 0,8 et 1 avec la probabilité 0,2, indépendamment. On regroupe les symboles deux par deux, on traite chacun des quatre couples 00, 01, 10 et 11 comme un seul symbole, et on les code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole d'origine ?
  5. Quelle description de l'idée de la méthode LZ77, utilisée dans ZIP, gzip et des outils similaires, est correcte ?

Termes associés

Longueur moyenne de code Entropie de l'information Compression sans perte Bit de parité Canal binaire symétrique Codage par plages (RLE) Code de Hamming Code préfixe Compression avec perte Correction d'erreurs directe (FEC)

Retour au glossaire