« Compression de données/Codage entropique » : différence entre les versions
Contenu supprimé Contenu ajouté
→Propriétés des codes de source : ajout d'un contre-exemple uniquement décodable mais non-préfixé |
Ajout de la partie sur les arbres |
||
Ligne 25 :
Un code doit respecter certaines propriétés pour être utile: une concaténation de mots de code doit avoir un décodage unique, aisé, et permettre la plus grande compression possible<ref name=McKay92>[[#McKay03|McKay (2003)]], {{p.}}92</ref>. Certaines conditions sont imposées au code pour satisfaire ces propriétés.
=== Codes préfixes ===
{{Théorème|Définition|Un code est dit '''uniquement décodable''' (ou uniquement déchiffrable) si
:<math>\forall x,y \in \Omega^+, x \ne y \Rightarrow C^+(x) \ne C^+(y)</math>}}
Ligne 64 ⟶ 65 :
|-
|}
Le code <math>C_1=\{0, 10, 110, 111\}</math> est un code préfixé.
La séquence codée comme : 11011111010110010110111 se décompose facilement en: 110 111 110 10 110 0 10 110 111
et se décode donc comme : c d c b c a b c d
* Tout code uniquement décodable n'est pas nécessairement un code préfixé. Par exemple <math> C \{a \mapsto 0, b\mapsto 01\} </math> est uniquement décodable.
=== Lien avec les arbres ===
Il existe une bijection entre les [[Arbre enraciné|arbres]] et les codes préfixes : étant donné un arbre <math>r</math>-aire dont les feuilles sont les éléments d’un alphabet <math>\mathcal{S}</math>, on trouve un code préfixe de <math>\{0, 1 \dots r-1\}</math>en associant à chaque élément les indices des fils allant de la racine à cet élément, la taille du code de chaque élément est alors la profondeur de cet élément dans l’arbre.
Par exemple, le code préfixe <math>C_2 : \{a\mapsto 00, b\mapsto 01, c\mapsto 10, d\mapsto 112, e\mapsto 12, f\mapsto 2\}</math> de <math>\mathcal{S} = \{a,b,c,d,e,f\}</math>sur l’alphabet <math>\{0,1,2\}</math> est représenté par l'arbre ternaire :
[[Fichier:Arbre préfixe.svg|alt=un arbre ternaire|centré|450x450px|arbre associé au codage <math>C_2</math><br />]]
Réciproquement, étant donné un code préfixe, on peut construire de tels arbres.
Ces arbres sont aussi une structure de données pour l’algorithme de décodage du code préfixe : en partant de la racine, à chaque lettre <math>x</math> aller au fils <math>x</math> du nœud sur lequel on se trouve, si ce fils est une feuille, l’afficher et revenir à la racine.
== Inégalité de Kraft ==
| |||