Aller au contenu

Codage de Huffman (construction de l'arbre)

Présentation rapide

Le codage de Huffman est un codage qui permet de compresser des données. Dans le cas d'un texte, codé en UTF-8, chaque caractère prendra la place de un à quatre octets. Dans le cas du codage de Huffman , plus un caractère est fréquent dans le texte, plus court sera son codage en binaire.

Exemple

Le texte : que voulez vous que je vous dise sera codé par : 01111011101110000011011000011010001111000001101010111011110111011110010110111000001101010111100110110010110. Soit \(107\) bits au lieu de \(256\) avec le codage UTF-8. Le caractère espace ' ' sera codé par 111, tandis que le caractère 'l' sera codé par 10000.

Série d'exercices

Cet exercice fait partie d'une série :

Ce codage est basé sur la construction d'un arbre, objectif de cet exercice.

Note

Toutes les fonctions créées dans des questions sont utilisables dans les questions suivantes.

Principe de construction⚓︎

  • Le codage de Huffman est basé sur un arbre, dont les feuilles sont liées aux caractères du texte.
  • On détermine les occurrences de tous les caractères d'un texte.
  • On crée les feuilles du futur arbre. Chaque feuille aura pour étiquette un caractère et un poids qui est son nombre d'occurrences dans le texte.
  • On fusionne les feuilles et les nœuds deux par deux.
  • Chaque fusion produit un nouvel arbre dont le nœud racine a pour étiquette un poids égal à la somme des poids des étiquettes des nœuds fusionnés.
Exemple de construction de l'arbre

Prenons pour exemple le texte que voulez vous que je vous dise.

Le nombre d'occurrences de chaque lettre est :

q u e v o l z s j d i
2 5 5 6 3 3 1 1 3 1 1 1

On peut alors créer les feuilles du futur arbre.

La donnée associée à chaque nœud est un caractère et son poids qui est son nombre d'occurrences.

graph TD
    N7(l:1):::feuille
    N8(z:1):::feuille
    N90(j:1):::feuille
    N10(d:1):::feuille
    N1(i:1):::feuille
    N11(q:2):::feuille
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88

Ces feuilles sont triées selon l'ordre croissant du poids de leur nœud.

L'arbre de Huffman est un arbre construit progressivement à partir des feuilles.

À partir des deux nœuds ayant les plus petits poids, on crée un arbre :

  • la racine aura pour donnée un symbole vide et comme poids la somme des poids des deux nœuds ;
  • les sous arbres droit et gauche seront les deux nœuds sélectionnés.

Ici les feuilles l:1 et z:1 ont été fusionnés de façon à former un nouvel arbre dont le poids de la racine est 1 + 1 = 2

graph TD
    N90(j:1):::feuille
    N10(d:1):::feuille
    N1(i:1):::feuille
    N11(q:2):::feuille
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N13(( :2)) --> N7(l:1):::feuille
    N13 --> N8(z:1):::feuille
    classDef feuille fill:#F88

Parmi l'ensemble des nœuds, d'une part les feuilles et d'autre part les nœuds fusionnés, on choisit les deux nœuds de poids les plus faibles, pour créer un arbre dont la racine aura pour donnée la somme des poids des deux nœuds et, pour sous arbres gauche et droit, les nœuds choisis.

graph TD
    N1(i:1):::feuille
    N11(q:2):::feuille
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N12(( :2)) --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13(( :2)) --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    classDef feuille fill:#F88

On poursuit jusqu'à ce qu'il ne reste qu'un seul nœud. Lorsqu'une feuille et un nœud ont le même poids, on privilégie la feuille.

graph TD
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N12(( :2)) --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13(( :2)) --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N14(( :3)) --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    classDef feuille fill:#F88

Ici on a fusionné deux nœuds déjà construits car leur poids (2) étaient plus petits que celui des feuilles (3 au minimum.)

graph TD
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N14(( :3)) --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N15(( :4)) --> N12(( :2))
    N15 --> N13(( :2))
    N12(( :2)) --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13(( :2)) --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille

    classDef feuille fill:#F88
graph TD
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N14(( :3)) --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N15(( :4)) --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N16(( :6)) --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    classDef feuille fill:#F88

Ici les deux nœuds aux poids les plus petits, sont la feuille s:3 et le nœud construit, qui avait un poids de 3

graph TD
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N15(( :4)) --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N16(( :6)) --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17(( :6)) --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    classDef feuille fill:#F88

graph TD
    N3(e:5):::feuille
    N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N16(( :6)) --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17(( :6)) --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N18(( :9)) --> N15(( :4))
    N18 --> N2(u:5):::feuille
    N15 --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    classDef feuille fill:#F88
graph TD
    N16(( :6)) --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17(( :6)) --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N18(( :9)) --> N15(( :4))
    N18 --> N2(u:5):::feuille
    N15 --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N19(( :11)) --> N3(e:5):::feuille
    N19 --> N4(_:6):::feuille
    classDef feuille fill:#F88
graph TD
    N18(( :9)) --> N15(( :4))
    N18 --> N2(u:5):::feuille
    N15 --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N19(( :11)) --> N3(e:5):::feuille
    N19 --> N4(_:6):::feuille
    N20(( :12)) --> N16(( :6))
    N20 --> N17(( :6))
    N16 --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17 --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    classDef feuille fill:#F88
graph TD
    N20(( :12))
    N21(( :20))
    N20 --> N16(( :6))
    N20 --> N17(( :6))
    N16 --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17 --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N21 --> N18(( :9))
    N18 --> N15(( :4))
    N18 --> N2(u:5):::feuille
    N15 --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N21 --> N19(( :11))
    N19 --> N3(e:5):::feuille
    N19 --> N4(_:6):::feuille
    classDef feuille fill:#F88

On poursuit jusqu'à ce qu'il ne reste qu'un seul nœud dont le poids sera égal à la somme des poids des nœuds initiaux, c'est à dire à la longueur du message.

graph TD
    N22(( :32)) --> N20(( :12))
    N22 --> N21(( :20))
    N20 --> N16(( :6))
    N20 --> N17(( :6))
    N16 --> N5(v:3):::feuille
    N16 --> N6(o:3):::feuille
    N17 --> N9(s:3):::feuille
    N17 --> N14(( :3))
    N14 --> N1(i:1):::feuille
    N14 --> N11(q:2):::feuille
    N21 --> N18(( :9))
    N18 --> N15(( :4))
    N18 --> N2(u:5):::feuille
    N15 --> N12(( :2))
    N15 --> N13(( :2))
    N12 --> N7(l:1):::feuille
    N12 --> N8(z:1):::feuille
    N13 --> N90(j:1):::feuille
    N13 --> N10(d:1):::feuille
    N21 --> N19(( :11))
    N19 --> N3(e:5):::feuille
    N19 --> N4(_:6):::feuille
    classDef feuille fill:#F88

Pour la suite, on adaptera l'algorithme en utilisant la structure suivante :

  • chaque nœud est un arbre dont l'étiquette de la racine sera un dictionnaire dont les clés seront caractère et poids.
  • une file, nommée par la suite file1, contiendra l'ensemble des feuilles enfilées dans l'ordre croissant de leur poids.
  • une file, nommée par la suite file2, contiendra l'ensemble des nœuds fusionnés au fur et à mesure.
  • si au début, la file contenant les feuilles, ne comporte qu'une seule feuille, l'arbre de Huffman correspondant est cette feuille.
  • la file contenant les feuilles sera systématiquement vide à la fin du traitement.
L'algorithme adapté à la structure 
Tant qu'il reste au moins deux nœuds dans l'ensemble des deux files:
    - prendre les deux nœuds de poids minimal et les retirer de leur file. À poids égaux, les nœuds des dictionnaires de `file1`
    sont choisis prioritairement.
    - fusionner les deux nœuds (avec l'étiquette `caractère` égale à `""` et le poids égal à la somme des 2 poids des nœuds précédents)
    - enfiler ce nœud à la file 2 des nœuds fusionnés
Renvoyer l'unique nœud, correspondant à l'arbre recherché.

On peut remarquer que lorsqu'on fusionne deux nœuds, le nouveau poids est obligatoirement supérieur ou égal au poids des nœuds qui ont déjà été fusionnés. La seconde file est donc toujours ordonnée de façon croissante.

Éléments fournis

  • Une classe Arbre dont un exemple d'utilisation est donné ci-dessous.

    La classe Arbre

    La classe d'arbre proposée dispose de l'interface suivante :

    Constructeur :

    • Arbre(donnee) : crée un arbre dont la racine a pour étiquette donnee, qui ici sera un dictionnaire.
    • Arbre(donnee, sous_arbre_gauche, sous_arbre_droit) : crée un arbre dont la racine a l'étiquette donnee et deux sous-arbres sous_arbre_gauche et sous_arbre_droit

    Méthodes fournies :

    • donnee() : renvoie l'étiquette de la racine
    • sous_arbre_gauche() : renvoie le sous-arbre droit
    • sous_arbre_droit() : renvoie le sous-arbre gauche
    • est_feuille()
    Exemple d'utilisation

    On ajoute la possibilité d'afficher un arbre, dont les étiquettes sont de forme {"caractere":…, "poids":…}, sous forme classique pour visualiser le contenu.

    🐍 Console Python
    >>> a1 = Arbre({"caractere": "a", "poids": 1})
>>> a1.est_feuille()
True
>>> a1.donnee()
{'caractere': 'a', 'poids': 1}
>>> a2 = Arbre({"caractere": "b", "poids": 2})
>>> a3 = Arbre({"caractere": "", "poids": 3}, a1, a2)
>>> a3.affiche()
      ':3'
     /    \
'a:1'      'b:2'

  • Une structure de file avec la classe File dont un exemple d'utilisation est donné ci-dessous.

    La classe File

    Afin d'effectuer la comparaison, sans avoir à défiler les éléments, on ajoute la méthode sommet, qui renvoie le prochain élément qui sera défilé, sans le retirer.

    Le constructeur : File()

    Les méthodes :

    • est_vide() : renvoie un True si la file est vide, False sinon.
    • enfile(x) : place x à la queue de la file
    • defile() : renvoie le premier élément de la file
    • sommet() : renvoie le sommet de la file, sans le défiler.

    La fonction len() renvoie la longueur de la file passée en paramètre.

    Exemple d'utilisation
    🐍 Console Python
    >>> f1 = File()
>>> f1.est_vide()
True
>>> f1.enfile(10)
>>> f1.enfile(20)
>>> len(f1)
2
>>> f1.sommet()
10
>>> len(f1)
2
>>> f1.defile()
10
>>> len(f1)
1
>>> f1.defile()
20

  • Une fonction construit_file_caracteres qui prend en paramètre une liste de dictionnaires sous la forme [{'caractere': 'l', 'poids': 1}, {'caractere': 'o', 'poids': 3},...], et qui renvoie une file de feuilles dont l'étiquette est un dictionnaire {'caractère': valeur, 'poids': valeur}. Les éléments de la file sont triés par ordre croissant. L'élément de poids le plus petit sera le premier élément défilé.

    Exemple d'utilisation

    🐍 Console Python
    >>> occurrences_1 = [{'caractere': 'l', 'poids': 1}, {'caractere': 'o', 'poids': 3}]
>>> file1 = construit_file_caracteres(occurrences_1)
    L'objet file1 contient dans l'ordre Arbre({'caractere': 'l', 'poids': 1}), Arbre({'caractere': 'o', 'poids': 3})

Question 1 : plus_leger(file1, file2)

Créer la fonction plus_leger. Cette fonction prend comme paramètres deux files file1 et file2 , file1 étant une file de feuilles enfilées dans l’ordre croissant des poids et file2 une file de nœuds(éventuellement feuilles) fusionnés enfilés dans l’ordre croissant du poids de la racine. La fonction renvoie l’élément de poids le plus faible de file1 et file2 et le défile. Les éléments des files sont des feuilles dont l'étiquette est un dictionnaire {'caractère': valeur, 'poids': valeur}, ou des arbres dont l'étiquette de la racine est un dictionnaire {'caractère': valeur, 'poids': valeur}.

Différents cas :

Si l'une des files est vide, c'est le sommet de l'autre file qui est renvoyé.

graph RL

subgraph resul [Plus léger]
R1(l:1):::feuille_resul
end
subgraph sub1 [file 1]
    direction TB
    N7(l:1):::feuille_resul
    N8(z:1):::feuille
    N90(j:1):::feuille
    N10(d:1):::feuille
    N1(i:1):::feuille
    N11(q:2):::feuille
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille

end

subgraph sub2 [file 2]
        direction TB
    IN7( ):::invisible
    IN8( ):::invisible
    IN90( ):::invisible
    IN10( ):::invisible
    IN1( ):::invisible
    IN11( ):::invisible



end
classDef feuille fill:#F88
classDef feuille_resul fill:#FF8
classDef invisible opacity:0
sub1 --> resul
sub2 --> resul
graph RL

subgraph resul [Plus léger]
subgraph noeud0 [ ]
        direction TB
            IN16(( :6)):::feuille_resul --> IN5(v:3):::feuille
            IN16 --> IN6(o:3):::feuille
        end

end
subgraph sub1 [file 1]

    direction TB
    IN7( ):::invisible
    IN8( ):::invisible
    IN90( ):::invisible
    IN10( ):::invisible
    IN1( ):::invisible
    IN11( ):::invisible


end

subgraph sub2 [file 2]
        direction TB
        subgraph noeud4 [ ]
        direction TB
            N19(( :11)) --> N3(e:5):::feuille
            N19 --> N4(_:6):::feuille
        end
        subgraph noeud3 [ ]
        direction TB
            N18(( :9)) --> N15(( :4))
            N18 --> N2(u:5):::feuille
            N15 --> N12(( :2))
            N15 --> N13(( :2))
            N12 --> N7(l:1):::feuille
            N12 --> N8(z:1):::feuille
            N13 --> N90(j:1):::feuille
            N13 --> N10(d:1):::feuille
        end
        subgraph noeud2 [ ]
        direction TB
            N17(( :6)) --> N9(s:3):::feuille
            N17 --> N14(( :3))
            N14 --> N1(i:1):::feuille
            N14 --> N11(q:2):::feuille
        end
        subgraph noeud1 [ ]
        direction TB
            N16(( :6)):::feuille_resul --> N5(v:3):::feuille
            N16 --> N6(o:3):::feuille
        end
end
classDef feuille fill:#F88
classDef feuille_resul fill:#FF8
classDef invisible opacity:0
sub1 --> resul
sub2 --> resul

C'est le cas général, c'est l'élément au poids le plus petit qui est renvoyé.


graph RL

subgraph resul [Plus léger]
    direction TB
    IN1(i:1):::feuille_resul
end
subgraph sub1 [file 1]
    direction TB
    N1(i:1):::feuille_resul
    N11(q:2):::feuille
    N5(v:3):::feuille
    N6(o:3):::feuille
    N9(s:3):::feuille
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::feuille
end

subgraph sub2 [file 2]
    direction TB
    subgraph noeud1 [ ]
        direction TB
        N12(( :2)) --> N7(l:1):::feuille
        N12 --> N8(z:1):::feuille
    end
    subgraph noeud2 [ ]
        direction TB
        N13(( :2)) --> N90(j:1):::feuille
        N13 --> N10(d:1):::feuille
    end
end
classDef feuille fill:#F88
classDef feuille_resul fill:#FF8
classDef invisible opacity:0
sub1 --> resul
sub2 --> resul
graph RL

subgraph resul [Plus léger]
    direction TB
    subgraph noeud3 [ ]
        direction TB
            IN13(( :2)) --> IN90(j:1):::feuille
            IN13 --> IN10(d:1):::feuille
            IN13:::feuille_resul
    end
end
subgraph sub1 [file 1]
    direction TB
            N5(v:3):::feuille
            N6(o:3):::feuille
            N9(s:3):::feuille
            N2(u:5):::feuille
            N3(e:5):::feuille
            N4(_:6):::feuille
    end
subgraph sub2 [file 2]
    direction TB
    subgraph noeud2 [ ]
        direction TB
            N12(( :2)) --> N7(l:1):::feuille
            N12 --> N8(z:1):::feuille
        end
    subgraph noeud1 [ ]
        direction TB
            N13(( :2)) --> N90(j:1):::feuille
            N13 --> N10(d:1):::feuille
            N13:::feuille_resul
    end

end
classDef feuille fill:#F88
classDef feuille_resul fill:#FF8
classDef invisible opacity:0
sub1 --> resul
sub2 --> resul

Si il y a égalité, c'est l'élément de la file 1 qui sera renvoyé.

graph RL

subgraph resul [Plus léger]
    direction TB
    IN11(q:2):::feuille_resul
end
subgraph sub1 [file 1]
    direction TB
            N11(q:2):::feuille_resul
            N5(v:3):::feuille
            N6(o:3):::feuille
            N9(s:3):::feuille
            N2(u:5):::feuille
            N3(e:5):::feuille
            N4(_:6):::feuille
    end
    subgraph sub2 [file 2]
    direction TB
    subgraph noeud2 [ ]
        direction TB
            N12(( :2)) --> N7(l:1):::feuille
            N12 --> N8(z:1):::feuille
        end
    subgraph noeud1 [ ]
        direction TB
            N13(( :2)) --> N90(j:1):::feuille
            N13 --> N10(d:1):::feuille
    end

end
classDef feuille fill:#F88
classDef feuille_resul fill:#FF8
classDef invisible opacity:0
sub1 --> resul
sub2 --> resul

On assure qu'au moins une des deux files n'est pas vide.

Aide pour créer ses propres tests
Exemple

Si liste_occurrences_triee = [{'caractere': 'l', 'poids': 1}, {'caractere': 'z', 'poids': 1}, {'caractere': 'v', 'poids': 3}]

  • Pour créer des files de feuilles, on fournit la fonction construit_file_caracteres qui prend comme argument une liste triée de dictionnaires dont les clés sont caractère et poids, et qui renvoie une file qui contient des feuilles dont les données sont les dictionnaires de la liste, rangées dans le même ordre.

    occurrences_1 = [{'caractere': 'l', 'poids': 1}, {'caractere': 'o', 'poids': 3}]
file1 = construit_file_caracteres(occurrences_1)
    L'objet file1 contient dans l'ordre Arbre({'caractere': 'l', 'poids': 1}), Arbre({'caractere': 'o', 'poids': 3})

  • Pour créer des files avec des nœuds. Créer des feuilles, éventuellement des arbres puis enfiler les éléments dans des files.

    feuille1 = Arbre({'caractere': 'l', 'poids': 1}) # crée un arbre réduit à sa racine.
feuille2 = Arbre({'caractere': 'o', 'poids': 3})
feuille3 = Arbre({'caractere': 'v', 'poids': 3})
arbre1 = Arbre({'caractere': '', 'poids': 4}, feuille1, feuille2) # crée un arbre avec une racine et deux feuilles
file1 = File()
file1.enfile(arbre1)
file2.enfile(feuille3)

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013,:ag)1ikn9/S=vmsuhb.84;y7e[62odt c0(w]r5_P3plf050F0A0G0d0h0T0q0H0I0T0d0q0q0n010G0h0S010406050q0r0p0p0d0N0y040m0E0T0r0/0E0j050l0_0{0}0 0@0S04181f051i0l1i1k1f0@0F0h0o0%0)0+0-0s0h0e0s0T1y0s0G0=050Y0t0T0A1t0*0,011x1z1B1z0G1H1J1F0G0t0E0F0 1G0N1g0G0s0%120q0S0d0j0-0D011L1v010U0!0A0j0d0p0A1F1-1/1@1N1`1J1}1 0=0a0H0Q0N0E0S0E0q0h150j0H0W1+0N0N0A0I2k18220j1g0l1)2x0G1%1$1(0F240-1B0j1|2h1F1q1s0(1M2H0h2J0j1Z1r1F0S2q1g2v2x2#0^1.2l2P1^2U0N0|0T0=0H0g2u2)0?2(232+1N2-2/2;0D2@1/2_2v2G012~0d2:040H0R322w0@352|0-383a0H0w3e342)363k2;0O3o3g3q3i370E2.392;0C3v2`2*1u2}3A2 3b0z3F3h3I3j3K3C3b0v3O3x3Q3z3B3l0k3W2{3Y3s040g0J3%3H2Q3Z3L0g2?192^3w3(3:3*0g313^331h2Z182N2A0F2E360I1Z201g451j432%402w054a0W2!3X3:0i0=0W0U3o3G360L2;4u3P3|0U0=0S130q0P1J0e0A0N4z4o1^0;040K4M3{2,0=260A3@2%4A4O0=0b3o0H4v3y0j4V1{3 4Z4N1N4P0f0c3v0H4`4)4!1N4q040h4t4i3b4*3)4-1J4Y2^553:0E0=0u4S3/4U040A0q0G0P0o0h0W5g364P0K4@4_4{5x5b1^4 2q0G0r0N17534|4;3j570A4/5a4}0-5d045f535z2}4r0A4W5r3y5t0f5w4`5V0-4 0A1B522#5I4T5W044W5N415P015R5T4:5=5K5j5l5n5p0A5!3Y5$4^53065x5y5{5B0X5E5G5:5*375L595`5J5|5e673|5X5Z5U5{5$5(5;5h4~0=5-0q665H6l4P6a2#6c6d5)5{4,040q0E0{0X0P6o2w6B365R0n4(6l6R4W6Y4n606r5S6t5i6T6V0G6;4=0=5u6_5Q6s6x6q6R0F162J6H5 6C0-5$0B6}010q0g0=002g5p0q007c4P0M6A6e710=6?1 5m5_6Z6l6$6(6Q5L7w6-786/5~5O7r6S6U7u7m6{5%706.5}7c72740A767I6.7a7c7e7g7i0F7k7N047o6b6O6P6q4 517A7J7t6W6,6!3y5R020T0G0x6%6I7B7K6@0P7D6J0=6L3_7/6d6l6g5D5F7@6.6*1{6,7y6 773r6v1{7+6|7.7/8g6E0#7X6p7Z8b7p8y6f0=5C6i8k7F8m1J895{7S7Q8N8t1J8v7P6M184l0A2x2Y8$441r462A2C2y1Y1!2A0d1I8)0l450@8_0X0Z0#04.
Question 2 : construit_arbre(file)
Rappel de l'algorithme de construction de l'arbre. 
Tant qu'il reste au moins deux nœuds dans l'ensemble des deux files:
    prendre les deux nœuds de poids minimal et les retirer de leur file. À poids égaux, les nœuds de `file1` sont choisis prioritairement.
    fusionner les deux nœuds (avec l'étiquette `caractère` égale à `""` et le poids égal à la somme des 2 poids des nœuds précédents)
    ajouter ce nœud à la file 2 des nœuds fusionnés
Renvoyer l'unique nœud, correspondant à l'arbre recherché.

Créer la fonction construit_arbre qui prend comme argument une file file_caracteres, comme ci-dessus et renvoie un arbre de Huffman construit avec la méthode décrite ci-dessus.

La file file_caracteres est supposée triée. Le premier élément qui sera défilé aura le poids le plus petit.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013:,ag)1ikn9}/SA=vFms{uhb.84;y7e[6+2odt c0(w]r5_P3plf050K0E0L0d0h0Y0t0M0N0Y0d0t0t0p010L0h0X010406050t0v0s0s0d0S0C040n0J0Y0v0@0J0j050m0~1012140|0X041d1k051n0m1n1p1k0|0K0h0q0,0.0:0=0w0h0e0w0Y1D0w0L0`050%0x0Y0E1y0/0;011C1E1G1E0L1M1O1K0L0x0J0K141L0S1l0L0w0,170t0X0d0j0=0I011Q1A010Z0)0E0j0d0s0E1K1=1@1|1S1 1O22240`0a0M0V0S0J0X0J0t0h1a0j0M0#1:0S0S0E0N2p1d270j1l0m1.2C0L1,1+1-0K290=1G0j212m1K1v1x0-1R2M0h2O0j1(1w1K0X2v1l2A2C2*0}1?2q2U1}2Z0S110Y0`0M0g2z2.0{2-282:1S2=2@2_0I2|1@2~2A2L01330d2^040M0W372B0|3a310=3d3f0M0A3j392.3b3p2_0T3t3l3v3n3c0J2?3e2_0G3A2 2/1z323F343g0D3K3m3N3o3P3H3g0z3T3C3V3E3G3q0k3#303%3x040g0O3,3M2V3(3Q0g2{1e2}1m2(1d2S2F0K2J3b0N1(251l421o402,3}3805470#2)3$3^0i0`0#0Z3t3L3b0Q2_4r3U3^0j0Z0`470j0t2G0v2o0U120x2v4w4l1}0_040P4M3-4y0`2b0E0U0N120d2x0E2v0t4S3@4O0`0f0b3A0M4;0M4s3D0j4V200U0Z0v2n1b2O4)4f2B4?4x1}0J0`0p3t554N320`0r204*3b4P0P0f4:4=4@3%4n040Q1C1O5b5p4y0x0`2c5i3D5k5C3.4`1O4Y4!4$4(5F3^4P5m533g5x570`0H5w56325z045B5R5T1S5E5%5Y3o5H4X4}4 0j515N4,045Q2,5,015804020e0L0B5@1S0s0h0`3|5{5d0=4P4/5R064=6h5c4T2;0`2Z0E0v0K692}6j4+1S5~5a5R6t3w0`0X180t0U1O0e4%646c0`4R5+6b3c5.5J0S4#0L4%0E526a6k5)0`0c5X6O4_044W4|4~0h506W6J015P5n6i6z4^6m0J6o0K366y5(0=6w6%6Z5-046C4~6F0E6H0S6;5*6Y6u766+4Z6S5L6:6N756=6#747h6P6*4{5:6.5=7n7g5j4-6@6i717u0K6/0E7s3b73705|4P0u6;0t0g0`007k6T6V007e0`6e2*6_3%0t1`0401017#046$7O6O7T7V2l0h0K0t7!7?7p6d7L6`046n6p6r4g5|5~0y6;6)7I7z7K7o7t5k0f0F7S7U04007`7|7~7B5D0`0R823%5~5W7 7t6)856~6;8a8c4o7J7:5l8l8h3b7^8o8q7}7:0R0l7E6h7G6)4J4L8B7M598x4U040o0S4K8g8t3%7f3~5|8d8K8O8u7;8*6l846|867:7=7(8Z6{6}6 8;5O7D6f6^4;967v5I7x6/6X8@6O8H8{5G04214W8L8I048#8:9m809c2*6g5o5|5r0h4q8%3D0J4u900L8~5e9h4X7X7m9l889n0`8b9p8+6W0L0U0q7{9y9W9A4Q4.8X9E6O5r2v0L0v0S1c9J9q7j5K6U5M9!5U049Z9a8 4p5ha26!9.7E7G9?0$9_9{958^6Q9j7z9V2B7G9oa69Qa85vaa6Kac6y9e0|0m4i0E2C2%aE411w432F2H2D1%1)2F0d1NaH0m42aB0#0%0)0t04.
Complement arbre_Huffman(chaine)

Pour créer un arbre de Huffman à partir d'une chaîne de caractères, il faut :

  • déterminer les occurrences
  • créer la file des feuilles
  • créer l'arbre.

Voici un IDE qui permet de tester le résultat, avec vos propres chaînes de caractères. La fonction à utiliser est arbre_Huffman(chaine) qui prend en paramètre une chaine de caractères et renvoie un arbre de Huffman construit. Pour afficher le résultat sous forme d'arbre, utiliser la méthode affiche(). (L'affichage étant textuelle, attention à ne pas mettre un arbre trop grand)

Exemple
>>> arbre = arbre_Huffman("Coucou !")
>>> arbre.affiche()
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier