Skip to content

Séquence 7

L'objectif de la séquence est de travailler sur la notion de codage optimal. On poura lire le chapitre 16 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

Les codes ci-dessous ont-ils la propriété du préfixe

Lettre code 1 code 2 code 3 code 4 code5
A 0 01 01 0 000
B 10 10 000 10 001
C 110 111 1000 1100 010
D 1110 101 1001 1101 011
E 11110 11001 110 1110 100
F 11111 11100 111 1111 101

réponses (éléments)

  1. oui le code 1 a la propriété du préfixe, l'arbre associé est un peigne
  2. non le code 2 n'a pas la propriété du préfixe, le code de B est préfixe du code de D
  3. oui le code 3 a la propriété du préfixe, il n'est pas optimal (construire l'arbre associé)
  4. oui le code 4 a la propriété du préfixe, dans l'arbre associé tout noeud interne a exactement 2 fils
  5. oui c'est le code de longueur fixe (longueur = 3)

Question 2

Dans un texte on observe le nombre de lettres (le texte comporte 32 lettres).

Lettre A B C D E F G
Nombre 1 16 4 4 4 2 1
  1. L'entropie de cette répartition de lettres est \(2\),\(2.1875\),\(2.625\),\(3\), \(3.742\),\(4\)
  2. Dans l'arbre de Huffman la lettre G sera à la hauteur (hauteur de la racine = 0 par convention) \(2\), \(3\), \(4\), \(5\), \(6\)
  3. Pour cette répartition de lettres la complexité du code de Huffman est inférieure/égale/supérieure à l'entropie ?

réponses (éléments)

  1. l'entropie est \(\sum p_i(-\log_2 p_i)\) ici on obtient \(2.1875\), c'est calculable à la main car les proportions sont des puissances de 2
  2. la lettre G est à la hauteur 5, il faut 5 symboles pour coder G. C'est logique, sa proportion est \(\frac 1{32}= 2^{-5}\)
  3. dans ce cas particulier de puissances de 2 la complexité du code est égale à l'entropie. Dans le cas général elle est toujours supérieure ou égale.

Question 3

Dans l'algorithme de Huffman, que l'on exécute sur un ensemble de \(K\) symboles, à la fin de l'itération \(i\)

  1. la somme des tailles des arbres contenus dans la file à priorité est égal à \(K\), \(2K\), \(K+i\), \(K-i\)
  2. la somme des poids des racines des arbres dans la file à priorité est (a) à la somme des poids des feuilles, (b) à \(1\) si la pondération est une probabilité, © au nombre d'arbres dans la file à priorité, (d) au nombre de symboles

réponses (éléments)

  1. la file à priorité contient \(n+i\) noeuds, en effet initialement la file contient les \(K\) feuilles, à chaque étape on réalise la fusion de 2 arbres avec l'adjonction d'un noeud. donc à l'itération i on rajoute \(1\) noeud.
  2. (a) et (b) sont correctes (ce sont des invariants).