Corrigé bac NSI 2025 Métropole jour 2 — Exercice 1 : Codage de Shannon-Fano : arbre de codage, hauteur, parcours en largeur et fonction récursive

Partie A

1. On lit les étiquettes des branches depuis la racine jusqu'à la feuille _ : branche 0 (vers la droite), puis 1, puis 0. Le caractère espace est donc codé par le mot binaire 010.

On vérifie sur les exemples du sujet : c s'obtient par 1, 1, 0, 1 soit 1101, et d par 1, 1, 0, 0, 0 soit 11000 : c'est bien la lecture attendue.

2. On descend depuis la racine en suivant les bits, et l'on repart de la racine chaque fois qu'une feuille est atteinte :

Le mot binaire 00 011 1010 1111 11001 1001 se décode donc en « espion ». Les 22 bits ont tous été consommés et la dernière lecture s'achève exactement sur une feuille : le décodage est complet.

Ce que le correcteur attend : le décodage n'est pas ambigu parce qu'aucun code n'est le préfixe d'un autre (les symboles ne sont que sur les feuilles) : dès qu'on atteint une feuille, on sait que le symbole est terminé et on repart de la racine.

3. La taille de l'encodage d'un symbole est la profondeur de sa feuille (le nombre de branches entre la racine et la feuille). Le parcours qui visite les nœuds niveau par niveau, par profondeur croissante, est le parcours en largeur (BFS) : il rencontre d'abord e (profondeur 2), puis s et _ (profondeur 3), puis i, u, c, la virgule, p, n, j (profondeur 4), enfin o et d (profondeur 5). Il s'implémente avec une file (FIFO) : on défile un nœud, on enfile ses enfants. Un parcours en profondeur (préfixe, infixe ou suffixe) ne convient pas : il descend jusqu'aux feuilles d'un sous-arbre avant de passer au suivant et mélangerait les profondeurs.

Partie B

4. Le total des occurrences est $7\times 1+2+2+3+4+4=22$, ce qui correspond bien aux 22 caractères du texte (espaces et virgule compris). La moitié vaut $11$. On cumule les occurrences dans l'ordre du tableau : $1,2,3,4,5,6,7$ après les sept symboles à une occurrence, puis $9$ avec n, puis $11$ avec j. Le premier groupe $\{$i, u, c, o, d, « , », p, n, j$\}$ totalise $11$ occurrences et le second $\{$s, _, e$\}$ totalise $3+4+4=11$ occurrences : les deux totaux sont égaux, on ne peut pas faire plus proche. C'est la séparation de la Figure 2 : le premier groupe part à gauche (branche 1), le second à droite (branche 0).

5. La hauteur de l'arbre de la Figure 3 est $5$ : la branche la plus longue mène de la racine aux feuilles o et d en cinq arêtes (racine $\to$ [iucod,pnj] $\to$ [iucod] $\to$ [cod] $\to$ [od] $\to$ o). Dans le contexte de l'exercice, la hauteur est la longueur du plus long code binaire : les symboles les moins fréquents, o et d, sont codés sur $5$ bits (11001 et 11000). C'est le nombre maximal de bits qu'il faut lire pour décoder un symbole.

6. En ASCII, chaque caractère occupe un octet : le texte de $22$ caractères occupe $22$ octets, soit $176$ bits.

Avec le codage de Shannon-Fano, la longueur du code d'un symbole est la profondeur de sa feuille dans la Figure 3 ; on multiplie par le nombre d'occurrences :

Total : $4+4+4+5+5+4+4+8+8+9+12+8=75$ bits, soit $10$ octets ($9$ octets ne font que $72$ bits ; il en faut un dixième pour les $3$ bits restants). On passe de $22$ octets à $10$ octets, soit un rapport $22/10=2,2$ : environ deux fois moins d'octets. Le gain vient de ce que les symboles fréquents (e, _, s) ont les codes les plus courts.

7. On applique l'algorithme au mot chiffrer ($8$ lettres).

Étape 1 : occurrences c : 1, h : 1, i : 1, e : 1, f : 2, r : 2 (total $8$) ; on les range par nombre croissant : c, h, i, e, f, r (l'ordre entre symboles de même nombre d'occurrences est libre).

Étape 2 : la moitié de $8$ est $4$ ; les quatre premiers symboles cumulent $4$ occurrences, les deux derniers aussi : premier groupe [c h i e] (branche 1), second groupe [f r] (branche 0).

Étape 4, récursivement : [c h i e] (total $4$, moitié $2$) se sépare en [c h] et [i e], puis chacun en deux feuilles ; [f r] (total $4$, moitié $2$) se sépare en f et r.

Les codes obtenus sont c : 111, h : 110, i : 101, e : 100, f : 01, r : 00 ; le mot chiffrer s'encode en $4\times 3+4\times 2=20$ bits au lieu de $64$ en ASCII. Tout arbre de même forme obtenu avec un autre ordre des symboles à une occurrence (par exemple e i h c) est également correct.

Partie C

8. Si le symbole est déjà une clé du dictionnaire, on incrémente son compteur ; sinon on crée la clé avec la valeur $1$ :

def creer_dico_occ(texte):
    """renvoie un dictionnaire dont les clés sont les
    symboles de texte et les valeurs associées leur
    nombre d'occurences dans texte"""
    dico = {}
    for symbole in texte:
        if symbole in dico:
            dico[symbole] = dico[symbole] + 1
        else:
            dico[symbole] = 1
    return dico

