Aller au contenu

Compression Run-Length Encoding

Le cadre

Certains formats de fichiers informatiques utilisent la compression Run-Length Encoding.

Le principe est de remplacer les suites de valeurs identiques par des couples (valeur, répétition).

On propose ci-dessous un exemple d'application à un fichier texte :

Exemple 
>>> compression_RLE("aabbbbcaa")
"2a4b1c2a"

Le code "2a4b1c2a" signifie que la chaine "aabbbbcaa" comporte dans cet ordre :

  • deux "a" ;
  • quatre "b" ;
  • un "c" ;
  • deux "a".
Remarques

Cette méthode de compression est particulièrement efficace dans le cas d'un texte comportant de nombreuses répétitions.

Par exemple, le texte "aaaa...a" comportant 10 000 fois le caractère "a" sera compressé en "10000a". On passe ainsi de 10 000 caractères à 6 !

À l'inverse, si le texte comporte beaucoup de caractères uniques, la compression n'est pas avantageuse : "abcd" devient "1a1b1c1d" et la taille a doublé !

Exercice

Afin de simplifier la démarche, on ne considèrera que des chaines de caractères ne comportant aucun chiffre. Ainsi, toutes les chaines étudiées ne comporteront que des lettres ou de la ponctuation.

Coder une fonction compression qui prend en paramètre texte et qui renvoie le texte compressé avec la méthode RLE décrite.

