Distance de Hamming

La distance de Hamming permet de mesurer le nombres de différences entre deux « suites de symboles ». Dans cet exercice nous nous limiterons à des chaînes de caractères.

Soient $a$ et $b$ deux chaînes de caractères de même longueur. La distance de Hamming entre $a$ et $b$, notée $hamming(a, b)$ est le nombre de positions où ces deux chaînes ont des caractères différents.

Ainsi :

$hamming(«~ chat~ », «~ chat~ ») = 0$ : tous les caractères sont identiques ;
$hamming(«~ louve~ », «~ poule~ ») = 2$ : les caractères en première position et en quatrième position sont différents.

À quoi ça sert ?

La distance de Hamming permet donc de mesurer les différences entre deux suites de symboles.

Elle est en particulier utilisée en télécommunication afin de détecter les erreurs de transmissions dans un message. Dans le « cube » ci-dessous, les sommets sont des messages de trois bits. Deux sommets sont reliés par une arête si la distance de Hamming qui les sépare vaut $1$. Les sommets $100$ et $001$ sont à une distance de $3$ l'un de l'autre.

Par en:User:Cburnett — Travail personnel Cette image vectorielle
SVG non W3C-spécifiée a été créée avec Inkscape ., CC BY-SA 3.0, Lien

Écrire en Python la fonction hamming qui prend en paramètres deux chaînes de caractères a et b de même longueur et renvoie la distance de Hamming de ces deux chaînes.

On rappelle qu'il est possible de tester la différence de deux valeurs avec l'expression x != y. Ainsi 3 != 2 renvoie True et 3 != 3 renvoie False.

Exemples

>>> hamming("", "")
0
>>> hamming("1", "1")
0
>>> hamming("ab", "ac")
1
>>> hamming("001", "100")
2
>>> hamming("nuage", "neige")
2

Évaluations restantes : 10/10

.128013buS[,3_è4l(wn/R)pIaPké0;:hors1vc25qm6!gyd]ieft =+050P0S0U0t0R0k0D0V0G0k0t0D0D0W010U0R0r010406050D0c0K0K0t0C0O040d0B0k0c0=0B0n0V020t0K0r0y0V0p0S0 0C0J0c0S0D050o0|0~10120`0r041q1x051A0o1A1C1x0`0P0R0F0*0,0.0:0A0R0N0A0k1Q0A0U0^050#0b0k0S1L0-0/011P1R1T1R0U1Z1#1X0U0b0B0P121Y0C1y0U0A0*150D0r0t0n0:0H011%1N010T0%0S0n1d0S1X2224291)2c1#2f0K2h040a0V0u0C0B0r0B0D0R181a0Z200C0C0S0G2C1q2j0n1y0o1~2O0U1|1{1}0P2l0:1T0n2e2z1X1I1K0+1(2Y0R2!0n1^1J1X0r2H1y2M2O2_0{231a2*2a2/0C0 0k0^0E2L2}0_2|2k2 1)31330^0H3724392M2X013e0t34040g3i2N0`3l3c0:3o3q0j3t3k2}3m3z0^0I3C3v3E3x3n0B323p0^0L3C1z2@1q2(2R0P2V3m0G1^2r0Y1J1y2?0S2^383T3$0Z3.3b1M1)0v0^0Z0T3T3w3^0:0m0^0V3~3L403n0T0^0A1d0K2-0N453@2+010@040l4g2~470n0^0t4n3m4k0f3C443 4i4q040b4t3M4k0q0z3J0V4K4y464A3{0R0T0T0S2H0n0G1o4x3a4o4i0B0^0W4Y4z2a4d0^0x4J4L4Z3m3`040T3O4)4N300^0R4`4h2a0B42042-4 4!300b0^0C240N0S4E474k4m1r3/4*3d59042o5f4i5h5q4|044s5j3j4;4F0^0q4H4/4L4:5l0:4?4Q563F4r5t1)4k0e5O3y4}5S4j0^0Q5L3M4$040M4(5x2N4M503d0^4D5)3?575P0^5R5:5z4p5U5_5H5W040Q4I5:065F655G4{5-041I4R4T2e4W1p5:5+5=0:5#5(2_6i5M6a4Q4S4U6f5Z475#0X6v4i4,0436635F5`4i4?2H0U0c0C0n6z5u6b6s6e4X631q3;3-3U6X0o3X1q0U3Z6$2T2P1@1_2R0t1!6Z3X1w5;3m2H0K0h0T0t0v0S0h0A0g0^1i1k1m1o0V622{1D391x0s0k0V1o0U0V0t0c0.0R0V2y7m6:0V2E0G0C0w4T0V0,7y0R0D0U1$0Z0)2-1I6f7s770G100t2J0i2H0)6Q0w4U0U0)0!7K0V4U0F0B0O7x0D0t7y190N1n6L781z392(3m1+1S1U1W6@3M2n2e2g0^2t0d7u0?7i0u0O1~193T3,5;2`3/6W7}474?3|5V53445}683y49044b0~4e5V5s8p5,5T5v8x0^4w6h6G5u5/2{5~4G793864678A3n4P6c7V6g6n8H1)6l6O5?045^8K8q8S548#5I0^4^0C8-8+4~8G5~524}6N8^8*0n5n5b0n5d8D4l5V8 0^5p8z6j5 5i8)8R4B5w9e9b4G0q8=5J3}8}9f5N9a4u5@965|9i9t608=5#5%8=4B8J5k8*5Q9v8,9s5A605Y6E8Q9b6I0!6L8|8X5~975o2e949d9G9q6q8U2e7W949l6U0o8h6Y2O6=3W0!0$0(04.