Le codage de Huffman est un procédé très utilisé en compression de données. Il sert à encoder un texte en binaire, en utilisant pour chaque lettre un nombre de bits dépendant du nombre de fois où la lettre est présente : plus la lettre apparaît, plus le nombre de bits est petit. Ainsi, le nombre total de bits utilisés pour encoder le texte est réduit par rapport à un codage ASCII standard qui utilise huit bits pour chaque lettre.
Quand il s’agit de transmettre de l’information sur un canal non bruité, l’objectif prioritaire est de minimiser la taille de la représentation de l’information : c’est le problème de la compression de données. Le code de Huffman (1952) est un code de longueur variable optimal, c’est-à-dire tel que la longueur moyenne d’un texte codé soit minimale. On observe ainsi des réductions de taille de l’ordre de 20 à 90%.
Le code binaire associé à chaque lettre est défini par un arbre binaire. Les feuilles de l’arbre correspondent aux lettres de l’alphabet. Les nœuds interne ne contiennent pas d’information. Le chemin emprunté pour atteindre une feuille depuis la racine définit le code de la lettre sur cette feuille : à gauche 0, à droite 1. Par exemple :
Arbre de Huffman
Lorsque le texte à encoder est connu, il est possible d’optimiser l’arbre binaire utilisé pour raccourcir les codes des lettres les plus fréquentes. C’est ce que fait l’algorithme de Huffman : il commence par compter dans le texte le nombre d’apparitions de chaque caractère. Par exemple, dans la phrase :
À partir de ces fréquences, l’algorithme initialise un arbre par caractère, avec comme poids le nombre d’apparitions du caractère :
À chaque itération, l’algorithme sélectionne les deux arbres ayant les poids les plus faibles, et les assemble pour former les deux enfants d’un arbre binaire dont le poids est la somme des deux arbres. Lorsque plusieurs arbres sont à égalité pour le poids le plus faible, l’arbre sélectionné parmi eux peut être n’importe lequel. Ainsi, à la première itération, nous pourrions obtenir :
et après quatre itérations de plus :
Lorsqu’il ne reste plus qu’un seul arbre, l’algorithme est terminé.
Voici un exemple de construction de l’arbre de Huffman afin de mieux comprendre le processus. Dans cet exemple nous avons placé les lettres par ordre croissant contrairement à l’exemple précédent :
Algorithme de Huffman
Plus formellement, l’algorithme de Huffman est le suivant :
Codage et décodage
On peut réécrire l’arbre sous la forme d’un tableau. Le codage d’une lettre est lié au chemin parcouru dans l’arbre jusqu’à la lettre voulu. Prenons le tableau suivant :
Ce type de code est dit préfixe, ce qui signifie qu’aucun code n’est le préfixe d’un autre (le code de A est 10 et aucun autre code ne commence par 10, le code de B est 001 et aucun autre code ne commence par 001). Cette propriété permet de séparer les caractères de manière non ambiguë.
Attention, ici tout laisse à croire que la table proposée n’est pas optimale. En effet, il y a 8 caractères, donc en utilisant le binaire, on pourrait utiliser 3 bits pour coder tous les caractères (2^3 = 8 possibilités).
Ici, la somme des bits des lettres encodés est de 2+3+3+4+2+4+4+4 = 26 bits, soit une moyenne de 26/8 = 3.25 bits par caractère. Mais en fait ce qui va compter ce n’est pas la moyenne, mais la moyenne pondérée par la fréquence comme nous allons le voir dans l’exercice en exemple.
En utilisant le tableau, il est possible d’encoder un message (ici le + est une concaténation) :
CACHE = 000 + 10 + 000 + 1111 + 01 = 00010000111101.
Nous avons donc un message de 14 bits au lieu de 5*3=15 bits, ce qui correspond à une réduction de mémoire pour le stockage du texte de (15-14)/15 = 6.6%. Bien qu’en moyenne l’encodage soit plus grand, dans les faits nous avons bien une réduction de l’espace mémoire utilisé !
Exemple
1) On cherche à coder chaque lettre de cet alphabet par une séquence de chiffres binaires.
a) Combien de bits sont nécessaires pour coder chacune des 8 lettres de l’alphabet.
b) Quelle est la longueur en octets d’un message de 1 000 caractères construit sur cet alphabet ?
2) Proposer un code de taille fixe pour chaque caractère de l’alphabet de 8 lettres.
3) On considère maintenant le codage suivant, la longueur du code de chaque caractère étant variable.
a) En utilisant la table précédente, donner le code du message : CACHE.
b) Quel est le message correspondant au code 001101100111001.
4) Dans un texte, chacun des 8 caractères a un nombre d’apparitions différent. Cela est résumé dans le tableau suivant, construit à partir d’un texte de 1 000 caractères.
a) En utilisant le code de taille fixe proposé à la question 2., quelle est la longueur en bits du message contenant les 1 000 caractères énumérés dans le tableau précédent ?
b) En utilisant le code de la question 3., quelle est la longueur du même message en bits.
5) Réaliser l’arbre de Huffman optimisant l’espace mémoire. Refaire la question 3 et 4 avec le nouvel arbre.
Correction de l'exemple
1a – Pour coder les 8 lettres, il faut 3 bits car 23 = 8.
1b – 1000 caractères correspondent à 1000*3 = 3000 bits. On divise par 8 pour avoir le nombre d’octet = 375.
2 – Vu qu’avec 3 bits il y a 8 possibilités, on va affecter chaque possibilité à un caractère comme par exemple :
3a – On l’a vu dans le texte CACHE est codé par 00010000111101.
3b – On lit les bits de gauche à droite, dès que la lecture donne une lettre on l’écrit et on recommence à chercher dans la table le caractère correspondant.
0 ne donne rien, 00 ne donne rien, 001 donne un B. 1 ne donne rien, 10 donne un A, etc. Le mot final est BADGE.
4a – La longueur serait de 1000*3 = 3000 bits.
4b – Pour connaître la longueur avec la table de codage, nous allons multiplier pour chaque caractère sa fréquence par sa longueur d’encodage : 240*2 + 140*3 + 160*3 + 51*4 + 280*2 + 49*4 + 45*4 + 35*4. Soit 2 660 bits avec une réduction de (3000-2660)/3000 = 11% (ce qui n’est vraiment pas terrible…).
5 – Après avoir réaliser la méthode de Huffman, vous obtenez l’arbre suivant :
Au final c’est la table qui était déjà fourni auparavant, donc elle était déjà optimale !
