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
.128013oPf 8lkg5:+bry2a1}h3tvw=u6{e[(Sn]x_s-c)7im/4pd050U0C0v0q0P0g0K0e0M0g0q0K0K0y010v0P0T010406050K0z0Q0Q0q0n0o040F0b0g0z0/0b0G050R0_0{0}0 0@0T04051f181i0R1f0@0U0P0w0%0)0+0-0)0G0i0z0q0i0C0L0T0o0v0t160e0t0P0i0t0g1K0t0v0=050Y0m0g0C1r0*0,011J1L1N1L0v1T1V1R0v0n1g1F0%120K0T0q0G0-0p011X1t010d0!0C0G0q0Q0C1R1?1^1}1Z201V23250=0a0e0c0n0b0T0b0K0P150G0e0W1;0n0n0C0M2q18280G1g0R1F2D1-1/1.1S0U2a1u0P0G222n1R1o1q0(1Y2N2P0G0b2T1R0T2w1g2B2D2*0^1@2r2V1~2Z0n0|0g1R0q1I2w0d0-030J0J0M2!0C1N2Y0b0L0r380=0r180q2+2.0?2-292:1Z2=2@2_2{0C2}012 3133352Q380L1{040p3d3f1^3h2B2M013m0q2^1g2`0t2|2~30320W3w2Z3y0u0=0u3D2A3g0@3H3k0-3K3M053O3Q3s3S3v2O3x390S0=0S3#193%3i2/1s3l0b2?3L3o3P3q3R3u3U3@3W390j0=0j3}2*3(2.3I3,473:3t3T344d37390A0=0A4j3 3)423+443n3N3p3r4r3?363y0O0=0O4A3F4l3j4D3J4F464H484J3=4c4M390f0=0f4R2C1j2(182T2G0U1/2L3*014s2S1p1g2%0C2)3g3$3F054s52290P0U0-302B3y0r3o5a5c4b4t4(3a0e2e0C5j4s3V4v3a2D3e403I0h0=0W0d544.4C2W010x0=0e5E58415H0G0d0=0b0M0M0z2v220M0C0K5M5y4`0;040E5$5G2;0=0v0C0I5:5,4m5(0=0N0k5M0@3~553H5i015d2.3y3A3.0e624$5l3^3z1|5p5r4L6d670R3e0e6n5L5-3l0=0M0}5M6p5^4V0b0=0y6v5%4V5)0B0s5}5@595b630J5e393Y4H6a5k5t3X6f245q6M5s4u6V5w046o6w4U5H5A040d446C6q3+6s6;6x5H0b5J042O6^6+5.045:5=0C6J5O1~5)5|5 2C5~2,616L641^3y3`6R7g6T6#3_6W256h4%6d7k3D6)6)6D6,0=0P5D7b6(7z710M6 771Z6{7B177E6*7K6?046t0n763I796I7E5y6S6O0L4g7l7s6c4e7(7q6Y6b6U4f1R6l6(7x7`7G6r7T6u7!6=015)0D7W4`0G6@806_780=0H7J3I6z040l6B7P7|0-0Q0P3b7Z7e4m7$654w5h7m6!5m4x5o6X7+7=0L4x6%7`6n8l016-340K7589701Z7Y7E7d537f5j7%4O7*6Z6i7-4O8B7r8$7t8(7@6m8I7y81877~7V8Q7R820=848`4n888r8R0-5)8d8k818g8j2*7Q3I8n8p8U7W8t7i4)8w8D7o0L4*8*7:7n5m4*8H6o8K6-2w0v5W7O9b8K8@7U8q530R574/514;4~180v4@9P2J2E0q1U9M0R4=5~0W0Y0!0K04.

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
.128013oPf 8lkg5:j+,bry2a1Ch3tvw=u6e[(Sn9]_s-c)7im./4p0d050X0D0x0s0Q0g0L0e0N0g0s0L0L0A010x0Q0V010406050L0B0R0R0s0p0q040G0b0g0B0=0b0H050T0|0~10120`0V04051i1b1l0T1i0`0X0Q0y0*0,0.0:0,0H0i0B0s0i0D0M0V0q0x0v190e0v0Q0i0v0g1N0v0x0^050#0o0g0D1u0-0/011M1O1Q1O0x1W1Y1U0x0p1j1I0*150L0V0s0H0:0r011!1w010d0%0D0H0s0R0D1U1_1{201$231Y26280^0a0e0c0p0b0V0b0L0Q180H0e0Z1@0p0p0D0N2t1b2b0H1j0T1I2G1:1=1;1V0X2d1x0Q0H252q1U1r1t0+1#2Q2S0H0b2W1U0V2z1j2E2G2-0{1`2u2Y212$0p0 0g1U0s1L2z0d0:030K0K0N2%0D1Q2#0b0M0j0M0t0^0e0t1b0s2.2;0_2:2c2?1$2^2`2|2~0D3001323436382T3b0M1~040e0r3i3k1{3m2E2P013r0s2{1j2}0v2 3133350Z3B2$3D0w3f0w3J2D3l0`3N3p0:3Q3S053U3W3x3Y3A2R3C3c0U3f0U3+1c3-3n2=1v3q0b2_3R3t3V3v3X3z3!3}3$3c0j3f0j432-3.2;3O3=4d3_3y3Z374j3a3c0C3f0C4p453/483;4a3s3T3u3w4x3|393D0P3f0P4G3L4r3o4J3P4L4c4N4e4P3{4i4S3c0f3f0f4X2F4Z472Z4$4b3?3^4f3`4h4z4.0M0I3f0I4?3M4s3:4{4M3@4O4g4y3#4B3d0W0^0t0W584^4t4%4}5f505h4A3D0t3e045z5p465r4|4v4 4Q4-3~3d3F0t3I0T3j3,4Y5E5b4u4)4w4,525L0t3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2@5s5H625w530t4D5B4F694q5-5 6e5X5I5Z643c0t4U5B4W6n4H5a5.6r5:5Y635x6w4:5B4=6B3L1m2+1b2W2J0X1=2O5b4y2V1s1j2*0D2,3l5|1j4y6)2c0Q0X0:332E5y3t6:6=6I6i1 2h0D6{6h5#1U5{6c1$0h0^3p6+6p210z3f7b763;0N0^0u367g6D4`0@040k6+0`6a2F5E6`016?2;3D3F5e7y6u6J3E6~27707z6|5L7D5*0e7R0e7c770^0Z0d7n4!4`7e3G7Z4_210d0R0^332R2s337(3O7q0F7=5b0o7q0L377Y7v6.7)1$7q0n6+7T7h3P0^0y3R0B0D7_4#84867U3;790v107}0x8f7p0^0O7s807u2/3N7F0K6@3c5%7E6;7M724k0M3(0e6 715?8I8D7Q7S8S8j017{0^7}0g7 8x7o210b0^0S8q2@8a8i888(040A8.8$3q8a8c8e8v7=8z8B0M5^8E8N5K8I408L7K935!95743j8S8T888W048Y8!6*8/8)8+8^040N0L8?7!8%0^8=80878@8k9q8m0p8o7t8}8F7A1{3D66928G8O5j4m9728996v3b9c3m807x9I8A7B4C6_9#8H5j4D9S7L7G536k3J9f9A010N5A030e0s0l0b171Z0B2u0o2s9}0e0i0s0B0N0v1Z2}0xa00x0e1Y0)4y9s8|9Z8y9#8 6y9N9:5L4U9.9U7Hat8R7R8U78047X9o0:7$7Tap9^0H0d0^0s0X0X0Ka58paM9u830^7^aX820:9h9jaI018h9y8U0H0^aVa+7q8u2-9zaY3;0o8X1:a?8sa^45a$0e8~9%0M6Lau7N8I4:ay9O945jb9aC9eaE0^0d4a9ta%899q10bp3O0b7$2Rbu7`7|7~a+8:8*b45V79an8#a{a,0^b25Tb4b69K3c554N8z9+3D55beav8IbU9?9eb)8Ua)bCbG4#bEa+a:9qbJ9l9^7q0Eb;79btb.8r040Jbzb/9wc35 a;2sc69v040mca1$b,8ZbD9nb 8,b?b004b{ck9p0Nb~bKbq7qc2aocub5arb75n9)az6i5lb!bb5jcD2G3j8wb^6/cBbS3d5AbabX6w3ecIcWcT9X9@bLaFaHcqaJ7fc+3PaP049 byc.7@a+cg9k6P88a-a_a/0^0b1I0D0pcn8t9GbQcR0H5y7D2}bW9Pdc7J9Tbf9acK7P9db)a`bqc`ci04bFczbH040yce0:8:0m9xc 88b=d2add5c.b:c.b=dzcycP2ubRdb6w8Dde9*dgdVdi9/cJ5y8Qdob*9gbBchdLcjdw5.aQaSaUc9c@a!a+0L3F015ld6d8czdT5y91dXcF5@d#e88I0t91bjc%bqdHd3dKd;4`dMelclaRaTa=d`04a#eo1$d}0^013ee1dQc|4se46w9Me7dk9V0t9R8MeK7HeM9XcOeEcQ6{8 6jcEeP6i9-eOb#cK9=ef7S8U9`0^9|0d0B2r192Saj0Dal360)2w9j0e0!0edId4e2dRcAeWcCateJe(5yaxe%d%6waBd*bk88aFbnek3ldq4t79cn85dN797ma.8/bx1afyaNd1ejdtdvf6dx9rfGb|042s0D0Rb@eUcva!d7eD7waqf8cS0tb9fbfg3dbdffc!f#c$dpeg3Odsd/dufMfKetcpew9B0NcncxdF9^8:dEfpd09qfx6o9Z0T6-6Q6(6S6#1b0x6Vgh2M2H0s1Xge0T6T7u0Z0#0%0L04.

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
.128013oP;f 8lkg5j:,bry2a1Ch}3tvw=u6{e[(Sn9]x_s-c)7iqm./4Ă©p0d050$0F0y0s0T0h0O0f0Q0h0s0O0O0B010y0T0!010406050O0C0V0V0s0p0q040I0b0h0C0`0b0J050X111315170 0!04051n1g1q0X1n0 0$0T0z0/0;0?0^0;0J0j0C0s0j0F0P0!0q0y0v1e0f0v0T0j0v0h1S0v0y0}050*0o0h0F1z0=0@011R1T1V1T0y1#1%1Z0y0p1o1N0/1a0O0!0s0J0^0r011)1B010e0,0F0J0s0V0F1Z1~20251+281%2b2d0}0a0f0c0p0b0!0b0O0T1d0J0f0(1|0p0p0F0Q2y1g2g0J1o0X1N2L1^1`1_1!0$2i1C0T0J2a2v1Z1w1y0:1*2V2X0J0b2#1Z0!2E1o2J2L2=101 2z2%262+0p140h1Z0s1Q2E0e0^030N0N0Q2,0F1V2*0b0P0D0P0t0}0f0t1g0s2?2_0~2^2h2{1+2}2 31330F350137393b3d2Y3g0P23040f0r3n3p203r2J2U013w0s301o320v3436383a0(3G2+3I0x3k0x3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0Y3k0Y3:1h3=3s2`1A3v0b2~3W3y3!3A3$3E3)423+3h0k3k0k482=3?2_3T3`4i3~3D3(3c4o3f3h0D3k0D4u4a3@4d3_4f3x3Y3z3B4C413e3I0S3k0S4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0g3k0g4$2K4(4c2(4+4g3{3}4k3 4m4E4?0P0K3k0K4{3R4x3^504R3|4T4l4D3*4G3i0#0}0t0#5d4}4y4,525k555m4F3I0t3j045E5u4b5w514A544V4=433i3K0t3N0X3o3;4%5J5g4z4.4B4;575Q0t3-5G3/5V3P4|5Z4*5#5j4/5l4W5*455G475/5X5;4N4 5@534:565n5D4r5G4t60495Y632|5x5M675B580t4I5G4K6e4v5=646j5$5N5(693h0t4Z5G4#6s4M5f5?6w5^5%685C6B4^5G4`6G6g6I6v5L6x6l5{4p3i5a5G5c6T626V6i6X6L6y6N580r5q046?5I6h4e6.665`5P6#0r5F726`6,6|5i6~5A6!5o0r3K7d754)6W785z5O5)715,0r5.5W6f6+7h6-7j5_7a707c5}0r5 7r6t6{4P6}7k6z6O3J6b0r6d7E6H7u774-6/6Z7z3I0r6p7Z7g4~7v7U797l6A3J6D0r6F7Q6U7S7H7w6M6m5Q0r6Q7|7$5K7^6:7`716%0r6)7;7t7%7T5y7x7+7L0x6@8g7 5!6K7*7K580x5F8p5d1r2:1g2#2O0$1`2T5g4D2!1x1o2/0F2;3q611o4D8I2h0T0$0^382J5D3y8P8R6;5*242m0F8X835o5F3:7G010Q5F031|0J0O1^0C2G0T1P2B0;0f1V8?1(0$000b0o0l0)0.4D0f2W2x0T0s0C0M8K0 7s8N2z8W018S2_7Y8V8Q9n8Y718!2c8$9t8(9q2L5W8,0i0}0(0e8K6u260A3k9J8,0J0e0}1I0y0N0e4f0)9O760^0|040H9Z7?3U0}0b0Q0Q0C2D2a0Q0F0O9)8a9#0}0R0m9h9_9a9s9o203,9r8%7ba50f8#a77X3h5,3O0fah0f9K3v0}9I9jaj8,0b0}0B8Kap9!019$0G0L9 9j5J9ma30J3I5}5jaE9u5o45aa9xac7maM1Z5/aiav9*9F049W0pauak3_0}0Qa05g9$0na+5?0}0za$aq9M042Wa?aw0J9,9.9:2E0J9?9^aCaq0}0Wa/640}2x0F0Vb42@8,9$0H9}aBbg4xaK8T4qa69za8bqaO2daQ7,6bagaVaia%9+aZb926ar04b8b5a|0}0s0!0!2a0$bG1+bibTa(040u3bbWax0}9(bL9*a}04a=b)9`b$040n0Eb#b+a*b.3T9$9~b`5g0O5F0000b#9$0w0R0Rbl8J3Sbo9p4Hbr8n5Q4Ibv9ycg6#6pbAahbDaY2E0y9:1faobDb+an6tb`cca43h6DaJa2aL4Y9wbwbsad0PcF5/9ibm8OcHbp0P6QcGbx7L4^cjcZ58cX608,8.0}8:cs0bcu1(1%0.0(9f0fbZ2B2B0z3W0F9:0.0V9b2 0Fc93QaDcUcd59cfcI3h5ac$cMaR3I6%8+awaY9Hb#a^ajb~5?9R04c^0M0Nd3cvcSb/bVdtbaaZ9X0yc49|b}cAdCa18XcV5sdd9A6B5qdhcl8)6@coaWb/b+dA3mcwb604atd+bMdHcsdK040Gb#d30}5tdF269$aA9jcRcabndacD3i8*32aKdUe7cKckdeec9C3LbC9P0}dA5U2=d$3TbId.eocxamdId?d^d}1+d`5Gd?e0dNe3cTdQdb5TdTbt5Redc%5*3Kd#bDc,048:1P0zd00y0fd)0W1y020h0y0d0Be#2W0re%0n2A1e0Q0fbQ2~1c0s2y0f0ZeY0Jct3c1%d72Kd9eIe65+eLcNfbdXeffbehaVcqbbcz3qep5!el2Wd*dO5gbIbKfta:b,a{9*bI020je+fAd%fq0JeneGb/fvb@a;d?dM4acBe5aG6BaIe9cHeb0taNabdi7,f#aT3obBejd:d)d?a.d/b*fIfK3Qfo4*erfG4yf^f;f~fp04f:e1a0cCfV3ibzfYeP6#0t4rfff!bzcQg7fU5Dcngcf(7L6oeOgq6ncnaUf.aXeva#f?fH04b_eta@bbdBfneud;9Yez9{d@d_0T0}f_f7bh0}0m0LfR5YfTf9g96Cfcdj6B4ZgheMg)fif-f{4 aY0Tfmf`gLgFfLeqb7fOfzgCg 04e)e+esgKekg4frb#fNgObEb-fx4 b|f69kdP9tdRcXgpdY5Dc#f%hs6Pf+eig=gygDg5hid~0}f=gGf/e/g2f|ashLdGg}d8gWb;hO2|fIfsh9aweUeW2z2E0V0!0;9?8~9@2Ad09gg6g$hoeJdlhrfgdghvh`hyhAfk044Eg`2Kg?hVgEhdh0hfb+hhhYfB0}h6e,hUalhbfJi8bJh1ichRawhkh;dOg87Yd!h_eb6?gthw3Jd!gxhAcphaemii0^f}h3g3hQi4eT8/0f1Ph%h)0sh+0Od01%2df2e.ilitg~iv3h72g*7,i.g.cNi.g;iHdn0}cscuiKb:b(hEijhDg~a,hGh1iJhf9$c8i*iqeHh?e67di/7Ljhi=g+3JeRgkh=aF7YafiyeM7piBefjwehe2jd9lgmi-fXhniC7CjxizaIjpiujE7Mji6=ggh|izgj9DhZiS0e0C2w8{h-150o2E0.0lj#0U0C0032h+j/c=32a!0)aa1(3af20T2a2Xe_1b0.j/000C2z0Z0h0Zi$dJjcgVe4g%7YgojHjycijUjvgwjXgzdw3Adq9Niadvj)2E0N0v0C0e0e14gJjCb{b%h1j`kej1gPbkkfhmi,7-jR7{g-koi?cPf,hB3TaY0A1Rf5iN5?0o0}2ld?j0j4fykMd?jbhIieh5fEihk,4 eBgUhmj504g!5;jq0NcV7|kV71huaPgu7{c)k#f-gLj3kIl5hHidhChKl0bHhNluijdxdza`j9kKiagAgNkOb:k`fSjOkii-h^klizh{lgjIdliFbBlmhchfhelHb+0l0blBlHdEl#g0lC04lJg#lLjfg98gld5ol^jl7,l^i^lWhak^lZi9l,04h%0beYk;j7ltl*9|hlf8l?3,e8lPeM8pjKml8*lVi0i|0pkHiQm1ewl.eylHeBd|md04eElK8J0X8M8t8H8v8E1g0y8ymO2R2M0s1$mL0X8w9i0(0*0,0O04.