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 20 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_1$ et $a_2$, et les remplace par l'arbre formé de $a_1$ et $a_2$ et ayant comme étiquette la somme de l'étiquette de $a_1$ et de l'étiquette de $a_2$.

La figure 21 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 ; 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).

lettre	code
A	0111
B	010
C	10
D	00
E	11
F	0110

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.