Aller au contenu

Le codage de Huffman

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 à 4 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. Le caractère espace sera codé par 111, tandis que le caractère l sera codé par 1 0000.

Note

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

Déterminer le nombre d'occurrences⚓︎

Exemple

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
Question 1 : compter_occurrences(chaine)

Écrire la fonction compter_occurrences qui prend en paramètre une chaîne de caractères, et qui renvoie un dictionnaire dont les clés sont les caractères et les valeurs associées le nombre d'occurrences correspondant. La chaîne de caractères est non vide.

Exemple
🐍 Console Python
>>> compter_occurrences("que voulez vous que je vous dise")
{'q':2,'u':5, 'e':5, ' ':6, 'v':3, 'o':3,'l':1, 'z':1, 's':3, 'j':1, 'd':1, 'i':1}

###(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

.128013s3o_8bcdufvg/ly n7apSr1me(P2=4:}+twki][5h{)6050i0z0I0t0L0o0b0q0h0o0t0b0b0D010I0L0u010406050b0j0y0y0t0w0p040v0d0o0j0-0d0r050n0@0_0{0}0=0u04161d051g0n1g1i1d0=0i0L0l0#0%0)0+0P0L0m0P0o1w0P0I0:050W0g0o0z1r0(0*011v1x1z1x0I1F1H1D0I0g0d0i0}1E0w1e0I0P0#100b0u0t0r0+0C011J1t010k0Y0z0r0t0y0z1D1+1-1=1L1^1H1{1}0:0a0q0B0w0d0u0d0b0L130r0q0U1)0w0w0z0h2i16200r1e0n1%2v0I1#1!1$0i220+1z0r1`2f1D1o1q0$1K2F0L2H0r1X1p1D0u2o1e2t2v2Z0?1,2j2N1?2S0w0`0o0:0x2s2%0;2$212)1L2+2-0:0C2;1-2?2t2E012{0t2.040c2 2u0=322_0+35370E3a312%333g0:0O3j3c3l3e340d2,360:0S3q2@2(1s2`3v2|040s3A3d3D3f3F3x040f3j1f2X162L2y0i2C330h1X1~1e3V1h3T2#172=053!0U2Y3s3L010K0:0U0k3R3K2O010J0:0q3|3=3~0r0k0:3!0y0u0I0z0w0e0d0h0h0j2n1`0h0z0b432^3?0/040A4p3C45480P0X2H4v334s0R0F3q0q4I423}2*0:4g4i4k0r4m4o3,304K441?0d0:0D3j4W4q3~4s0Q0G4H4J3B333^040k3v4$4/3t0r480{0t2q4d0z4^4L1L0d40042Q524X2`4y4A514U2u4_4r0:4G5f0;4J5n4%4w1?4;0L3{5l5p3m4|0w4~4c2o594(4Y56585v5h4x044O4j2o4R4n4C3t4s5k2Z065o5X5w4`4N4h5N4l5Q5l5J1?4s0N5R3?4{040h4}4 5C5*530+4s0M5D5q544!5 5x5L5$4Q4S5/4)0:5.5`5a3f5y5A50695,0:5~5I5{014Z040H633t0y0L2/4-5X5+1L4;0z0Z5e2#6o5T6y5Y4I6A6f654P5O686d5E1L5-6j5b5=5@5B6F3-6H6l6t3?6q4#6n6e016v6x5l5W4.6o4;2o0I4j156-6T6N5M675)5V163/0z2v2W773U1p3W2y2A2w1W1Y2y0t1G7a0n3V0=7n0V0X0Z04.

Trier le dictionnaire des occurrences⚓︎

Le codage de Huffman , est basé sur un arbre construit à partir des caractères et du nombre d'occurrences.

Pour cette construction, il est nécessaire d'avoir une liste triée, selon le poids croissant des différentes lettres.

Question 2 : trier_occurrences(dico_occurrences)

Créer la fonction trier_occurrences, qui prend un paramètre, un dictionnaire comme ci-dessus, obtenu comme retour de la fonction compter_occurrences, et qui renvoie une liste triée de dictionnaires dont les clés sont 'caractère' associée au caractère et 'poids' associée au nombre d'occurrences de ce caractère.

Exemple
🐍 Console Python
>>> trier_occurrences({'q': 2, 'u': 5, 'e': 5, ' ': 6, 'v': 3, 'o': 3, 'l': 1, 'z': 1, 's': 3, 'j': 1, 'd': 1, 'i': 1})
[{'caractere': 'l', 'poids': 1}, {'caractere': 'z', 'poids': 1}, {'caractere': 'j', 'poids': 1}, {'caractere': 'd', 'poids': 1}, {'caractere': 'i', 'poids': 1}, {'caractere': 'q', 'poids': 2}, {'caractere': 'v', 'poids': 3}, {'caractere': 'o', 'poids': 3}, {'caractere': 's', 'poids': 3}, {'caractere': 'u', 'poids': 5}, {'caractere': 'e', 'poids': 5}, {'caractere': ' ', 'poids': 6}]

###(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

.128013s3o_8;bcdufvg/0ly n7apS.r1-me,(P2=4:}twki9][5h{)6050j0D0M0v0P0q0b0s0i0q0v0b0b0I010M0P0w010406050b0k0C0C0v0z0r040x0d0q0k0=0d0t050o0|0~10120`0w041b1i051l0o1l1n1i0`0j0P0m0*0,0.0:0U0P0n0U0q1B0U0M0^050#0h0q0D1w0-0/011A1C1E1C0M1K1M1I0M0h0d0j121J0z1j0M0U0*150b0w0v0t0:0H011O1y010l0%0D0t0v0C0D1I1:1=1`1Q1}1M20220^0a0s0G0z0d0w0d0b0P180t0s0Z1.0z0z0D0i2n1b250t1j0o1,2A0M1*1)1+0j270:1E0t1 2k1I1t1v0+1P2K0P2M0t1$1u1I0w2t1j2y2A2(0{1;2o2S1{2X0z0 0q0^0s0A2x2,0_2+262.1Q2:2=2@0H2`1=2|2y2J01310v2?040s0c352z0`382 0:3b3d0s0J3h372,393n2@0T3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0u3I3k3L3m3N3F3e0f3R3A3T3C3E3o0Q3Z2~3#3v040A0p3*3K2T3$3O0A2_1c2{3z3+3?3-0A343{363}3=2/3V3d0A3g433i3J3u480^0A3q4c2A2#0D2A2Q2D0j2H390i1$231j4p1m2$3J2)2{054u0Z2%3!3?0O0^0Z0l3r4e3B0N2@4O3S3 0l0^2V0b0D2t0z4T4I1{0@040F4%3~2/0^0i100v2v4!0D4-461Q4*0E3r0s4P3,0^2j0P0j0b4`394}4 513 0^0d0i0i0k2s1 0i0D0b0e2E0P0D5m583B4*0W0K3y0s5z504U4/045f5h5j0t5l5n5p5r574k5c1{0d0^0y5t52040v0w0w1 0j5U3?4*0F0V5$1{0b0A0^004;0z4?0M4^005+4|0^5x5O5C304:4=4@2t5`0:5a4k065A6a6b6c6d6c5P1Q5-5/54565_5~4(5{045}2*5 3m530d555N6s6o660^0L0W5y5A6g6u042j6y2{5B6A015R040I5b6t3a0h0^2a65015(6Z0t5e5g5i2t5I5m5o0z5q5s6n4.6p6E6=4{0:6Q0B6Z0C0P4h6F5z6H014K040N1A1M6T6O6%6J2k6Z6Q020n0M0g6~70043:4k6N6?6{4R5W0t5#7q747d5F6*5k6-5L6;6z7s6!0^0S6$6v6L36744*0R7L6_396i04006k0b6m7H6`7J040R7b7I7h0q7k7+7%7A6)5H5J6.6:7O2z7Q7K7M7e7{4H7,0^6}7U3B6 71863#7R7T7$7V5.7X7Z7#4D6U7R6r3|6e7z6(5G6+7^7F817}048d8k7c7N6Z7R4~7y6U7=8s7D5K6/5M8D7~8a5d807g847m898e5u0^7*8G6O6Q6S8#7I8I7C6,8L7`8O8y7 6K8T04858X3#883.8:0R8F2(7r7;8r8,8u8M7G8A7I4*8z7P8H8C8Q4)8Z726b8q8S8)7%8%7:3u9f91746|9q877n3`2(064539764M6Z7u509g304W045L0z0e7B7@989d6O6#9J6I9Q8t9S7|8l0^5w9j9l9Y8K7_8N9n399p9/8Y8y8!9A6a74760l3D9w5V5;5?4^9 3?0d7u2Va45D9+8-8:8n448p9e7e6xa91Q9;9tahab5J8:9c9#8B04a1634_9W7(9^8o6d9l4Y4^4$az9V8`8Raw5@64aI0^906M9l7Z8:aR36929r5E7?9Z8.9.aK9h046^9_6G6U762t0M5i1a9=5Vap7E97810`0o4F4n1k4A0o4y2B4r1b2E2D1#1%2D0v1Lb1b41u2|b40!0$0(04.

Construction de l'arbre de Huffman⚓︎

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

Voici un exemple de construction :

Exemple

On commence par créer des nœuds pour tous les caractères. 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

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

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

Ici les nœuds l:1 et z:1 ont été fusionnés en un nouvel arbre dont le poids 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
    N13( :2) --> N7(l:1):::feuille
    N13 --> N8(z:1):::feuille
    classDef feuille fill:#F88

Parmi l'ensemble des nœuds, on choisit les deux nœuds de poids le plus faible, 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
    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 arbre dont le poids sera égal à la somme des poids des nœuds initiaux, c'est à dire à la longueur du message.

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
    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

On poursuit jusqu'à ce qu'il ne reste qu'un seul arbre dont le poids sera égal à la somme des poids des nœuds initiaux, c'est à dire à la longueur du message. Ici on a fusionné deux arbres 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
    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
    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 l'arbre qui avait un poids de 3

graph TD
    N2(u:5):::feuille
    N3(e:5):::feuille
    N4(_:6):::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
    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
    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
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 créer l'arbre, il faut donc créer à partir du dictionnaire des occurrences, une liste ordonnée en fonction du poids du caractère.

L'algorithme de création de l'arbre est le suivant :

📋 Texte
Tant qu'il reste au moins deux nœuds:
    prendre un nœud de poids minimal et le retirer de l'ensemble des nœuds
    prendre un second nœud de poids minimal parmi les nœuds restant et le retirer de l'ensemble des nœuds
    créer un nouveau nœud (sans symbole) et de poids la somme des 2 poids des nœuds précédents
    ajouter ce nœud à l'ensemble des nœuds

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à étaient fusionnés. Si on considère une file_1, construite à partir de la liste des caractères triée par rapport à leur poids, et une seconde file_2, des nœuds fusionnés au fur et à mesure, les deux prochains nœuds à fusionnés seront :

  • Le plus petit des deux nœuds en tête des deux files.
  • Le plus petit des deux nœuds en tête des deux files, après avoir défilé le premier.
  • Si une file est vide, le plus petit est le premier de l'autre file.

On va donc définir :

  • une première file file_caracteres construit avec les nœuds(feuilles) obtenus à partir de la liste ordonnée des caractères en fonction du poids,
  • une seconde file file_fusionnes qui se remplira au fur et à mesure avec les nœuds fusionnés à partir de deux autres.

On fournit la classe Arbre dont un exemple d'utilisation est donné ci-dessous.

Exemple d'utilisation de la classe Arbre

La classe d'arbre binaire proposée permet :

Constructeur : ArbreBinaire() Fonction incluse qui permet de créer une feuille directement : feuille(donnee) Méthodes fournies :

  • est_vide()
  • get_donnee()
  • get_sous_arbre_gauche()
  • get_sous_arbre_droit()
  • est_feuille()
Exemple d'utilisation

🐍 Console Python
>>> t1 = ArbreBinaire()
>>> t1.est_vide()
True
>>> t2 = ArbreBinaire(1, t1, t1)
>>> t2.est_vide()
False
>>> t2.get_donnee()
1
>>> t2.get_sous_arbre_gauche().est_vide()
True
>>> t2.get_sous_arbre_droit().est_vide()
True
>>> t2.est_feuille()
True
>>> ArbreBinaire("coucou",ArbreBinaire(), ArbreBinaire()) == feuille("coucou")
True
On ajoute la possibilité d'afficher un arbre, dont les étiquettes sont de forme {"caractere":…, "poids":…}, sous forme classique pour visualiser le contenu comme dans les exemples ci-dessus.

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

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

Exemple d'utilisation de 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.

Les méthodes :

  • constructeur : File()
  • est_vide()
  • enfiler(x)
  • defiler() : 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.enfiler(10)
>>> f1.enfiler(20)
>>> len(f1)
2
>>> f1.sommet()
10
>>> len(f1)
2
>>> f1.defiler()
10
>>> len(f1)
1
>>> f1.defiler()
20
Question 3 : construire_file_caracteres(liste_triee_occurrences_triees)

Créer la fonction construire_file_caracteres qui prend comme argument une liste de dictionnaires occurrences_triees, résultat de la fonction trier_occurrences, 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.

Exemple de format des paramètres et du résultat renvoyé
  • paramètre : occurrences_triees = [{'caractere': 'l', 'poids': 1}, {'caractere': 'z', 'poids': 1}, {'caractere': 'v', 'poids': 3}]
  • retour : File qui contient dans l'ordre feuille({'caractere': 'l', 'poids': 1}), feuille({'caractere': 'z', 'poids': 1}), feuille({'caractere': 'v', 'poids': 3})

###(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

.128013s3o_bcdufvg/ly napS.r1Fme(P2=4:twki5h)050h0z0G0r0J0n0b0p0g0n0r0b0b0D010G0J0s010406050b0i0y0y0r0v0o040t0d0n0i0%0d0q050m0.0:0=0@0,0s041017051a0m1a1c170,0h0J0k0V0X0Z0#0L0J0l0L0n1q0L0G0*050Q0f0n0z1l0Y0!011p1r1t1r0G1z1B1x0G0f0d0h0@1y0v180G0L0V0`0b0s0r0q0#0C011D1n010j0S0z0q0r0y0z1x1#1%1,1F1/1B1=1@0*0a0p0B0v0d0s0d0b0J0}0q0p0O1Z0v0v0z0g2c101`0q180m1X2p0G1V1U1W0h1|0#1t0q1;291x1i1k0W1E2z0J2B0q1R1j1x0s2i182n2p2T0-1$2d2H1-2M0v0;0n0*0w2m2X0+2W1{2Z1F2#2%0*0C2+1%2-2n2y012=0r2(040c2_2o0,2|2:0#2 310E342{2X2}3a0*0K3d192R102F2s0h2w2}0g1R1^183o1b3m2V112,053t0O2S3f38010I0*0O0j3k371m1F0H0*0p3O3H3Q390j0*3t0q0b2t0i0J2i0e1~0z0e0g0=0r2k0z2i0b3V2/3X010)040A3`2Y3|0q0*0d0g0g0i2h1;0g0z0b0e2t0J0z4d412}3~0M0F3d060p4r3U3P2I2~0*3-3d4t3W4v0d0*0D4z2.424v44040x1:4k3I3~0A0M4p4s4A3{4v3K040j0d0v4G4u2!0*2M0z0i0h4%4B1-0d3S042K4/4W4)0446484a0q4c4e4g4i3_3B2`4H4l0*4o56354U4U583I4K4y5c3G4`1F4D040u4O430*1;3-4$5k5g3|4Q5r4J4x4,0S1B5B1-5A5x4(2;4*0d4,4.5K4:1F4m4S5k4q4s5y4X0*2i0G490 5k4V4I4{5j2T0,0m3E0z2p2Q5?3n1j3p2s2u2q1Q1S2s0r1A5_0m3o5:0O0Q0S0b04.
Question 4 : plus_leger(file1, file2)

Créer la fonction plus_leger qui prend comme arguments deux files, dont les éléments sont des dictionnaires {'caractère': valeur, 'poids': valeur} et renvoie l'élément avec le poids le plus faible, en le défilant. Si l'une des files est vide, c'est le sommet de l'autre file qui est renvoyé. On supposera qu'au moins une des deux files n'est pas vide.

Exemple de format des paramètres et du résultat renvoyé
  • paramètre : Deux files qui contiennent des nœuds dont la donnée de la racine est un dictionnaire {'caractere': …, 'poids': …}
  • retour : un nœud dont dont la donnée de la racine est un dictionnaire {'caractere': …, 'poids': …}
Aide pour créer ses tests

Pour créer des files avec des nœuds.

Créer des feuilles, éventuellement des arbres puis enfiler les éléments dans des files.

🐍 Script Python
feuille1 = feuille({'caractere': 'l', 'poids': 1})
feuille2 = feuille({'caractere': 'o', 'poids': 3})
file1 = File()
file1.enfiler(feuille1)
file2.enfiler(feuille2)

###(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

.128013s3o_8;bcdufvg/ly n7apS.r1me,(P2=4:twki9][5h)6050j0B0J0u0M0p0b0r0i0p0u0b0b0G010J0M0v010406050b0k0A0A0u0y0q040w0d0p0k0.0d0s050o0^0`0|0~0?0v04171e051h0o1h1j1e0?0j0M0m0$0(0*0,0R0M0n0R0p1x0R0J0;050X0h0p0B1s0)0+011w1y1A1y0J1G1I1E0J0h0d0j0~1F0y1f0J0R0$110b0v0u0s0,0F011K1u010l0Z0B0s0u0A0B1E1,1.1?1M1_1I1|1~0;0a0r0E0y0d0v0d0b0M140s0r0V1*0y0y0B0i2j17210s1f0o1(2w0J1$1#1%0j230,1A0s1{2g1E1p1r0%1L2G0M2I0s1Y1q1E0v2p1f2u2w2!0@1-2k2O1@2T0y0{0p0;0z2t2(0=2%222*1M2,2.0;0F2=1.2@2u2F012|0u2/040c302v0?332`0,36380H3b322(343h0;0Q3k3d3m3f350d2-370;0T3r2^2)1t2{3w2}040t3B3e3E3g3G3y040f3K3t3M3v3x380N3k1g2Y172M2z0j2D340i1Y1 1f3%1i3#2$182?053,0V2Z3T2P010L0;0V0l3Z3L3~0K0;0r443}2+0l0;0v120b0e1I0n0B0y4a2_3U0:040D4n3D3~0s0;250B2;3@313C344q0C3k49452+4x1`2 4B2v4D3u4q0S0I3r0r4W4I4b1M40040M434O044Y4o4v4L1I4A2$4J1M0d0;0x4t3n0;0B0b0J0e0m0M0V4`4R0;0D4T4V4X5a4Q3U4#2p0J0k0y164)4+4u4K044y4N4;4Z0,4@044_4)5c4-04421`4m5x4=0,4q57594W5y1@4#0B1A4(2!5l4{5o4M543U5u5w5r4,5n4}4 51535E5s015H584)065a5b5F3 0;5f5h5j5R5L2{4.4z5W3~5Y625n5B1I5D5!5m1M5.5J5S3u5N5P4H5~3g604:3^5@645+5#5 040b0d0`0W656c560S6z5t4^6D350;4k4 0j152I0B6G5.0P6G0b0z0;002f520b006P0;0O6j6p0;020p0J0g0G6(5,4w5U1I5q6o5,6q6a5T6v6x0J6#4r6C6r6b6E5v6G6=6J0e6L0s6N71576R74346T6V6X0j6Z710O4U5:5=4X6k5^045`5i6:6s6l6?617i3u6{6_7B6H5A0B4y697I755-6B6e7v6h0b6O7F4p0;7r2!5;7t6f5d5_0W5{7A7Q6=5p6G7H4C5@6=674l7f737$173`0B2w2X813$1q3(2z2B2x1X1Z2z0u1H840o3%0?8h0W0Y0!04.
Question 5 : construire_arbre(file)

Créer la fonction construire_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.

###(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

.128013s3o_8;bcdufvg/ly n7ABapS.r1Fme,(P2=4:+}twki9][5h{)6050j0E0O0w0R0p0b0r0i0p0w0b0b0J010O0R0x010406050b0k0D0D0w0A0q040y0d0p0k0@0d0s050o0~1012140|0x041d1k051n0o1n1p1k0|0j0R0m0,0.0:0=0W0R0n0W0p1D0W0O0`050%0h0p0E1y0/0;011C1E1G1E0O1M1O1K0O0h0d0j141L0A1l0O0W0,170b0x0w0s0=0I011Q1A010l0)0E0s0w0D0E1K1=1@1|1S1 1O22240`0a0r0H0A0d0x0d0b0R1a0s0r0#1:0A0A0E0i2p1d270s1l0o1.2C0O1,1+1-0j290=1G0s212m1K1v1x0-1R2M0R2O0s1(1w1K0x2v1l2A2C2*0}1?2q2U1}2Z0A110p0`0B2z2.0{2-282:1S2=2@0`0I2{1@2}2A2L01320w2^040c362B0|39300=3c3e0K3h382.3a3n0`0V3q3j3s3l3b0d2?3d0`0Z3x2~2/1z313C33040t3H3k3K3m3M3E040f3Q3z3S3B3D3e0S3q1m2(1d2S2F0j2J3a0i1(251l3-1o3+2,1e2|053=0#2)3Z2V010Q0`0#0l3)3R440P0`0r4a432;0l0`3=0s0b2G0k0R2v0e120h2v4g2 3!0_040G4w3J440s0`2b0E0e0i120w2x0E2v0b4C3a4z0Y0L3x0r4X4f4b2;4G200e0l0k2n1b2O4Q3}374Z4h1S0d0`0J3q4;4x4E0`0C204R3A4z0G0Y4W4Y3I3a46040P1C1O4`583A0d4d042Z0O5f4!314$1O4J4L4N4P513!4@040z5w4}040E4n0e0m0R0#5B1}53554/2B4{4D1}5i0`3C5n4=3m0h0`2c5K1S535$3m5q4I4)4+0s4-5)014T5;5y020n0O0g5;0D0R2_5;4z4V5O0{4Y665Q3t0`2Z0E0k0j2`64685h4^5W4|4#040x180b0e1O0n4O610`4B645g3!4F044H5s0A4M0O4O5E6v040F6k5R5p6C4%5-0R4,6J6y5o0=5?640667576X3b6a0d6c0j356g6z445y4_6/6(6B6o4*6r0E6t0A6K6x2,6^5+6E6G6I4.725X5=0`6M6@7a6B6D6S6U783~6(6Z2*6#6$6h6A476U0E6N3a6=7w520`0X5;0b0B0`004K6F5u0E006K632*7r440b1`0401016K7d7P6:1}7E7G2l5I0b7M7e6l5%0`7O2|7Q6m6b6d6f797-0=5y5A6W7f0`6t0O0e0j7u700Y0U7D7F04007(0j7*6K0T7z5x0`0M8j5C7@6-5@0`7~7`6O5*048284867 7{7b4A888a7%0d7)7+8u4S0`0T0N566$7!6P4t4v7,8v017y8W69040u0A4u0E0v2X0(8V8L7A4A5;6B855/0E7v8B8X4z7Y7;8S8w8p7_7l7a8}8n7?6+6d6.8/4y0`5N7o7q7=6P7h4*6T8^7k37908Y8s8=0`214H6 8{8M8;9y3A6B8U8`9c447n2|7p4X9q5a2v0O0k0A1c8!9C747i9n8r5z9t0448209x9G5L6w9f9J1d400E2C2%9:3,1w3.2F2H2D1%1)2F0w1N9?0o3-0|a30$0(0*04.
Question 6 : arbre_Huffman(chaine)

Enfin, créer une fonction arbre_Huffman qui prend comme argument une chaîne de caractères et qui renvoie un arbre de Huffman.

###(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

.128013sH3o_bcdufvg/ly napSr1me(P2=4:twki5h)050i0y0F0s0I0o0b0q0h0o0s0b0b0C010F0I0t010406050b0j0x0x0s0v0p040u0e0o0j0$0e0r050n0-0/0;0?0+0t040 1605190n191b160+0i0I0l0U0W0Y0!0K0I0m0K0o1p0K0F0)050P0g0o0y1k0X0Z011o1q1s1q0F1y1A1w0F0g0e0i0?1x0v170F0K0U0_0b0t0s0r0!0B011C1m010k0R0y0r0s0x0y1w1!1$1+1E1.1A1;1?0)0a0q0A0v0e0t0e0b0I0|0r0q0N1Y0v0v0y0h2b0 1_0r170n1W2o0F1U1T1V0i1{0!1s0r1:281w1h1j0V1D2y0I2A0r1Q1i1w0t2h172m2o2S0,1#2c2G1,2L0v0:0o0)0w2l2W0*2V1`2Y1E2!2$0)0B2*1$2,2m2x012;0s2%040d2^2n0+2{2/0!2~300D332`2W2|390)0J3c182Q0 2E2r0i2v2|0h1Q1@173n1a3l2U102+053s0N2R3e37010H0)0N0k3j361l1E0G0)0q3N3G3P380k0)0;0g2h0f0c0j0k0k0:0r0~3A2_2-2X3W010(040z3U2.3?0r0)0h0K0Q2A3{3=2H3@0)0L0E3c060q4d3T3O463~040e0h0h0j2g1:0h0y0b3c4f3V460e0)0C4t3;3f0)2s0I0y0v0f4k4m4o0r4q4s3/2n4B3H3^3`4P3F3|4h3 0e0x0t0F4G4I4l4n2h4M4r442|4T4/3H4i40420y4=3?3^0L0L4b4e4u4X2Z0)1}0y0f0h0;0s2j4G4.4V52451,4x044z5f4R3}4Z0r0b2s0j0I3$56585a5c2h4O2U4g1,4;4V5n4Y4j4*4L4N4{464}504e5H54043!2h4A5D1E5j5l2S5g4C043s5q5s5u575V4`5G5Y0!5F5C4v5T5w590v5b4%5A5N5E485Q4d5S1E3J042h0F4n3.5$66383Z0v3#5:2S0+0n3D0y2o2P6p3m1i3o2r2t2p1P1R2r0s1z6s0n3n6m0N0P0R0b04.

Encodage⚓︎

Une fois l'arbre construit, il faut procéder à l'encodage du texte. Pour cela on va créer un dictionnaire, dont les clés seront les caractères et les valeurs associées le codage binaire du caractère en utilisant l'arbre construit.

Pour cela on va utiliser la convention suivante :

Dans l'arbre chaque embranchement à gauche correspond à 0 et chaque embranchement à droite correspond à 1.

Exemple d'arbre et de codes

On obtient l'arbre suivant :

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


graph TD
    N22( :32) --> |0| N20( :12)
    N22 --> |1| N21( :20)
    N20 --> |0| N16( :6)
    N20 --> |1| N17( :6)
    N16 --> |0| N5(v:3):::feuille
    N16 --> |1| N6(o:3):::feuille
    N17 --> |0| N9(s:3):::feuille
    N17 --> |1| N14( :3)
    N14 --> |0| N1(i:1):::feuille
    N14 --> |1| N11(q:2):::feuille
    N21 --> |0| N18( :9)
    N21 --> |1| N19( :11)
    N18 --> |0| N15( :4)
    N18 --> |1| N2(u:5):::feuille
    N15 --> |0| N12( :2)
    N15 --> |1| N13( :2)
    N12 --> |0| N7(l:1):::feuille
    N12 --> |1| N8(z:1):::feuille
    N13 --> |0| N90(j:1):::feuille
    N13 --> |1| N10(d:1):::feuille
    N19 --> |0| N3(e:5):::feuille
    N19 --> |1| N4(_:6):::feuille
    N5 o-...-o N32[000]:::binaire
    N1 o-..-o N33[0110]:::binaire
    N4 o-...-o N30[111]:::binaire
    N7 o-.-o N31[1 0000]:::binaire
    classDef feuille fill:#F88
    classDef binaire fill:#FF0
Par exemple, l (peu fréquent) sera codé 1 0000 (5 bits) alors que l'espace (très fréquente) sera codée 111 (3 bits).

Plus un symbole est fréquent, plus il est proche de la racine :

Question 7 : lettre_binaire(arbre)

Créer la fonction lettre_binaire qui prend comme argument un arbre de Huffman et qui renvoie un dictionnaire avec comme clé, les caractères et comme valeurs associées, le codage binaire du caractère.

###(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

.128013s3o_8bcdufvg/0ly n7apS.r1Fme,(P2=4:}+twki9][5h{)6050i0C0M0u0P0p0b0r0h0p0u0b0b0H010M0P0v010406050b0j0B0B0u0y0q040w0d0p0j0=0d0s050n0|0~10120`0v041b1i051l0n1l1n1i0`0i0P0l0*0,0.0:0U0P0m0U0p1B0U0M0^050#0g0p0C1w0-0/011A1C1E1C0M1K1M1I0M0g0d0i121J0y1j0M0U0*150b0v0u0s0:0G011O1y010k0%0C0s0u0B0C1I1:1=1`1Q1}1M20220^0a0r0F0y0d0v0d0b0P180s0r0Z1.0y0y0C0h2n1b250s1j0n1,2A0M1*1)1+0i270:1E0s1 2k1I1t1v0+1P2K0P2M0s1$1u1I0v2t1j2y2A2(0{1;2o2S1{2X0y0 0p0^0r0z2x2,0_2+262.1Q2:2=2@0G2`1=2|2y2J01310u2?040r0c352z0`382 0:3b3d0r0I3h372,393n2@0T3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0t3I3k3L3m3N3F3e0f3R3A3T3C3E3o0Q3Z2~3#3v040z0o3*3K2T3$3O0z2_1c2{3z3+3?3-0z343{363}3=2/3V3d0z3g433i3J3u480^0z3q4c3s3~473%4h3x4k454f4o3.3H4k1k2$1b2Q2D0i2H390h1$231j4B1m4z2*4x4G0Z2%3!3?0O0^0Z0k3r4e3B0N2@4Y3S3 0k0^1M1W2t0e0g2V0$2t4%4S1{0@040E4@4m300^100g4?4x4(4_0^0W0J3y0r5b0r4Z3,0^4P0C0b3r5d551Q0d0^0H5k5e3?4`0V0K5a5c5s2/5g4H5r5m0:5o045q4k5l4^1Q0b1^0401015x5b5z4 04290C5D5L5F5p5Z4~3m0^0A1~4}461Q4`0E0W5S5K5(3a0^5X5-395G0x5|3B0s0^1 5X0y603#5:4|545!5_0451532*5E014`0D5%5.5)045h675t575=4r5c5@6n014U040N1A1M6m5}4#042X0M6F615`5,6b5^5~6r5A045i0M0e0l0P0Z6S5/0^5;596v6w5y6i62040y0u0h2V5Y6P6y6k6#6o6q5J5U5#5H6L5f5W6O6h6c6R6^3u4V0C656{6j6%6u2(066+6,6c6A0P4X6~6-0^6:6=2M7e78765^6.6V0e0k0C0j0%6E793B5:585?7k5T7r6p106;0M0C6g2{6x5}5$7q6c6.7t6?7w0^5 7I730m0!0e0i192M6@7y6_7g0S7e5N0^010h7R2v7U237e4`0R7M7N6 6d5h5j7,6s047{8e6T807t7T7V368a86723?5G5I2(7X6M6p5C6*7k8a6A0C0(7@2{8p0^6)7i7N6+8a6.0m0u0j0h0U8G368w3#8t8r6T7%7v8i5n7*7e8P7/0b0d0j0b0e6f0C0e8Q8S8U857g888B7P0i2h2m8!8)717!7z7s6;7(8(707+7^7a047.6W8.8:8=0y528@910d939c7f4{7h3|8M6w8O6N7H9f3B7x8H7P641~669t698+0^8_8T8V2z8I046l976y6.6}8v8a5G0L940:7}5P0o5R9L6t8~8N7P5{9t9F8o9H0s7d9.4{6a9D739q9sa08f9V9!7P9Z7W9#0^9%9W399*010z9-a456040W9w449z6i6A2t0M0j0y1aae8x8c3I0n5h2A2#0C2A4K2B4D1b2E2D1#1%2D0u1LaG4A1u2|0n0Z0#0%0b04.
Question 8 : encoder_texte(texte)

Il faut maintenant encoder le texte initial avec ce code obtenu.

Créer la fonction encoder_texte qui prend comme argument un texte et qui renvoie une chaîne de caractères contenant le codage binaire du texte.

L'arbre de Huffman est créer au début de la fonction, ainsi que le dictionnaire de codage.

###(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

.128013sH3o_bcdufvg/ly n7apS.r1me(P2=4:jtwki][5hx)6050i0A0I0t0L0o0b0q0h0o0t0b0b0E010I0L0u010406050b0j0z0z0t0x0p040v0e0o0j0-0e0r050n0@0_0{0}0=0u04161d051g0n1g1i1d0=0i0L0l0#0%0)0+0P0L0m0P0o1w0P0I0:050W0g0o0A1r0(0*011v1x1z1x0I1F1H1D0I0g0e0i0}1E0x1e0I0P0#100b0u0t0r0+0D011J1t010k0Y0A0r0t0z0A1D1+1-1=1L1^1H1{1}0:0a0q0C0x0e0u0e0b0L130r0q0U1)0x0x0A0h2i16200r1e0n1%2v0I1#1!1$0i220+1z0r1`2f1D1o1q0$1K2F0L2H0r1X1p1D0u2o1e2t2v2Z0?1,2j2N1?2S0x0`0o0:0y2s2%0;2$212)1L2+2-0:0D2;1-2?2t2E012{0t2.040d2 2u0=322_0+35370F3a312%333g0:0O3j3c3l3e340e2,360:0S3q2@2(1s2`3v2|040s3j1f2X162L2y0i2C330h1X1~1e3N1h3L2#172=053S0U2Y3s3D0+0K0:0U0k3J3d3+010J0:0q3;3*2O340k0:1`3%0A0x0f0I0A0Q463{2^3?0/040B4a3C3}0r0:46480A4g334d0R0G3q0q4u3`3=4i0:0{0g2o3j4w3|1?0e0:0E4D3B3m4z0x4B0A0f0c0j0k0k0`0r153!304L3t4d4f4Z2u4#3?4j044l494)3)4b3}4q4t4v4+4y043%0t0m4n4;4E4?4G4I4K4x2*0:1H1R2o0f0g2Q0X4C4;4{1?4%4o3t4-4A5i2#581L4^4;064v534h594.47460f42574F1L4H044J525k5u0:0N0M4_4u5O3,0:0k3v5H542`0:0h0{0t2q43512Z5z330e3^042Q5!5A5$5C4m5n4c0:4s5w5y5y5V344k5D4Q5G5j5t0+5K0w5}4|0t0u0u1`0i6f5l0:4(5s5I3f5%1X4 5-3#6b014d0N6m5`5(0x5*465r6x6r6z0:0M0R5T5/3t3-042o0I0j0x4Y5.640b1:0401016C6c0:6e6a6K4-0H0e5@6.5#0+5m6@5_6s5{5E696q6^6L046O5w16422v2W0A2v3W2w3P162z2y1W1Y2y0t1G7b3M1p2?0n0U0W0Y0b04.

Remarque

Pour l'exercice le codage est « textualisé », alors que, dans la réalité, l'opération se passe au niveau des octets et est donc plus difficilement visible.

Décodage⚓︎

Question 9 : decoder_texte(texte, arbre)

Créer la fonction decoder_texte qui prend comme argument un texte codé et l'arbre de Huffman , et qui renvoie une chaîne de caractères contenant le texte décodé.

Le décodage du texte se fait en parcourant l'arbre. On s'interdit d'utiliser et ou de reconstruire le dictionnaire de codage.

###(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

.128013s3o_8;bcdufvg/0ly n7apS.r1-me,(P2=4:+jtwki9][5hx)6050j0D0N0v0Q0q0b0s0i0q0v0b0b0I010N0Q0w010406050b0k0C0C0v0z0r040x0d0q0k0?0d0t050o0}0 11130{0w041c1j051m0o1m1o1j0{0j0Q0m0+0-0/0;0V0Q0n0V0q1C0V0N0_050$0h0q0D1x0.0:011B1D1F1D0N1L1N1J0N0h0d0j131K0z1k0N0V0+160b0w0v0t0;0H011P1z010l0(0D0t0v0C0D1J1;1?1{1R1~1N21230_0a0s0G0z0d0w0d0b0Q190t0s0!1/0z0z0D0i2o1c260t1k0o1-2B0N1+1*1,0j280;1F0t202l1J1u1w0,1Q2L0Q2N0t1%1v1J0w2u1k2z2B2)0|1=2p2T1|2Y0z100q0_0s0A2y2-0`2,272/1R2;2?2^0H2{1?2}2z2K01320v2@040s0c362A0{39300;3c3e0s0J3i382-3a3o2^0U3s3k3u3m3b0d2=3d2^0Y3z2~2.1y313E333f0u3J3l3M3n3O3G3f0f3S3B3U3D3F3p0R3!2 3$3w040A0p3+3L2U3%3P0A2`1d2|3A3,3@3.0A353|373~3?2:3W3e0A3h443j3K3v490_0A3r4d3t3 483(4i3y4l464g4p3/3I4l1l2%1c2R2E0j2I3a0i1%241k4C1n4A2+4y4H0!2(3#3@0P0_0!0l3s4f3C0O2^4Z3T400l4W2v4I0z0e0N0D0W4;4(4T1|0^040F4^4n310_4;4?0D4~471R4{0E3s0s4!3-0_110h2u553a4{0X0K3z0s5o5b4)2:514=4;0e0!4Q544l5q4_1R0d0_0I5a5c3@4{0T0S5n5p5I5s040z0v0i2W5z2)5B4 0;5E045G5A5P50045f5h4s5p5Y563n0_2k0b5H5r5D5F5_5C0;0C0Q0_3;5.5O5`0;4V040O1B1N5}5Z3b5?2l6d5;015#020q0N0g6i3v0h0_2b5i3C4{4}4y666f04524@6z5~015k5m645/5o5)670_0Q4Y5(6A0t5e0z5g5W2|6N6k0_0y6v5d040D0b0N0e0l0D0k0(6c6F6e6x5l5N6L6L6!6U6C5u0D5w4-0!6(3@5#6%6@6j6 0v0w0w200j764`0_6y2+6T6V6X7i5{04797m6G6 0n0#5w1a2N6Y376!6_0T7q0;0b1_04010i115T4;2u017H6H0_0S0X6{6|657v7o5-5X6!5#5%7(7n5R5T5V7Y7Z5:3v6g5^6S6G7*6q3C6 5@7}3$5#0B813@604i7;7!6e680D1F6R7,7#70537T5K7T7 6h7a5j7V851|7*7+2|7?3C7J0_010p7S8p6w0_6J2)067=5/6~7$7C2A8x825|7`6e7c6W7%6Z6A788m0_7x6-0b0d0k0b0e5,720n0v0k0i0V8O4S6^7k7X6K6}6A8c0)8^7E8G896|8M5+8W8^8Q778S8g8U8N7T8!8E6)8%0e8)8+8-995w2i2n8k8{959b5Q808T6j7|9A7@049z9e9B0_0L8s1R873/7Y976D725x4I9h6$8#5+7e7g9u4|9X8.9V7s9X9l0j7A0D926A7F7T8z7L7N5S2w0D7R9#7W9P8 0_2u0N0k0z1b9D8y7K018D7u6e9iad7b0_0M0d2W9#7l8Y8h9R735y9#8|8I1c5y2B2$0D2B4L2C4E1c2F2E1$1(2E0v1MaA4B1v2}0o0!0$0(0b04.

Remarque

En pratique, le dictionnaire de codage est transmis dans le fichier avec le texte à décoder. Il faut d'abord reconstruire l'arbre, avant de décoder les données.