Exercice 2 · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2 bis)

Exercice 2 (6 points)

Cet exercice porte sur les arbres binaires et la représentation binaire.

L'échange de données sur les réseaux devient de plus en plus important. Il s'avère que la compression est un élément essentiel dans cet échange. On étudie ici un algorithme de compression, reposant sur le codage de Huffman.

Le codage de Huffman est adapté au texte à compresser car on se sert du nombre d'occurrences des caractères dans le texte. Par exemple, l'arbre de la Figure 1 a été construit pour compresser la phrase "julie fuit la pluie". Le nombre associé à un ensemble de caractères correspond à la somme de leur nombre d'occurrences dans la phrase. Chaque chemin parcouru de haut en bas dans l'arbre définit le code associé au caractère présent en bas: ce code est constitué d'un 0 à chaque fois qu'on est allé à gauche et d'un 1 à chaque fois qu'on est allé à droite, mis bout à bout.

La compression de "julie" donne donc: j → 0100, u → 111, l → 100, i → 101, e → 011, soit 0100111100101011. La compression de " " (caractère espace) donne 00.

1.

Donner un exemple de feuille et la racine de l'arbre de la Figure 1.

2.

On rappelle que la profondeur d'un nœud est égale à la distance en nombre d'arêtes entre ce nœud et la racine. Donner la profondeur du nœud correspondant au caractère p et son code binaire associé.

3.

On remarque que sur la Figure 1, les nœuds associés aux caractères les plus fréquents ont une profondeur plus petite. Expliquer l'intérêt de cette propriété pour le codage binaire de la phrase.

4.

On définit de façon incomplète la classe Noeud:

class Noeud:

def __init__(self, nom, nb_occu, fils_g, fils_d):

....nom = nom

....nb_occu = nb_occu

....fils_g = fils_g

....fils_d = fils_d

def __str__(self):

"""

Renvoie une chaine contenant les donnees

du noeud (nom et nombre d'occurrences)

"""

return '(' +....nom + ',' + str(...) + ')'

Recopier et compléter les lignes 3, 4, 5, 6 et 13 de la classe Noeud ci-dessus:

5.

On souhaite créer une fonction liste_occurrences:

def liste_occurrences(chaine):

dico =...

for c in chaine:

if c in...:

dico[c] = dico[c] + 1

else:

...

liste_res =...

for cle in dico:

liste_res....

return...

Recopier et compléter le code de la fonction liste_occurrences:

6.

Recopier et compléter le code de la fonction tri_liste:

def tri_liste(liste_a_trier):

liste_triee = []

for i in range(0,...):

element = liste_a_trier[i]

...

while (j < len(liste_triee) and

element[1] >= liste_triee[j][1]):

...

liste_triee.insert(...,...)

return liste_triee

7.

Une fois la liste triée, il faut ensuite transformer la liste de tuples en liste de nœuds. Écrire la fonction conversion_en_noeuds qui convertit une liste de tuples en liste de nœuds.

8.

Recopier et compléter le code de la fonction insere_noeud qui modifie la liste liste_noeud passée en paramètre:

def insere_noeud(noeud, liste_noeud):

j = 0

while j < len(liste_noeud) and... >...:

...

liste_noeud.insert(...,...)

9.

Recopier et compléter le code de la fonction construit_arbre, qui renvoie le nœud correspondant à la racine de l'arbre:

def construit_arbre(liste):

while... > 1:

noeud1 = liste.pop(0)

noeud2 = liste.pop(0)

nom_noeud_pere = noeud1.nom + "-" + noeud2.nom

nb_occu_noeud_pere =...

noeud_pere = Noeud(...)

insere_noeud(..., liste)

return...

10.

Indiquer la structure de données renvoyée par la fonction codage_arbre:

11.

Écrire une fonction compresse qui, à partir du texte et de la structure renvoyée par codage_arbre, renvoie la suite binaire sous forme d'une chaîne de caractères représentant le texte compressé.