« Compression de données/Codage entropique » : différence entre les versions

Contenu supprimé Contenu ajouté
m Résolution de redirection; changement de type cosmétique
m Mise en forme d'une formule LaTeX
Ligne 71 :
:minimiser <math>\sum_{i=1}^{|\Omega|}p_i l_i</math> sous la condition <math> \sum_{i=1}^{|\Omega|} D^{-l_i} \leq 1. </math>
Par la méthode des [[multiplicateurs de Lagrange]], on définit le lagrangien <math>J</math>:
:<math>J=\sum_{i=1}^{|\Omega|}p_i l_i + \lambda \left(\sum_{i=1}^{|\Omega|} D^{-l_i}-1\right)</math>
que l'on différentie par rapport aux <math>l_i</math>. Un rapide calcul<ref>[[#CoTh06|Cover, Thomas (2006)]], {{p.}}110-111</ref> donne les longueurs optimales <math>l_i^*=-\log_D p_i</math>, soit une longueur moyenne <math>L(C)=-\sum p_i \log_D p_i</math>, c'est-à-dire l'[[entropie de Shannon|entropie]] <math>H(X)</math>.
Les longueurs données par cette méthode ne sont cependant pas [[entier naturel|entières]], sauf dans le cas exceptionnel où les <math>p_i</math> sont des puissance négatives de D. Ce résultat n'est donc pas utile en pratique, et il est nécessaire d'utiliser d'autres méthodes pour construire un code optimal.