Distance de Levenshtein

Présentation du problème⚓︎

Lors de la comparaison de chaines de caractères, on cherche parfois des chaines plus ou moins proches les unes des autres. En particulier, on peut définir d'un point de vue mathématique trois opérations élémentaires permettant de passer d'une chaine à une autre :

substituer un caractère : "ABC" -> "AAC" ;
insérer un caractère : "ABC" -> "ABDC" ;
supprimer un caractère : "ABC" -> "AC".

On va supposer ici que le coût de ces opérations est le même. Le nombre d'opérations élementaires pour passer d'une chaine à une autre constitue la distance de Levenshtein.

On peut utiliser la formule récursive suivante, où on note $\|a\|$ la longueur de la chaine $a$, et $a-1$ la chaîne $a$ tronquée de sa première lettre :

\[\qquad\operatorname{lev}(a,b) = \begin{cases} \max(\|a\|,\|b\|) & \text{ si } \min(\|a\|,\|b\|)=0, \\ \operatorname{lev}(a-1,b-1) & \text{ si } a[0]=b[0], \\ 1 + \min \begin{cases} \operatorname{lev}(a-1,b)\\ \operatorname{lev}(a,b-1)\\ \operatorname{lev}(a-1,b-1) \end{cases} & \text{ sinon.} \end{cases} \]

L'objectif est d'écrire une fonction lev qui prends en paramètres deux chaînes de caractères a et b et qui renvoie un entier correspondant à la distance de Levenshtein.

Exemples

>>> lev("distance", "distance")
0
>>> lev("distance", "distante")
1
>>> lev("distance", "distances")
1
>>> lev("distance", "dispense")
3
>>> lev("distance", "pense")
6
>>> lev("distance", "haricots")
8

Les tranches

On peut obtenir un extrait d'une chaîne de caractères en désignant une tranche (slice en anglais) . Pour cela il faut indiquer le premier élément et le dernier qui ne sera pas inclus séparés par :.

🐍 Console Python

>>> mot = "tranche"
>>> mot[2:6]
'anch'
>>> mot[2:]
'anche'
>>> mot[:4]
'tran'

Aide

On pourra utiliser les fonctions native minet max

🐍 Console Python

>>> min (5, 4)
4
>>> max(1, 3, 2)
3

Évaluations restantes : 10/10

.128013:pbvà(40i2+edmx3;s7= 1o5w_lSInatf)9Oh]R6qcrg,.[éyPku8/050n0m0G0F0j0B0s0v0Q0B0F0s0s0u010G0j0c010406050s0!0o0o0F0R0X040C0x0B0!0`0x0E0v020F0o0c0r0v0N0m140R0P0!0m0s050$111315170 0c041v1C051F0$1F1H1C0 0n0j0e0/0;0?0^0L0j0S0L0B1V0L0G0}050*0d0B0m1Q0=0@011U1W1Y1W0G1(1*1$0G0d0x0n171%0R1D0G0L0/1a0s0c0F0E0^0k011,1S010H0,0m0E1i0m1$27292e1.2h1*2k0o2m040a0v0Y0R0x0c0x0s0j1d1f0(250R0R0m0Q2H1v2o0E1D0$232T0G2120220n2q0^1Y0E2j2E1$1N1P0:1-2%0j2)0E1}1O1$0c2M1D2R2T2~10281f2/2f2@0R140B0}0v0w2Q320~312p341.36383a0k3d293f2R2$013k0F39040v0q3o2S0 3r3i0^3u3w0v0h3A3q323s3G3a0y3K3C3M3E3t0x373v3a0O3R3g331R3j3W3l3x0t3#3D3(3F3*3Y3x0#3.3T3:3V3X3H0J3_3h3{3O040w0i403%2:3|3+0w3c1w3e1E2|1v2-2W0n2!3s0Q1}2w0%1O1D2{0m2}4f4e3p054o0(4w41490Z0}0(0H3K3$3s0z3a4K3/490E0H0}1*0e4P3`490|040g4X4E350}0F4%482f4!0T3K0v4L3U0E0}0d4,3s4!0I0b3R0v514=4Q4)040B1e0S0m0!0R0A4+4y2S534Y2f0x0}0u4;4?420d4U2j4{3U4!4$5f4D4-3j4*5t3{4}50525o4R4U585a5c4`5x5h4(1.5k045m5O5H355q565s5x5W1.5v5C5I045N30545%0}0I5F515$0^4G040j4J5V5.3F5Y0o2=5)4.0}5w5-5i5A565K5b5d635/044:5}683F5J0E596c5,4f5~015E6i5Q0^5S0u5U2~5P5z0^610}465#6r4!4 5x06526N6B3s5_2M0G5b0E5n6r0E600F0p6e0^5(6H6j3t6l6n5c5e676v6s0}6h6A5@6+6a6m5L0A6p4z6I5:5=6P3U5_0m1Y5|6^6X5B6)6;4!0V6$016E046G6:6C6=040M6W6*6x6z3e74424_7h7f7h7j7l6q6*4!0M6K2~6M6O5?6r6R0)6U7r6;4^5Z4W7d7n6(7m3N7c7Z5u0}7g7W3s7j4d7$5D0}7I7E7S6,6}6/7=7X0}0M6@7v6_7T6 2S6_7A7*3U7,7z7:7h7T576|6o897p5;6L6N6_760-0m8g7;3p7K7L8l0}6S7Q6u7n888y3s5S0l7R7n6Y0}616V867/4#8b5r7V7.4Z658O047_707F7(7B0j0}7-7`4|8a8L5*8d6-6d8+647p7~3p7w5*825y8)047)8R2f8A8 6f8q837b6{8.8`847|0I8?3B7L9f9g7M6*8c0m8Q8(7%8N8:698W958Y6g8F7!5+8g8~9n3{919B8S04948{4@7@8f9q6%9b9d0~9h9R8k964V8g669E559s9I8M9A8X6;9D9(7{9G8U8-7^8g7}9w9J9y9M7o0I8i7J1v4B4v4ga00$4j1v0G4la52Y2U1|1~2W0F1)a24j1B9#492M0o0A0H0F0Z0m0A0L0q0}1n1p1r1t0v9H1E3f1C0D0B0v0s000F0S2G0v0n000W0Q0R0j2M0v0j0Q0j0v0!2)0v0H1e2O0j1e0v0RaQ5b2F0e1+0n290.0;ay0B1*0va+0e0F0v140E0{0!1*0R060(0!0p0/0L0+2)0s0U0v0K1f0c5a0G25132j0Q0m0R0v28btaQaSaUa!1+a%0Ea)a+a-0Qa/1O1+1r0j064o1j151+0faZa#0Qbd2=1+280?0W1+2j0v2j2Xb#0vbSbAbcbebB0j0p0m0UaC0 a30)0+0-04.