Huffman : construire, coder, chiffrer le gain

Les fréquences : $\text{a}:5$, $\text{b}:2$, $\text{r}:2$, $\text{c}:1$, $\text{d}:1$, pour $11$ caractères.

La construction, en extrayant à chaque tour les deux plus petits poids (à poids égal, on prend d'abord la feuille alphabétiquement la plus petite, puis les nœuds par ordre de création) :

file : c(1) d(1) b(2) r(2) a(5)
  fusion c(1) + d(1) -> [cd](2)     file : b(2) r(2) [cd](2) a(5)
  fusion b(2) + r(2) -> [br](4)     file : [cd](2) [br](4) a(5)
  fusion [cd](2) + [br](4) -> (6)   file : a(5) [bcdr](6)
  fusion a(5) + [bcdr](6) -> (11)   file : [abcdr](11)

Les mots de code : $\text{a}\to 0$, $\text{c}\to 100$, $\text{d}\to 101$, $\text{b}\to 110$, $\text{r}\to 111$.

Le codage de abracadabra :

0 110 111 0 100 0 101 0 110 111 0   =  01101110100010101101110   (23 bits)

Le coût, par la formule ${\sum }_c{f}_c|\mathrm{code}(c)|$ : $5\times 1+2\times 3+2\times 3+1\times 3+1\times 3=23$ bits. Le compte des bits écrits le confirme.

Les comparaisons.

Huffman est à $2,5\%$ de la borne théorique — il ne peut pas faire beaucoup mieux, et aucun code caractère par caractère ne le peut.

Non, l'arbre n'est pas unique. Une autre règle de départage (nouveaux nœuds insérés avant les feuilles de même poids) donne $\text{a}\to 0$, $\text{b}\to 10$, $\text{r}\to 111$, $\text{c}\to 1101$, $\text{d}\to 1100$ — un profil de longueurs différent : $1,2,3,4,4$ au lieu de $1,3,3,3,3$. Et pourtant :

$$5\times 1+2\times 2+2\times 3+1\times 4+1\times 4=23.$$

Même coût, à l'unité près. C'est un résultat général : Huffman produit un code optimal, et l'optimum est unique en valeur, jamais en forme. On ne teste donc pas une mise en œuvre de Huffman en comparant l'arbre à un arbre attendu — on la teste en comparant le coût total, et en vérifiant que le code est préfixe.