Probleme – Codes préfixes et inégalité de Kraft

1. Le sens direct. Un code préfixe se dessine dans l'arbre binaire complet : le mot de code $w$ est le chemin de la racine à un nœud, et « aucun mot n'est préfixe d'un autre » signifie exactement qu'aucun de ces nœuds n'est ancêtre d'un autre.

Prenons $L={\max }_i{\ell }_i$ et regardons les $2^L$ feuilles de l'arbre complet de profondeur $L$. Le nœud du mot $w_i$, à la profondeur ${\ell }_i$, a exactement $2^{L-{\ell }_i}$ descendants à la profondeur $L$. Comme aucun $w_i$ n'est ancêtre d'un autre, ces ensembles de descendants sont deux à deux disjoints. Ils sont tous inclus dans les $2^L$ feuilles, d'où

$$\sum _{i=1}^k{2}^{L-{\ell }_i}\le 2^L,\text{soit}\sum _{i=1}^k{2}^{-{\ell }_i}\le 1.$$

2. La réciproque, constructive. Trions les longueurs par ordre croissant, ${\ell }_1\le \cdots \le {\ell }_k$. On attribue les mots de code par ordre : $w_1$ est le mot de ${\ell }_1$ zéros ; puis, à chaque étape, $w_i$ est obtenu en lisant $w_{i-1}$ comme un entier binaire, en lui ajoutant $1$, et en complétant à droite par des zéros jusqu'à la longueur ${\ell }_i$.

Cette construction est le code canonique. Elle est préfixe : pour $j<i$, on a $v_i\ge (v_j+1)2^{{\ell }_i-{\ell }_j}$, donc l'entier formé par les ${\ell }_j$ premiers bits de $w_i$ est au moins $v_j+1$, strictement plus grand que $v_j$ — $w_j$ n'est donc pas préfixe de $w_i$. Et comme les longueurs croissent, aucun mot plus long ne peut être préfixe d'un plus court. Elle ne déborde pas : une récurrence immédiate donne pour valeur du $i$-ième mot $v_i={\sum }_{j<i}{2}^{{\ell }_i-{\ell }_j}=2^{{\ell }_i}{\sum }_{j<i}{2}^{-{\ell }_j}\le 2^{{\ell }_i}(1-2^{-{\ell }_i})=2^{{\ell }_i}-1$, donc $w_i$ tient bien sur ${\ell }_i$ bits.

L'intérêt pratique est considérable : un code canonique se transmet en donnant seulement les longueurs, et non l'arbre. C'est ce que fait le format deflate (celui de zip et de png), et c'est ce qui répond à l'avertissement du chapitre sur le coût de la transmission de l'arbre.

3. Les trois profils.

Pour $(1,2,3,3)$ le code canonique donne $0$, $10$, $110$, $111$. Pour $(1,2,3,4,4)$ : $0$, $10$, $110$, $1110$, $1111$.

Quand la somme vaut exactement $1$, le code est dit complet : toutes les feuilles sont utilisées, aucune suite de bits n'est invalide. C'est toujours le cas de Huffman — il ne laisse jamais de nœud à un seul fils, sans quoi on raccourcirait un mot de code d'un bit et l'on ferait mieux. Un profil de longueurs de somme $<1$ prouve donc à lui seul qu'un code n'est pas optimal, sans rien savoir des fréquences.