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

.128013:pbv(40i2+edm3;s= 1o5w_lSInatf)h]R6qcrg,[éyP!kuè/050m0l0D0C0i0y0q0s0L0y0C0q0q0r010D0i0c010406050q0V0n0n0C0M0R040z0u0y0V0=0u0B0s020C0n0c0p0s0I0l0 0M0K0V0l0q050X0|0~10120`0c041q1x051A0X1A1C1x0`0m0i0e0*0,0.0:0G0i0N0G0y1Q0G0D0^050#0d0y0l1L0-0/011P1R1T1R0D1Z1#1X0D0d0u0m121Y0M1y0D0G0*150q0c0C0B0:0j011%1N010E0%0l0B1d0l1X2224291)2c1#2f0n2h040a0s0S0M0u0c0u0q0i181a0Z200M0M0l0L2C1q2j0B1y0X1~2O0D1|1{1}0m2l0:1T0B2e2z1X1I1K0+1(2Y0i2!0B1^1J1X0c2H1y2M2O2_0{231a2*2a2/0M0 0y0^0t2L2}0_2|2k2 1)31330^0j3724392M2X013e0C34040o3i2N0`3l3c0:3o3q0g3t3k2}3m3z0^0v3C3v3E3x3n0u323p0^0J3C1z2@1q2(2R0m2V3m0L1^2r0Y1J1y2?0l2^383T3$0Z3.3b1M1)0U0^0Z0E3T3w3^0:0w0^0s3~3L403n0E0^0G1d0n2-0N453@2+010@040f4g2~470B0^0C4n3m4k0O3C443 4i4q040d4t3M4k0F0b3J0s4K4y464A3{0i0E0E0l2H0B0L1o4x3a4o4i0u0^0r4Y4z2a4d0^0h4J4L4Z3m3`040E3O4)4N300^0i4`4h2a0u42042-4 4!300d0^0M240N0l4E474k4m1r3/4*3d59042o5f4i5h5q4|044s5j3j4;4F0^0F4H4/4L4:5l0:4?4Q563F4r5t1)4k0P5O3y4}5S4j0^0H5L3M4$040T4(5x2N4M503d0^4D5)3?575P0^5R5:5z4p5U5_5H5W040H4I5:065F655G4{5-041I4R4T2e4W1p5:5+5=0:5#5(2_6i5M6a4Q4S4U6f5Z475#0k6v4i4,0436635F5`4i4?2H0D0V0M0B6z5u6b6s6e4X631q3;3-3U6X0X3X1q0D3Z6$2T2P1@1_2R0C1!6Z3X1w5;3m2H0n0x0E0C0U0l0x0G0o0^1i1k1m1o0s622{1D391x0A0y0s1o0D0s0C0V0.0i0s2y7m6:0s2E0L0M0Q4T0s0,7y0i0q0D1$0Z0)2-1I6f7s770L100C2J0W2H0)6Q0Q4U0D0)0!7K0s4U0e0u0R7x0q0C7y190N1n6L781z392(3m1+1S1U1W6@3M2n2e2g0^2t0z7u0?7i0S0R1~193T3,5;2`3/6W7}474?3|5V53445}683y49044b0~4e5V5s8p5,5T5v8x0^4w6h6G5u5/2{5~4G793864678A3n4P6c7V6g6n8H1)6l6O5?045^8K8q8S548#5I0^4^0M8-8+4~8G5~524}6N8^8*0B5n5b0B5d8D4l5V8 0^5p8z6j5 5i8)8R4B5w9e9b4G0F8=5J3}8}9f5N9a4u5@965|9i9t608=5#5%8=4B8J5k8*5Q9v8,9s5A605Y6E8Q9b6I0!6L8|8X5~975o2e949d9G9q6q8U2e7W949l6U0X8h6Y2O6=3W0!0$0(04.