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

.128013s3Oo_;8bcdufvgI/0lyàq n7apS.r1meh,(P2=4:+twki9][5Rx)é6050k0G0Q0z0T0s0b0w0j0s0z0b0b0M010Q0T0A010406050b0l0F0F0z0D0t040B0e0s0l0`0e0x0w020z0F0A0g0w0Y0G140D0v0l0G0b050q111315170 0A041v1C051F0q1F1H1C0 0k0T0n0/0;0?0^0H0T0o0H0s1V0H0Q0}050*0i0s0G1Q0=0@011U1W1Y1W0Q1(1*1$0Q0i0e0k171%0D1D0Q0H0/1a0b0A0z0x0^0L011,1S010m0,0G0x1i0G1$27292e1.2h1*2k0F2m040a0w0K0D0e0A0e0b0T1d1f0(250D0D0G0j2H1v2o0x1D0q232T0Q2120220k2q0^1Y0x2j2E1$1N1P0:1-2%0T2)0x1}1O1$0A2M1D2R2T2~10281f2/2f2@0D140s0}0w0E2Q320~312p341.36383a0L3d293f2R2$013k0z39040w0c3o2S0 3r3i0^3u3w0w0N3A3q323s3G3a0X3K3C3M3E3t0e373v3a0$3R3g331R3j3W3l3x0y3#3D3(3F3*3Y3x0h3.3T3:3V3X3H0U3_3h3{3O040E0r403%2:3|3+0E3c1w3e1E2|1v2-2W0k2!3s0j1}2w0%1O1D2{0G2}4f4e3p054o0(4w41490S0}0(0m3K3$3s0R3a4K3/490x0m0}1*0n4P3`490|040J4X4E350}0z4%482f4!0I3K0w4L3U0x0}0i4,3s4!0!0O3R0w514=4Q4)040s1e0o0G0l0D0f4+4y2S534Y2f0e0}0M4;4?420i4U2j4{3U4!4$5f4D4-3j4*5t3{4}50525o4R4U585a5c4`5x5h4(1.5k045m5O5H355q565s5x5W1.5v5C5I045N30545%0}0!5F515$0^4G040T4J5V5.3F5Y0F2=5)4.0}5w5-5i5A565K5b5d635/044:5}683F5J0x596c5,4f5~015E6i5Q0^5S0M5U2~5P5z0^610}465#6r4!4 5x06526N6B3s5_2M0Q5b0x5n6r0x600z0Z6e0^5(6H6j3t6l6n5c5e676v6s0}6h6A5@6+6a6m5L0f6p4z6I5:5=6P3U5_0G1Y5|6^6X5B6)6;4!0W6$016E046G6:6C6=040V6W6*6x6z3e74424_7h7f7h7j7l6q6*4!0V6K2~6M6O5?6r6R0)6U7r6;4^5Z4W7d7n6(7m3N7c7Z5u0}7g7W3s7j4d7$5D0}7I7E7S6,6}6/7=7X0}0V6@7v6_7T6 2S6_7A7*3U7,7z7:7h7T576|6o897p5;6L6N6_760-0G8g7;3p7K7L8l0}6S7Q6u7n888y3s5S0P7R7n6Y0}616V867/4#8b5r7V7.4Z658O047_707F7(7B0T0}7-7`4|8a8L5*8d6-6d8+647p7~3p7w5*825y8)047)8R2f8A8 6f8q837b6{8.8`847|0!8?3B7L9f9g7M6*8c0G8Q8(7%8N8:698W958Y6g8F7!5+8g8~9n3{919B8S04948{4@7@8f9q6%9b9d0~9h9R8k964V8g669E559s9I8M9A8X6;9D9(7{9G8U8-7^8g7}9w9J9y9M7o0!8i7J1v4B4v4ga00q4j1v0Q4la52Y2U1|1~2W0z1)a24j1B9#492M0F0f0m0z0S0G0f0H0c0}1n1p1r1t0w9H1E3f1C0p0s0w0b000z0o2G0w0k000#0j0D0T2M0w0T0j0T0w0l2)0w0m1e2O0T1e0w0DaQ5b2F0n1+0k290.0;ay0s1*0wa+0n0z0w140x0{0l1*0D060(0l0Z0/0H0+2)0b0C0w0d1f0A5a0Q25132j0j0G0D0w28btaQaSaUa!1+a%0xa)a+a-0ja/1O1+1r0T064o1j151+0uaZa#0jbd2=1+280?0#1+2j0w2j2Xb#0wbSbAbcbebB0T0Z0G0CaC0 a30)0+0-04.