Mesurer l'information

Le codage de Huffman

Coder les symboles fréquents sur peu de bits

Dans un texte français, le « e » est bien plus fréquent que le « z ». Pourquoi les coder sur le même nombre de bits ? Le codage de Huffman exploite cette idée simple : donner des codes courts aux symboles fréquents et des codes longs aux symboles rares. En moyenne, le message occupe moins de bits.

Construire l'arbre de Huffman

On construit un arbre binaire de bas en haut. On part des symboles avec leur fréquence, et on fusionne à chaque étape les deux plus petites fréquences en un nœud, jusqu'à obtenir un seul arbre.

Frequences : A=5  B=2  C=1  D=1

etape 1 : fusionner C(1) et D(1) -> noeud (2)
etape 2 : fusionner B(2) et (2)   -> noeud (4)
etape 3 : fusionner A(5) et (4)   -> racine (9)

arbre obtenu :               (9)
                            /    \
                       A(5)      (4)
                                /    \
                             B(2)    (2)
                                     /   \
                                  C(1)   D(1)

codes (gauche=0, droite=1) :
   A = 0        (1 bit,  car le plus frequent)
   B = 10       (2 bits)
   C = 110      (3 bits)
   D = 111      (3 bits, car le plus rare)

Un code sans ambiguïté

Le génie du procédé : aucun code n'est le début d'un autre (on parle de code préfixe). On peut donc décoder un flux de bits sans séparateur : 0 10 0 110 se lit sans hésitation A, B, A, C. Cette propriété vient directement du fait que les symboles sont aux feuilles de l'arbre.

Le gain

Avec l'exemple ci-dessus, coder A B A C D coûte 1+2+1+3+3 = 10 bits avec Huffman, contre 2 bits fixes par symbole (soit 10 bits aussi ici sur 5 symboles), mais sur un long texte où A domine, l'économie devient importante et s'approche de l'entropie de la source.

Piège classique