Cette semaine, c'est Renaud qui vous propose un #KataOfTheWeek : Distance de Levenshtein

Briefing du Kata : L'objectif de ce kata est de coder la fonction d(A, B) renvoyant la distance de Levenshtein entre 2 chaînes de caractères A et B. Comme il s'agit d'un exercice compliqué, plusieurs indices vous sont donnés ci-dessous. Vous pouvez chercher par vous-mêmes évidemment, ou ne lire qu'une partie des indices, pour plus de challenge !

Cet exercice est un classique de Programmation Dynamique, c'est-à-dire que, pour le résoudre, il va falloir le décomposer en sous-problèmes plus simples. Une bonne méthode pour la programmation dynamique consiste à partir des cas limite, et à voir comment on peut étendre ces résultats.

Indice 1

Ici, on peut facilement trouver la distance entre 2 chaînes vides : d("", "") = 0 (ce qui est logique, la distance de Levenshtein étant une distance mathématique, d(A, A) = 0).

De la même façon, on peut trouver la distance entre une chaîne vide et une chaîne B de longueur l : d("", B) = l. Pour passer d'une chaîne vide à une chaîne de longueur l, il faut ajouter l caractères.

Reste la question de comment on peut étendre ces résultats.

Pour l'instant, on sait que d("", "") = 0, d("", "t") = 1, d("", "ta") = 2, etc. On peut résumer ce que l'on sait dans un tableau à double entrée :

levenshtein1

Chaque cellule (i, j) du tableau contient la distance entre les i premiers caractères de A et les j premiers caractères de B. Ce que nous cherchons se situe dans la case en bas à droite du tableau, il ne nous reste qu'à arriver à remplir cette case, en partant des cases déja remplies.

Indice 2

On peut désormais résumer le problème à "Si l'on connait la distance entre A et B, la distance entre A+x et B, et la distance entre A et B+y (où x et y sont des caractères), comment trouver la distance entre A+x et B+y ?". Ou "Comment remplir la case du tableau qui nous intéresse en partant des cases adjacentes dont on connaît les valeurs ?".

Si x est égal à y, la distance entre A+x et B+y est égale à la distance entre A et B. (Par exemple, la distance entre abc et ac est de 1, donc la distance entre abcd et acd est aussi de 1).

À l'inverse, si x n'est pas égal à y, cela signifie que, pour passer de A+x à B+y, il y a 3 solutions :

  • substituer x par y (la distance sera donc égale à d(A, B) + 1)
  • ajouter y à B (la distance sera donc égale à d(A+x, B) + 1)
  • ajouter x à A (la distance sera donc égale à d(A, B+y) + 1)

Il faut alors choisir la meilleure solution, c'est-à-dire celle qui minimise la distance.

Saurez-vous résoudre le problème ?

Bon courage ! Retrouvez la solution dans cet article 😉