Le codage de Huffman quand toutes les fréquences sont égales

Mesuré, pour $k$ caractères de fréquence $1$ :

Quand $k$ est une puissance de deux, l'arbre de Huffman est parfaitement équilibré et tous les codes ont la longueur ${\log }_{2}k$ : Huffman ne gagne rien, et ne peut rien gagner. C'est cohérent avec le théorème : le code obtenu est optimal, et l'optimum est ici le code de longueur fixe.

Quand $k$ n'est pas une puissance de deux, Huffman fait mieux qu'un code fixe. Pour $k=5$, il donne trois codes de $2$ bits et deux de $3$, soit $12$ bits pour cinq caractères ($2,4$ bits en moyenne), contre $\lceil {\log }_{2}5\rceil =3$ bits chacun, soit $15$. Un gain de $20\%$ sur des fréquences parfaitement uniformes — là où l'intuition dirait qu'il n'y a rien à prendre.

Ce que la mesure révèle. Huffman n'exploite pas seulement le déséquilibre des fréquences ; il exploite aussi le fait qu'un code de longueur fixe gaspille $\lceil {\log }_{2}k\rceil -{\log }_{2}k$ bits par caractère. L'entropie vaut ${\log }_{2}5=2,32$ bits, Huffman en emploie $2,4$, et le code fixe $3$.

La conséquence pratique. Si l'on doit décider s'il vaut la peine de coder un texte par Huffman, ce n'est pas la longueur du texte qu'il faut regarder, c'est l'écart entre son entropie et $\lceil {\log }_{2}k\rceil$. Sur un texte dont toutes les lettres sont équiprobables et dont l'alphabet compte $256$ symboles, le gain est nul — et le stockage de la table est une perte sèche.