Sur 'je pense, donc je suis', la fonction renvoie \{'j': 2, 'e': 4, ' ': 4, 'p': 1, 'n': 2, 's': 3, ',': 1, 'd': 1, 'o': 1, 'c': 1, 'u': 1, 'i': 1\}, en accord avec le tableau de la Partie B. Le test d'appartenance symbole in dico porte sur les clés et coûte un temps constant en moyenne (table de hachage) : le comptage est linéaire en la longueur du texte.

9. On parcourt le tableau et l'on accumule la seconde composante de chaque tuple :

def somme_occ(tab):
    """renvoie la somme des nombres d'occurrences
    des tuples (symbole, nb_occ) du tableau tab"""
    somme = 0
    for couple in tab:
        somme = somme + couple[1]
    return somme

Sur le tableau trié de l'exemple, somme_occ renvoie 22 ; sur un tableau vide elle renvoie 0. Sa complexité est linéaire en la longueur du tableau.

10. Après la séparation, si le symbole est dans le premier sous-tableau t1, son code commence par 1 et se poursuit par son code dans t1 ; sinon il commence par 0 et se poursuit par son code dans t2 :

def shannon(symbole, tab):
    """renvoie l'écriture binaire associée à symbole
    dans le tableau trié tab"""
    if len(tab) == 1:
        return ""
    else:
        t1, t2 = separe(tab)
        if symbole in [elt[0] for elt in t1]:
            return "1" + shannon(symbole, t1)
        else:
            return "0" + shannon(symbole, t2)

Trace de shannon('s', tab) sur le tableau trié de l'exemple : 's' est dans t2 = [s, _, e] donc on renvoie "0" + shannon('s', t2) ; dans t2 (total $11$, moitié $5$), separe donne [s, _] et [e], 's' est dans le premier : "1" + shannon('s', [s, _]) ; enfin [s, _] (total $7$, moitié $3$) se sépare en [s] et [_], d'où "1" + shannon('s', [s]) et le cas de base renvoie "". Résultat : "011", le code de s dans la Figure 3.

11. La fonction est récursive et chaque appel récursif porte sur t1 ou t2, deux sous-tableaux strictement plus courts que tab : dès que tab contient au moins deux symboles, separe place au moins un symbole dans chaque partie (la boucle while fait au moins un tour car moitie $\ge 1>$ somme $=0$, et s'arrête avant d'avoir tout pris puisque les sommes sont les plus proches possible). La longueur len(tab) est donc un variant : un entier positif qui décroît strictement à chaque appel. Elle finit par atteindre $1$, qui est le cas de base (len(tab) == 1, ligne 4) : la fonction renvoie "" sans appel récursif. La récursion s'arrête donc après au plus len(tab) $-1$ appels.

Ce que le correcteur attend : nommer les deux ingrédients, le cas de base et la décroissance stricte de la taille du tableau à chaque appel. On note au passage que la terminaison suppose que symbole figure bien dans tab et que les deux sous-tableaux sont non vides ; avec le code de separe donné, un symbole qui à lui seul dépasse la moitié des occurrences (texte 'aaab' par exemple) laisse t2 vide et la fonction ne termine plus (RecursionError) : c'est pour cela que le sujet prend soin de supposer que separe équilibre les deux parties.

12. On construit une seule fois le tableau trié, puis on concatène le code de chaque symbole du texte, dans l'ordre :

def encode_shannon(texte):
    """renvoie le mot binaire codant texte
    par l'algorithme de Shannon-Fano"""
    dico = creer_dico_occ(texte)
    tab = creer_tab_trie(dico)
    mot = ""
    for symbole in texte:
        mot = mot + shannon(symbole, tab)
    return mot

Testée sur 'je pense, donc je suis', la fonction renvoie un mot de $75$ bits, la longueur calculée à la question 6. Sur 'chiffrer' elle renvoie un mot de $20$ bits au lieu des $64$ du codage ASCII. Le sujet ne dit pas comment creer_tab_trie départage les symboles de même nombre d'occurrences, et ce choix change le mot obtenu : avec le tableau [('e', 1), ('i', 1), ('h', 1), ('c', 1), ('r', 2), ('f', 2)] (l'ordre qu'on obtient en départageant les ex æquo comme dans l'exemple du sujet) on lit '10010111000000111101' ; avec [('c', 1), ('h', 1), ('i', 1), ('e', 1), ('f', 2), ('r', 2)], l'ordre de l'arbre dessiné à la question 7, on lit '11111010101010010000'. L'ordre choisi entre ex æquo change les codes, jamais la longueur totale ($20$ bits dans les deux cas). Sur un texte vide elle renvoie la chaîne vide, et sur un texte formé d'un seul symbole répété ('aaa') elle renvoie aussi la chaîne vide : le tableau trié n'a qu'un élément et son code est vide.

Ce que le correcteur attend : le tableau trié est calculé avant la boucle, pas à chaque symbole, et c'est shannon(symbole, tab) qui est appelée sur le tableau complet (la descente dans les sous-tableaux est faite par la récursion). Remarque : pour le groupe [, p n j] (occurrences $1,1,2,2$), deux séparations sont aussi équilibrées ([, p] $|$ [n j] et [, p n] $|$ [j], écart $2$ dans les deux cas) ; le code de separe choisit la seconde, si bien que encode_shannon attribue 100 à j, 1010 à n, 10110 à p et 10111 à la virgule, codes différents de la Figure 3 mais de même longueur totale ($75$ bits) : c'est pourquoi le sujet dit qu'on « peut » obtenir l'arbre de la Figure 3.