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

.1280135[tf4)+2IrR3,sa!o iug0èm1]P6pnlhe=céy:v(wq;S/b_dk050W0H0d0p0t0F0o0s0J0F0p0o0o0I010d0t0D010406050o0u0y0y0p0k0L040S0r0F0u0=0r0E0s020p0y0D0R0s0l0H0 0k0Q0u0H0o050T0|0~10120`0D041q1x051A0T1A1C1x0`0W0t0N0*0,0.0:0G0t0v0G0F1Q0G0d0^050#0U0F0H1L0-0/011P1R1T1R0d1Z1#1X0d0U0r0W121Y0k1y0d0G0*150o0D0p0E0:0i011%1N010e0%0H0E1d0H1X2224291)2c1#2f0y2h040a0s0B0k0r0D0r0o0t181a0Z200k0k0H0J2C1q2j0E1y0T1~2O0d1|1{1}0W2l0:1T0E2e2z1X1I1K0+1(2Y0t2!0E1^1J1X0D2H1y2M2O2_0{231a2*2a2/0k0 0F0^0z2L2}0_2|2k2 1)31330^0i3724392M2X013e0p34040m3i2N0`3l3c0:3o3q0f3t3k2}3m3z0^0b3C3v3E3x3n0r323p0^0C3C1z2@1q2(2R0W2V3m0J1^2r0Y1J1y2?0H2^383T3$0Z3.3b1M1)0X0^0Z0e3T3w3^0:0P0^0s3~3L403n0e0^0G1d0y2-0v453@2+010@040O4g2~470E0^0p4n3m4k0n3C443 4i4q040U4t3M4k0g0M3J0s4K4y464A3{0t0e0e0H2H0E0J1o4x3a4o4i0r0^0I4Y4z2a4d0^0w4J4L4Z3m3`040e3O4)4N300^0t4`4h2a0r42042-4 4!300U0^0k240v0H4E474k4m1r3/4*3d59042o5f4i5h5q4|044s5j3j4;4F0^0g4H4/4L4:5l0:4?4Q563F4r5t1)4k0c5O3y4}5S4j0^0A5L3M4$040q4(5x2N4M503d0^4D5)3?575P0^5R5:5z4p5U5_5H5W040A4I5:065F655G4{5-041I4R4T2e4W1p5:5+5=0:5#5(2_6i5M6a4Q4S4U6f5Z475#0h6v4i4,0436635F5`4i4?2H0d0u0k0E6z5u6b6s6e4X631q3;3-3U6X0T3X1q0d3Z6$2T2P1@1_2R0p1!6Z3X1w5;3m2H0y0V0e0p0X0H0V0G0m0^1i1k1m1o0s622{1D391x0j0F0s1o0d0s0p0u0.0t0s2y7m6:0s2E0J0k0K4T0s0,7y0t0o0d1$0Z0)2-1I6f7s770J100p2J0x2H0)6Q0K4U0d0)0!7K0s4U0N0r0L7x0o0p7y190v1n6L781z392(3m1+1S1U1W6@3M2n2e2g0^2t0S7u0?7i0B0L1~193T3,5;2`3/6W7}474?3|5V53445}683y49044b0~4e5V5s8p5,5T5v8x0^4w6h6G5u5/2{5~4G793864678A3n4P6c7V6g6n8H1)6l6O5?045^8K8q8S548#5I0^4^0k8-8+4~8G5~524}6N8^8*0E5n5b0E5d8D4l5V8 0^5p8z6j5 5i8)8R4B5w9e9b4G0g8=5J3}8}9f5N9a4u5@965|9i9t608=5#5%8=4B8J5k8*5Q9v8,9s5A605Y6E8Q9b6I0!6L8|8X5~975o2e949d9G9q6q8U2e7W949l6U0T8h6Y2O6=3W0!0$0(04.