Exemples 
>>> compression_RLE("aabbbbcaa")
'2a4b1c2a'
>>> compression_RLE("aa aa.")
'2a1 2a1.'
>>> compression_RLE("a" * 1000)
'1000a'
>>> compression_RLE("aA")
'1a1A'
###(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 : ∞/∞
.128013x/.r;nbOylaeêu)dM63m(P+02è-],59fq7B8 _o=pcwgv41kRIéhtsSàLC[ji:E050q0m0#0l0-0k0$0L0Q0k0l0$0$0O010#0-0P010406050$0o0u0u0l0e0j040%0N0k0o130N0g0L020l0u0P0f0L0X0m1d0e0H0o0m0$050c1a1c1e1g180P04051L1E1O0c1L180q0-0T0{0}0 110!0-0S0!0k1$0!0#16050?0h0k0m1X0~10011#1%1)1%0#1/1;1-0#0e1M0#0!1?1Z010G0^0m0g1r0m010{1j0$0P0l0g110z1-2j2l271^2a1;2d0u2f040a0L0w0e0N0P0N0$0-1m1o0;2h0e0e0m0Q2J1E2q0g1M0c252V2224231.0q2s111)0g2c2G1-1U1W0|1@2)0-2+0g0N2/1-0P2O1M2T2V30192k1o2;282_0e1d0k160L0V2S3417332r361^383a3c0z3f2l3h2T2(013m0l3b040L0t3q2U183t3k113w3y0L0U3C3s343u3I3c0E3M3E3O3G3v0N393x3c0s3T3i351Y3l3Y3n3z0I3%3F3*3H3,3!3z0K3:3V3=3X3Z3J0F3{3j3}3Q040V0y423)2=3~3-0V3e1F3g3U434b450V3p4g3r4i4a373@3y0V3B4o3D3(3P4t160V3L4x3N4j4s3 4C3S4F4q4A4J463$4M4z3W4l3/4S3;4k4B463`4X3|4Z4P0V414%4H3+4P0z484F1P2~1E2/2Y0q242%3W0Q2`2y0:1V1M2}0m2 3g3M05500;584.110W160;0G5a4Y280R3c5l4(370G16501s2O0 0-1n0M0X0)0/5q5f0115040v5F4r3l160#0m0b5P5L3u5I0p0.3T0L5Z0L4T3}5h040-5k4F5#5m3l0h162v5T3W5I5K4?5.3H5O5Q5S5`5r1^5V3M5-61110N160O0O645$4b0u0-164=325{5H165X4M5!6p655G5(2O0#0o0e0g6c6k0$2o0401013T066p6d375}5R0m0M5v560 0Z6z660168046b5,6J1^6B166E6G6I6k0g5u1e0l2Q0A2O0M0e0Z0P0Z0#6S6Z6k6W6Y306r5M5|045P6M5?3}5I0+786e6g046i596k5I0C5Y5!6!740g0h6?6^6`2I5z0g1D6}6U6 6T5G6f6h6)7m6k5(0G3Y7B733v6-0e6/0#6;0m7L3u0N5o5)6y7y5G6,755~7T605G5I6n306H6q5Z7n015(5*7U4U7O7Q7S7_3}6 703g723P7{6:6=6@6_6{7c287,7l7:6*6U7$7p7r897u1n7x717=6W0x813r833W7D468e6q7=5(0m0_7)6j6U8d6o8f8g7#6L5P6O0N5w1C0$6|8p6~168s7~4k5:040$228b62165_8G8M048j887t2J8o7h8H160p8Z288r8|5N040Q6.866N8;8a8J8K7;6+857R877s978V7z698 74927P948z8K7=8i7q968m7w9k6V9j7!7M8x4f7.7/9a8h8N6N6P5x8T9x8r8t2U8v448#8%0e8)115^9W7N8/9t9f9v8@3r7=639A7V8X9x7$9m7|9e898U4h9F9R4b6t0=6w7Z9h8.768O9K8S9_4p1E5c574@ac0c4`1E0#4|ah2#2W0l1:ae4`1K5e7M2O0u0M0G0l0W6N0!0t161w1y1A1C0L7-591R3h1L0)0l2h0g926{2d2J0L2L0Q0!0@2+0`aX939daH5b513u1`1(1*1,as8491aZ2@8F828q8X9P3z9r162_0o0T0m0l0o5a0cab3z0P0m1l0L0n221=501lbd0$1=2c2B0j251n0L0v0q0o0Lax2IaW1=0}0{6@0laV0q000o2+0Lb2b40k1;0{a^bKa%9na)0$0p0d0L0i1obcbe1l0^0-bm0e0LbC0u6`0!a,a+aX3}a.1|1+2p8h9T8(7*7M6W0d9Z7$0,0N2@b8ba0L1A0-0Lbc390=aW000Z0T2I0mb,0Q1=0q0Z0$0l0S6@2x0g0#c3aLar0Y0kbxb60#0L3x3Y0`0Q6@cn0LbJbBb*5PbA2h0o0P1;0`b?57bjcX1Caa513z0(0L2Ocv0NcWcO0q2l0`bCaYa!bi8Q6Q8TbncH2LcY0L01c62@0q2O2gbod38T2k7Pcyce1ecPbKc`a_0Lcl2Lc!a-1*b`a;7=6$6D6Fc09.04cA8-7Mc5c7a18^7+8+c45uc:c%9)2U9+8`c9c*cA1S4_0=0@0_3h2/3u0l0q0u1n9v0L0h1n0o0$161Kd%d)d+2J0B130#20040Jd/7xdW1L2C2E2GcOcQdncn2Hbs0lb40Q5#bad67Zca2F6w0Lckcmb,d350aRbF0ZaU7v0`960ZaHaXbReCbia(7S0$dVd#1Vd@d*0gd,2@7Jd=1NeNd_7vd{2Id~0rb:b=eidGc)5d1PaM04aO0Lb/brdpe(c8b9c*c-2c0Tc71=bJ2hbOcucqbIbK1)8%cqbieEa$eGbUeI0Lbob(f72lcHf0dd6.5Pen0q1n0g0ZeK1TeM3Wb_a:b|5G2u2c2e162A0*8n1j1=0wbqb;dH9*56as3159ba7=0S5I020S0#0ffZf#f%1u9Zdw2g0xd49Zc2dL04ej9Z5^7bdz3Wf,47dydD5U160D9xf,4;f dI7M5Ig39-f|6C010t0yg79*7i160C8{4-7M0S6W00470Lf.4;gu3A0y003%e_e+1R4^af5418gG0T3hgJ04.