A est-il loin de Z ?

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 :

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 !

Et voici une solution proposée par l'auteur en Java:

import static java.lang.Math.min;

public class Levenshtein {
    public static void main(String[] args) {
        System.out.println(levenshteinDistance(args[0], args[1]));
    }   

    private static int levenshteinDistance(String a, String b) {
        int[][] distances = initializeArray(a, b); 
        for (int i = 1; i < a.length() + 1; i++){
            for (int j = 1; j < b.length() + 1; j++){
                distances[i][j] = a.charAt(i-1) == b.charAt(j-1) ?
                    distances[i-1][j-1] :
                    (1 + min(min(distances[i-1][j], distances[i][j-1]), distances[i-1][j-1]));            
            }   
        }       
        return distances[a.length()][b.length()];

    }

    private static int[][] initializeArray(String a, String b) {
        int[][] distances = new int[a.length()+1][b.length()+1];
        for (int i = 0; i < a.length() + 1; i++) {
            distances[i][0] = i;
        }       
        for (int j = 0; j < b.length() + 1; j++) {
            distances[0][j] = j;
        }       
        return distances;
    }       
}

Votre équipe TakiVeille