Aller au contenu

Le code de Huffman et Shakespeare

1. Fonctionnement : le code de Huffman⚓︎

Le code de Huffman est un algorithme de compression sans perte qui permet de représenter un texte de manière plus compacte en utilisant des codes binaires de longueur variable.

Principe :

  • Les caractères frĂ©quents reçoivent des codes courts
  • Les caractères rares reçoivent des codes longs
  • Les codes sont prĂ©fixes : aucun code n’est le dĂ©but d’un autre.

Cela permet de décoder le message de manière non ambiguë.

L’algorithme fonctionne en trois étapes : 1. Calcul des fréquences de chaque caractère 2. Construction d’un arbre de Huffman 3. Déduction du code binaire de chaque caractère

Pour le texte de Shakespeare, nous allons construire le grand arbre suivant:

2. Récupération du texte de Macbeth⚓︎

Python
1
2
3
4
with open("macbeth.txt",'r') as f:
    contenu = f.readlines()

texte = "".join(contenu) # join sert à concaténer les chaines d'une liste en ajoutant "" entre chaque élément
###(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 : 5/5
.128013it3advn{2S5wbcy+14: f-up8)_}eklohxrP=[s6(]/mg7050f0D0c0e0b0F0N0u0o0F0e0N0N0L010c0b0y010406050N0x0S0S0e0J0p040k0G0F0x0/0G0h050R0_0{0}0 0@0y04051f181i0R1f0@0f0b0g0%0)0+0-0)0h0T0x0e0T0D0w0y0p0c0H160u0H0b0T0H0F1K0H0c0=050Y0n0F0D1r0*0,011J1L1N1L0c1T1V1R0c0J1g1F0%120N0y0e0h0-0j011X1t010v0!0D0h0e0S0D1R1?1^1}1Z201V23250=0a0u0K0J0G0y0G0N0b150h0u0W1;0J0J0D0o2q18280h1g0R1F2D1-1/1.1S0f2a1u0b0h222n1R1o1q0(1Y2N2P0h0G2T1R0y2w1g2B2D2*0^1@2r2V1~2Z0J0|0F1R0e1I2w0v0-030B0B0o2!0D1N2Y0G0w0r380=0r180e2+2.0?2-292:1Z2=2@2_2{0D2}012 3133352Q380w1{040j3d3f1^3h2B2M013m0e2^1g2`0H2|2~30320W3w2Z3y0d0=0d3D2A3g0@3H3k0-3K3M053O3Q3s3S3v2O3x390s0=0s3#193%3i2/1s3l0G2?3L3o3P3q3R3u3U3@3W390l0=0l3}2*3(2.3I3,473:3t3T344d37390O0=0O4j3 3)423+443n3N3p3r4r3?363y0U0=0U4A3F4l3j4D3J4F464H484J3=4c4M390z0=0z4R2C1j2(182T2G0f1/2L3*014s2S1p1g2%0D2)3g3$3F054s52290b0f0-302B3y0r3o5a5c4b4t4(3a0u2e0D5j4s3V4v3a2D3e403I0E0=0W0v544.4C2W010m0=0u5E58415H0h0v0=0G0o0o0x2v220o0D0N5M5y4`0;040P5$5G2;0=0c0D0I5:5,4m5(0=0A0t5M0@3~553H5i015d2.3y3A3.0u624$5l3^3z1|5p5r4L6d670R3e0u6n5L5-3l0=0o0}5M6p5^4V0G0=0L6v5%4V5)0i0C5}5@595b630B5e393Y4H6a5k5t3X6f245q6M5s4u6V5w046o6w4U5H5A040v446C6q3+6s6;6x5H0G5J042O6^6+5.045:5=0D6J5O1~5)5|5 2C5~2,616L641^3y3`6R7g6T6#3_6W256h4%6d7k3D6)6)6D6,0=0b5D7b6(7z710o6 771Z6{7B177E6*7K6?046t0J763I796I7E5y6S6O0w4g7l7s6c4e7(7q6Y6b6U4f1R6l6(7x7`7G6r7T6u7!6=015)0M7W4`0h6@806_780=0Q7J3I6z040q6B7P7|0-0S0b3b7Z7e4m7$654w5h7m6!5m4x5o6X7+7=0w4x6%7`6n8l016-340N7589701Z7Y7E7d537f5j7%4O7*6Z6i7-4O8B7r8$7t8(7@6m8I7y81877~7V8Q7R820=848`4n888r8R0-5)8d8k818g8j2*7Q3I8n8p8U7W8t7i4)8w8D7o0w4*8*7:7n5m4*8H6o8K6-2w0c5W7O9b8K8@7U8q530R574/514;4~180c4@9P2J2E0e1U9M0R4=5~0W0Y0!0N04.

Pour Macbeth, on obtient :

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
occ = {
'A': 915, 'C': 571, 'T': 939, ' ': 25653, 'I': 666, '.': 1625,
'\n': 3863, 'S': 433, 'E': 603, 'N': 320, 'n': 4690, 'o': 5704,
'p': 960, 'e': 8609, 'l': 2981, 'a': 5118, 'c': 1580, '[': 174,
'h': 4801, 'u': 2390, 'd': 2942, 'r': 4224, 'i': 4007, 'g': 1222,
't': 6139, 'W': 449, 's': 4519, ']': 174, 'F': 299, 'R': 305,
'H': 460, 'w': 1488, 'm': 1840, ',': 1700, '?': 235, 'O': 348,
'D': 407, 'y': 1506, 'b': 1045, "'": 685, 'f': 1401, 'U': 195,
'M': 637, 'G': 106, 'k': 665, '!': 222, 'P': 51, 'L': 334,
':': 328, 'v': 635, 'K': 28, 'x': 94, ';': 374, 'q': 80,
'B': 410, 'j': 36, 'Y': 137, 'z': 16, 'X': 22, '-': 122,
'"': 52, 'Q': 36, 'V': 22, '&': 2, '(': 1, ')': 1, 'J': 2
}

3. Création d'un classe Code⚓︎

La classe Code sert à représenter un sous-arbre dans la construction de l’arbre de Huffman. Chaque objet contient deux informations principales :

v : le poids du sous-arbre, c’est-à-dire la somme des occurrences des caractères qu’il contient.

cs : un dictionnaire des codes binaires associés aux caractères présents dans ce sous-arbre.

Ainsi, un objet Code représente à la fois un groupe de caractères et les codes binaires provisoires qui leur sont attribués pendant la construction de l’arbre de Huffman.

A l'initialisation les caractères seront placés dans des arbres racines sans code.

Exemple:

Python
1
c = Code(2, {'J': ''})

Cette classe comporte deux méthodes :

  • add_bit : ajoute un bit ("0" ou "1") au dĂ©but de tous les codes des caractères contenus dans l’objet.
  • join : permet de fusionner deux sous-arbres, ce qui correspond Ă  l’étape principale de l’algorithme de Huffman : on combine les deux nĹ“uds de plus petit poids. L'attribut v devient Ă©gal Ă  la somme des deux attributs v correspondants. L'attribut cs devient un dictionnaire contenant les codes des deux objets (après avoir Ă©tĂ© prĂ©fixĂ©s, l'un par "0", l'autre par "1"

Exemple:

Python
1
2
3
4
c = Code(7, {"a": "10", "b": "11"})
c.add_bit("0")
c.cs
>>>{"a": "010", "b": "011"}

join sera appelé après avoir appelé add_bit sur self avec "0" comme argument et sur other avec "1" comme argument.

###(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 : 5/5
.128013Cit3a;dv,n2.S5wbcy+14q: f-up08)_j9eklohrP=[s6(]/mg7050h0J0d0f0c0L0S0y0r0L0f0S0S0Q010d0c0C010406050S0B0X0X0f0O0s040n0M0L0B0@0M0k050W0~1012140|0C04051k1d1n0W1k0|0h0c0i0,0.0:0=0.0k0Y0B0f0Y0J0A0C0s0d0N1b0y0N0c0Y0N0L1P0N0d0`050%0q0L0J1w0/0;011O1Q1S1Q0d1Y1!1W0d0O1l1K0,170S0C0f0k0=0l011$1y010z0)0J0k0f0X0J1W1{1}221(251!282a0`0a0y0P0O0M0C0M0S0c1a0k0y0#1_0O0O0J0r2v1d2d0k1l0W1K2I1=1@1?1X0h2f1z0c0k272s1W1t1v0-1%2S2U0k0M2Y1W0C2B1l2G2I2/0}1|2w2!232(0O110L1W0f1N2B0z0=030G0G0r2)0J1S2%0M0A0o0A0u0`0y0u1d0f2:2?0{2=2e2^1(2`2|2~300J32013436383a2V3d0A20040y0l3k3m1}3o2G2R013t0f2}1l2 0N313335370#3D2(3F0e3h0e3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0v3h0v3-1e3/3p2@1x3s0M2{3T3v3X3x3Z3B3$3 3(3e0o3h0o452/3:2?3Q3@4f3{3A3#394l3c3e0T3h0T4r473;4a3?4c3u3V3w3y4z3~3b3F0Z3h0Z4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0E3h0E4Z2H4#492#4(4d3^3`4h3|4j4B4:0A0I3h0I4^3O4u3=4}4O3_4Q4i4A3%4D3f0D0`0u0D5a4`4v4)4 5h525j4C3F0u3g045B5r485t4~4x514S4/403f3H0u3K0W3l3.4!5G5d4w4+4y4.545N0u3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550u4F5D4H6b4s5/616g5Z5K5#663e0u4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D3N1o2-1d2Y2L0h1@2Q5d4A2X1u1l2,0J2.3n5~1l4A6+2e0c0h0=352G5A3v6=6@6K6k212j0J6}6j5%1W5}6e1(0K0`3r6-6r230p3h7d783?0r0`0b387i6F4|0_040x6-0|6c2H5G6|016^2?3F3H5g7A6w6L3G7029727B6~5N7F5,0y7T0y7e790`0#0z7p4$4|7g3I7#4{230z0X0`352T2u357*3Q7s0U7@5d0q7s0S397!7x6:7+1(7s0j6-7V7j3R0`0i3T0B0J7{4%86887W3?7b0N127 0d8h7r0`0F7u827w2;3P7H0G6_3e5)7G6?7O744m0A3*0y71735^8K8F7S7U8U8l017}0`7 0L818z7q230M0`0m8s2_8c8k8a8*040Q8:8(3s8c8e8g8x7@8B8D0A5`8G8P5M8K428N7M955$97763l8U8V8a8Y048!8$6,8;8+8-8`040r0S8^7$8)0`8@82898_8m9s8o0O8q7v8 8H7C1}3F68948I8Q5l4o992a9b6x3d9e3o827z9K8C7D4E6{9%8J5l4F9U7N7I556m3L9h9C010r5C030y0f0H0M191#0B2w0q2u9 0y0Y0f0B0r0N1#2 0da20d0y1!0+4A9u8~9#8A9%916A9P9=5N4W9:9W7Jav8T7T8W7a047Z9q0=7(7Var9`0k0z0`0f0h0h0Ga78raO9w850`7`aZ840=9j9laK018j9A8W0k0`aXa-7s8w2/9Ba!3?0q8Z1=a^8ua`47a(0y909)0A6Naw7P8K4=aA9Q965lbbaE9gaG0`0z4c9va)8b9s12br3Q0M7(2Tbw7|7~80a-8=8,b65X7bap8%a}a.0`b45Vb6b89M3e574P8B9-3F57bgax8KbW9^9gb+8Wa+bEbI4%bGa-a=9sbL9n9`7s0Rb?7bbvb:8t040VbBb;9yc561a?2uc89x040tcc1(b.8#bF9pc18.b^b204b}cm9r0rc0bMbs7sc4aqcwb7atb95p9+aB6k5nb$bd5lcF2I3l8yb`6;cDbU3f5CbcbZ6y3gcKcYcV9Z9_bNaHaJcsaL7hc-3RaR04a1bAc:7_a-ci9m6R8aa/a{a;0`0M1K0J0Ocp8v9IbScT0k5A7F2 bY9Rde7L9Vbh9ccM7R9fb+a|bsc|ck04bHcBbJ040icg0=8=0t9zd18ab@d4afd7c:b=c:b@dBcAcR2wbTdd6y8Fdg9,didXdk9;cL5A8Sdqb,9ibDcjdNcldy5:aSaUaWcbc_a$a-0S3H020w0Bd40g0De1e30d0gd8dacBdV5A93dZcH5_d%ei8K0u93blc)bsdJd5dMd?4|dOevcnaTaVa@d|04a%ey1(d 0`e7e40ueKe9ebdSc~4uee6y9Oehdm9X0u9T8OeX7JeZ9ZcQeRcS6}916lcGe$6k9/e#b%cM9@ep7U8W9|0`9~0z0B2t1b2Ual0Jan380+2y9l0y0$0ydKd6ecdTcCe-cEaveWe^5Aaze@d)6yaDd,bm8aaHbpeu3nds4v7bcp87dP7b7oa:8;bz1cfLaPd3etdvdxfjdz9tfTb~042u0J0Xb_e+cxa$d9eQ7yasflcU0ubbfoft3fbffsc$f=c(dreq3Qdud;dwfZfXeDcreG9D0rcpczdH9`8=dGfCd29sfK6q9#0W6/6S6*6U6%1d0d6Xgu2O2J0f1Zgr0W6V7w0#0%0)0S04.

4. Création d'un forêt (ensemble d'arbres, ici une liste) et regroupement.⚓︎

