Exemple d'arbre : code de Huffman

      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%.

L'algorithme opère sur une forêt  , c'est-à-dire une ensemble d'arbres. Ceux-ci sont des arbres étiquetés complets  : tout nud interne (c'est-à-dire qui n'est pas une feuille) a deux fils non-vides (l'arbre de la figure 22 n'est pas complet car les nuds 4 et 7 n'ont qu'un seul fils non-vide).

La forêt initiale est formée d'un arbre à un nud pour chaque lettre du langage-source, dont l'étiquette est la probabilité de cette lettre. La forêt finale est formée d'un unique arbre, qui est l'arbre de décodage du code.

L'algorithme est de type glouton   : il choisit à chaque étape les deux arbres d'étiquettes minimales, soit a₁ et a₂, et les remplace par l'arbre formé de a₁ et a₂ et ayant comme étiquette la somme de l'étiquette de a₁ et de l'étiquette de a₂.

  

Figure 23: Construction d'un code de Huffman

La figure 23 représente les étapes de la construction d'un code de Huffman pour l'alphabet source $\{ \mathtt{A}, \mathtt{B}, \mathtt{C}, \mathtt{D}, \mathtt{E}, \mathtt{F} \}$, avec les probabilités $\mathbf{P}(\mathtt{A}) = 0,10$, $\mathbf{P}(\mathtt{B}) = 0,10$, $\mathbf{P}(\mathtt{C}) = 0,25$, $\mathbf{P}(\mathtt{D}) = 0,15$,$\mathbf{P}(\mathtt{E}) = 0,35$, $\mathbf{P}(\mathtt{F}) = 0,05$.

Le code d'une lettre est alors déterminé en suivant le chemin depuis la racine de l'arbre jusqu'à la feuille associée à cette lettre en concaténant successivement un 0 ou un 1 selon que la branche suivie est à gauche ou à droite. Le codage se réalise facilement à l'aide d'une table associant à chaque lettre son code :

 

lettre code

A 0111

B 010

C 10

D 00

E 11

F 0110

Une fois ce code construit, le décodage se réalise avec un arbre de décodage (figure 7, page ), grâce à la propriété de préfixe des codes de Huffman (voir § 26).

Compte tenu de ces probabilités, le code obtenu a une longueur moyenne de 2,4, alors que l'entropie du langage source est 2,32, qui est légèrement inférieure. On montre que la longueur moyenne d'un code de Huffman peut approcher l'entropie d'aussi près que voulu, à condition de coder non pas des lettres, mais des blocs de lettres de longueur assez grande.