Wikilivres

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

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Aucun résumé des modifications
Annulation de la modification de Calin-info (d)
Ligne 31 :
{{Théorème|Définition|Un code est un [[code préfixe]] si aucun mot de code n'est le préfixe d'un autre mot de code.}} L'intérêt des codes préfixés est qu'ils sont décodables immédiatement, en les parcourant de la gauche vers la droite. La fin d'un mot de code est reconnaissable immédiatement, sans la nécessité d'un code spécial pour indiquer la terminaison ou une séparation<ref name=McKay92/>{{,}}<ref>[[#CoTh06|Cover, Thomas (2006)]], {{p.}}106</ref>. De plus, les codes préfixes sont uniquement décodables.
 
{{Démonstration|
Soient <math> x_1x_2\dots x_n, y_1y_2\dots y_m: C^+(x_1x_2\dots x_n) = C^+(y_1y_2\dots y_m) </math>
Alors <math>C^+(x_1x_2\dots x_n) = C(x_1)C^+(x_2\dots x_n)</math> = C(y_1)C^+(y_2\dots y_m) </math>
Supposons sans perte de généralité <math> |C(x_1)| \leq |C(y_1)| </math>.
Alors <math> C(x_1) </math> est préfixe de <math> C(y_1) </math>, donc, comme <math>C</math> est sans préfixe, <math> x_1 = y_1 </math>.
}}
*Exemple: Soit le code défini par le tableau suivant
{| class="wikitable centre" style="text-align:center; width:80%;"
Récupérée de « https://fr.wikibooks.org/wiki/Compression_de_données/Codage_entropique »