Inégalité de Kraft

Par induction structurelle sur l’arbre : évident si ${\displaystyle {\mathcal {A}}}$ est une feuille ou vide.

Si ${\displaystyle {\mathcal {A}}={\mathcal {N}}({\mathcal {A}}_{0},{\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r-1})}$, tel que ${\displaystyle {\mathcal {A}}_{i}}$ vérifie l'inégalité de Kraft pour tout ${\displaystyle i}$, notons ${\displaystyle d'(\ell )}$ la profondeur de la feuille ${\displaystyle \ell }$ dans le sous-arbre de ${\displaystyle {\mathcal {A}}}$ auquel elle appartient. On a alors :

${\displaystyle \sum _{\ell \in {\mathcal {L}}({\mathcal {A}})}r^{-d(\ell )}=\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d(\ell )}=\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d'(\ell )-1}=r^{-1}\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d'(\ell )}}$

En appliquant l’hypothèse de récurrence, on a ${\displaystyle \sum _{\ell \in {\mathcal {L}}({\mathcal {A}})}r^{-d(\ell )}\leqslant r^{-1}\sum _{i=0}^{r-1}1=1}$

Sans perte de généralité, supposons ${\displaystyle \ell _{0}\leqslant \ell _{1}\leqslant \dots \ell _{n-1}}$ On propose de construire cet arbre avec l’algorithme suivant :

programme arbre(n, r, [l_0, l_1, ... l_{n-1}])
    A <- Arbre r-aire complet de profondeur l_{n-1}
    pour i de 0 à n-1
        choisir un noeud n de A non-marqué de profondeur l_i
        en faire une feuille i.e. supprimer tous ses descendants
        le marquer
    retourner A

Pour justifier de la correction de l'algorithme, on a besoin de deux éléments :

• On ne supprime jamais un nœud marqué par l’algorithme : lorsqu'on construit une feuille de profondeur ${\displaystyle \ell _{i}}$, on ne supprime que des nœuds de profondeur strictement supérieure à ${\displaystyle \ell _{i}}$. Or, comme les profondeurs sont triées par ordre croissant, toutes les feuilles marquées sont de profondeur au plus ${\displaystyle \ell _{i}}$.
• À l'étape ${\displaystyle i}$, il existe un nœud de profondeur ${\displaystyle \ell _{i}}$ qui n’a pas été marqué : il suffit de remarquer qu'à l'étape ${\displaystyle j}$ l’algorithme supprime ou marque ${\displaystyle r^{\ell _{n-1}-\ell _{j}}}$ nœud(s) de profondeur ${\displaystyle \ell _{n-1}}$. Avant l'étape ${\displaystyle i}$ on a donc supprimé ou marqué ${\displaystyle \sum _{j=0}^{i-1}r^{\ell _{n-1}-\ell _{j}}\leqslant r^{\ell _{n-1}}\sum _{j=0}^{n-1}r^{-\ell _{j}}\leqslant r^{\ell _{n-1}}}$, par inégalité de Kraft. Il existe donc un nœud de profondeur ${\displaystyle \ell _{n-1}}$ qui n'a été ni marqué, ni supprimé, prenons son ancêtre de profondeur ${\displaystyle \ell _{i}}$, ce nœud n’a pas encore été marqué, ce qui conclut la preuve de l'algorithme.

Notons ${\displaystyle \ell (a)}$ la longueur du code d'un mot ${\displaystyle a}$ sur ${\displaystyle {\mathcal {S}}}$ et ${\displaystyle \ell _{M}=\max\{\ell (s),s\in {\mathcal {S}}\}}$, et considérons ${\displaystyle N_{m,p}}$ le nombre de mots de taille ${\displaystyle m}$ dont le code est de taille ${\displaystyle p}$ : ${\displaystyle N_{m,p}=|\{a\in {\mathcal {S}}^{m},\ell (a)=p\}|}$. comme ${\displaystyle {\mathcal {C}}}$ est uniquement décodable, on a ${\displaystyle N_{m,p}\leqslant |{\mathcal {T}}^{p}|=r^{p}}$.

On a alors

${\displaystyle \sum _{a\in {\mathcal {S}}^{m}}r^{-\ell (a)}=\sum _{p=1}^{m\ell _{M}}\sum _{a\in {\mathcal {S}}^{m},\ell (a)=p}r^{-\ell (a)}=\sum _{p=1}^{m\ell _{M}}N_{m,p}r^{-p}\leqslant \sum _{p=1}^{m\ell _{M}}r^{p}r^{-p}=m\ell _{M}}$

Mais un simple développement nous donne : ${\displaystyle \left(\sum _{s\in {\mathcal {S}}}r^{-\ell (s)}\right)^{m}=\sum _{a\in {\mathcal {S}}^{m}}r^{-\ell (a)}}$, ce qui nous amène à ${\displaystyle \sum _{s\in {\mathcal {S}}}r^{-\ell (s)}\leqslant (m\ell _{M})^{1/m}}$. Ceci étant vrai pour tout ${\displaystyle m}$, comme ${\displaystyle (m\ell _{M})^{1/m}\longrightarrow 1}$, on retrouve l'inégalité voulue.