On va commencer par créer la liste de tous les arbres racines qui correspondent à chaque caractère, avec comme attribut v le nombre d'occurrences.

Puis, par itérations, on va chercher a chaque étape les deux arbres ayant les poids minimaux et les fusionner avec la méthode join après les avoir préfixé.

Pour cela on a besoin de 3 fonctions :

  • get_foret : construction de la liste d'objets code initiaux
  • deux_min: retourne les deux objets Code de valeurs minimales
  • arbre_huffman : fusion des arbres jusqu'a ce que la foret ne contienne plus qu'un Ă©lĂ©ment

Code à compléter

###(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 : 5/5
.128013Cit3a;dv,n{2.S5Ă©wbcy14q: f-up08j_)9}eklohxrP=[s6(]/mg7050h0L0d0f0c0N0V0z0t0N0f0V0V0T010d0c0D010406050V0C0!0!0f0R0u040o0O0N0C0`0O0k050Z111315170 0D04051n1g1q0Z1n0 0h0c0i0/0;0?0^0;0k0#0C0f0#0L0B0D0u0d0P1e0z0P0c0#0P0N1S0P0d0}050*0s0N0L1z0=0@011R1T1V1T0d1#1%1Z0d0R1o1N0/1a0V0D0f0k0^0m011)1B010A0,0L0k0f0!0L1Z1~20251+281%2b2d0}0a0z0S0R0O0D0O0V0c1d0k0z0(1|0R0R0L0t2y1g2g0k1o0Z1N2L1^1`1_1!0h2i1C0c0k2a2v1Z1w1y0:1*2V2X0k0O2#1Z0D2E1o2J2L2=101 2z2%262+0R140N1Z0f1Q2E0A0^030H0H0t2,0L1V2*0O0B0W0B0v0}0z0v1g0f2?2_0~2^2h2{1+2}2 31330L350137393b3d2Y3g0B23040z0m3n3p203r2J2U013w0f301o320P3436383a0(3G2+3I0e3k0e3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0w3k0w3:1h3=3s2`1A3v0O2~3W3y3!3A3$3E3)423+3h0p3k0p482=3?2_3T3`4i3~3D3(3c4o3f3h0W3k0W4u4a3@4d3_4f3x3Y3z3B4C413e3I0$3k0$4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0F3k0F4$2K4(4c2(4+4g3{3}4k3 4m4E4?0B0J3k0J4{3R4x3^504R3|4T4l4D3*4G3i0E0}0v0E5d4}4y4,525k555m4F3I0v3j045E5u4b5w514A544V4=433i3K0v3N0Z3o3;4%5J5g4z4.4B4;575Q0v3-5G3/5V3P4|5Z4*5#5j4/5l4W5*455G475/5X5;4N4 5@534:565n5D4r5G4t60495Y632|5x5M675B580v4I5G4K6e4v5=646j5$5N5(693h0v4Z5G4#6s4M5f5?6w5^5%685C6B4^5G4`6G6g6I6v5L6x6l5{4p3i5a5G5c6T626V6i6X6L6y6N580m5q046?5I6h4e6.665`5P6#0m5F726`6,6|5i6~5A6!5o0m3K7d754)6W785z5O5)715,0m5.5W6f6+7h6-7j5_7a707c5}0m5 7r6t6{4P6}7k6z6O3J6b0m6d7E6H7u774-6/6Z7z3I0m6p7Z7g4~7v7U797l6A3J6D0m6F7Q6U7S7H7w6M6m5Q0m6Q7|7$5K7^6:7`716%0m6)7;7t7%7T5y7x7+7L0e6@8g7 5!6K7*7K580e5F8p5d1r2:1g2#2O0h1`2T5g4D2!1x1o2/0L2;3q611o4D8I2h0c0h0^382J5D3y8P8R6;5*242m0L8X835o5F3:7G010t5F031|0k0V1^0C2G0c1P2B0;0z1V8?1(0h02030e0J0g0O0s0G0)0.4D0z2W2x0c0f0C0Q8K0 7s8N2z8W018S2_7Y8V8Q9r8Y718!2c8$9x8(9u2L5W8,0M0}0(0A8K6u260r3k9N8,0k0A0}1I0d0H0A4f0)9S760^0|040X9%7?3U0}0O0t0t0C2D2a0t0L0V9-8a9)0}0I0y9l9}9e9w9s203,9v8%7ba90z8#ab7X3h5,3O0zal0z9O3v0}9M9nan8,0O0}0T8Kat9(019*0U0Ya39n5J9qa70k3I5}5jaI9y5o45ae9Bag7maQ1Z5/amaz9.9J049!0Rayao3_0}0ta45g9*0ja/5?0}0ia*au9Q042Wa`aA0k9:9=9@2E0k9`9|aGau0}0na?640}2x0L0!b82@8,9*0Xa1aFbk4xaO8T4qaa9DacbuaS2daU7,6bakaZama+9/a%bd26av04bcb9b00}0f0D0D2a0hbK1+bmbXa,040b3bb!aB0}9,bP9.b104a_b-9~b*040j0lb)b/a.b=3T9*a2b~5g0V5F93950gc696b)9*0K0I0Ibp8J3Sbs9t4Hbv8n5Q4Ibz9Ccn6#6pbEalbHa$2E0d9@1fasbHb/ar6tb~cja83h6DaNa6aP4Y9AbAbwah0BcM5/9mbq8OcObt0B6QcNbB7L4^cqc*58c(608,8.0}8:cz0OcB1(1%0.0(9j0zb%2B2B0i3W0L9@0.0!9f2 0Lcg3QaHc#ck59cmcP3h5ac-cTaV3I6%8+aAa$9Lb)a|anc25?9V04c 0Q0HdacCcZb?bZdAbea%9#0dcba0c1cHdJa58Xc$5sdk9E6B5qdocs8)6@cva!b?b/dH3mcDba04axd=bQdOczdR040Ub)da0}5tdM269*aE9ncYchbrdhcK3i8*32aOd#eecRcrdlej9G3LbG9T0}dH5U2=d-3TbMd^evcEaqdPd}d e41+e15Gd}e7dUeac!dXdi5Td!bx5Rekc.5*3Kd,bHc?048:1P0id70d0zd:0n1y020N0d0g0Te,2W0me.0j2A1e0t0zbU2~1c0f2y0z0qe)0kcA3c1%de2KdgePed5+eScUfid(emfieoaZcxbfcG3qew5!es2Wd;dV5gbMbOfAa@b:a 9.bM020#e=fHd.fx0keueNb?fCb{a^d}dT4acIecaK6BaMegcOei0vaRafdp7,f,aX3obFeqd`d:d}a=d_b.fPfR3Qfv4*eyfN4yf f{g5fw04f`e8a4cJf$3ibDf)eW6#0v4rfmf+bDcXgef#5Dcugjf/7L6oeVgx6ncuaYf^a#eCa)f}fO04b}eAa{bfdIfueBd{9$eG9 d~e00c0}g0febl0}0y0YfY5Yf!fggg6Cfjdq6B4ZgoeTg:fpf@g24 a$0cftg1gSgMfSexbbfVfGgJh604e:e=ezgRergbfyb)fUgVbIb;fE4 c0fd9odW9xdYc(gwd)5Dc,f.hz6Pf=epg|gFgKgchpe50}f|gNf_e_g9g3awhSdNh4dfg%b^hV2|fPfzhgaAe#e%2z2E0!0D0;9`8~9{2Ad79kgdg-hveQdshyfndnhCi1hFhHfr044Eh12Kg}h$gLhkh7hmb/hoh)fI0}hde?h#aphifQifbNh8ijhYaAhrh{dVgf7Yd+i0ei6?gAhD3Jd+gEhHcwhhetip0^g4hagahXibe!8/0z1Ph.h:0fh=0Vd71%2df9e^isiAh5iC3h72g;7,i^g^cUi^g{iOdu0}czcBiRb@b,hLiqhKh5a:hNh8iQhm9*cfi;ixeOh}ed7di_7Ljoi|g=3JeYgrh|aJ7YajiFeT7piIemjDeoe9jk9pgti@f(huiJ7CjEiGaMjwiBjL7Mjp6=gni3iGgq9Hh*iZ0A0C2w8{h@150s2E0.0Gj,0x0Cc90g32h=j_c|32a(0)ae1(3af90c2a2Xf01b0.j_j{0C2z0q0N0qi-dQjjg$ebg.7YgvjOjFcpj#jCgDj(gGdD3Adx9RihdCj:2E0H0P0C0A0A14gQjJb b+h8k2kmj8gWboknhti?7-jY7{g@kwi}cWf?hI3Ta$0r1RfciU5?0s0}2ld}j7jbfFkUd}jihPilhcfLiok@4 eIg#htjc04g+5;jx0Hc$7|k%71hBaTgB7{c:k-f@gSjakQldhOikhJhRl8bLhUlCiqdEdGa~jgkSihgHgUkWb@l2fZjVkqi@h ktiGi2lojPdsiMbFluhjhmhllPb/0G0OlJlPdLl-g7lK04lRg,lTjmgg8gll5om0js7,m0i l(hhl0l+igl@04h.0Oe)k|jelBl=a0hsffl~3,eflXeT8pjRmt8*l%i7j30RkPiXm9eDl_eFlPeIe3ml04eLlS8J0Z8M8t8H8v8E1g0d8ymW2R2M0f1$mT0Z8w9m0(0*0,0V04.