Comment calculer la distance de Levenshtein en Java?

1. Introduction

Dans cet article, nous décrivons la distance de Levenshtein, également connue sous le nom de distance d'édition. L'algorithme expliqué ici a été conçu par un scientifique russe, Vladimir Levenshtein, en 1965.

Nous fournirons une implémentation Java itérative et récursive de cet algorithme.

2. Quelle est la distance de Levenshtein?

La distance de Levenshtein est une mesure de la dissemblance entre deux cordes. Mathématiquement, étant donné deux chaînes x et y , la distance mesure le nombre minimum de modifications de caractères nécessaires pour transformer x en y .

En règle générale, trois types de modifications sont autorisés:

  1. Insertion d'un caractère c
  2. Suppression d'un caractère c
  3. Substitution d'un caractère c par c '

Exemple: Si x = 'shot' et y = 'spot' , la distance d'édition entre les deux est de 1 car 'shot' peut être converti en 'spot' en remplaçant ' h ' par ' p '.

Dans certaines sous-classes du problème, le coût associé à chaque type de vérification peut être différent.

Par exemple, moins de coût pour la substitution avec un personnage situé à proximité sur le clavier et plus cher autrement. Pour plus de simplicité, nous considérerons que tous les coûts sont égaux dans cet article.

Certaines des applications de la distance d'édition sont:

  1. Vérificateurs d'orthographe - détecter les fautes d'orthographe dans le texte et trouver l'orthographe correcte la plus proche dans le dictionnaire
  2. Détection de plagiat (voir - Papier IEEE)
  3. Analyse ADN - trouver la similitude entre deux séquences
  4. Reconnaissance vocale (voir - Microsoft Research)

3. Formulation d'algorithme

Prenons deux chaînes x et y de longueurs m et n respectivement. Nous pouvons désigner chaque chaîne par x [1: m] et y [1: n].

Nous savons qu'à la fin de la transformation, les deux chaînes seront de longueur égale et auront des caractères correspondants à chaque position. Donc, si nous considérons le premier caractère de chaque chaîne, nous avons trois options:

  1. Substitution:
    1. Déterminez le coût ( D1 ) de la substitution de x [1] par y [1] . Le coût de cette étape serait nul si les deux caractères sont identiques. Sinon, le coût en serait un
    2. Après l'étape 1.1, nous savons que les deux chaînes commencent par le même caractère. Par conséquent, le coût total serait maintenant la somme du coût de l'étape 1.1 et du coût de transformation du reste de la chaîne x [2: m] en y [2: n]
  2. Insertion:
    1. Insérez un caractère dans x pour correspondre au premier caractère de y , le coût de cette étape serait de un
    2. Après 2.1, nous avons traité un caractère de y . Par conséquent, le coût total serait maintenant la somme du coût de l'étape 2.1 (c'est-à-dire 1) et du coût de transformation de la totalité de x [1: m] en y restants (y [2: n])
  3. Effacement:
    1. Supprimez le premier caractère de x , le coût de cette étape serait de un
    2. Après 3.1, nous avons traité un caractère de x , mais le y complet reste à traiter. Le coût total serait la somme du coût de 3,1 (c'est-à-dire 1) et du coût de transformation de x restant en y complet

La prochaine partie de la solution consiste à déterminer quelle option choisir parmi ces trois. Comme nous ne savons pas quelle option entraînerait un coût minimum à la fin, nous devons essayer toutes les options et choisir la meilleure.

4. Mise en œuvre récursive naïve

Nous pouvons voir que la deuxième étape de chaque option dans la section # 3 est principalement le même problème de distance d'édition mais sur des sous-chaînes des chaînes d'origine . Cela signifie qu'après chaque itération, nous nous retrouvons avec le même problème mais avec des chaînes plus petites .

Cette observation est la clé pour formuler un algorithme récursif. La relation de récurrence peut être définie comme:

D (x [1: m], y [1: n]) = min {

D (x [2: m], y [2: n]) + Coût de remplacement de x [1] par y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

Nous devons également définir des cas de base pour notre algorithme récursif, qui dans notre cas se produit lorsqu'une ou les deux chaînes deviennent vides:

  1. Lorsque les deux chaînes sont vides, la distance entre elles est nulle
  2. Lorsque l'une des chaînes est vide, la distance d'édition entre elles correspond à la longueur de l'autre chaîne, car nous avons besoin de ce nombre d'insertions / suppressions pour transformer l'une en l'autre:
    • Exemple: si une chaîne est «chien» et une autre chaîne est «» (vide), nous avons besoin de trois insertions dans une chaîne vide pour la rendre «chien» , ou nous avons besoin de trois suppressions dans «chien» pour la rendre vide. Par conséquent, la distance d'édition entre eux est de 3

Une implémentation naïve récursive de cet algorithme:

public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }

Cet algorithme a la complexité exponentielle. A chaque étape, nous bifurquons en trois appels récursifs, construisant une complexité O (3 ^ n) .

Dans la section suivante, nous verrons comment améliorer cela.

5. Approche de programmation dynamique

En analysant les appels récursifs, nous observons que les arguments des sous-problèmes sont des suffixes des chaînes d' origine . Cela signifie qu'il ne peut y avoir que m * n appels récursifs uniques (où m et n sont un nombre de suffixes de x et y ). Par conséquent, la complexité de la solution optimale doit être quadratique, O (m * n) .

Regardons certains des sous-problèmes (selon la relation de récurrence définie dans la section # 4):

  1. Les sous-problèmes de D (x [1: m], y [1: n]) sont D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) et D (x [2: m], y [1: n])
  2. Les sous-problèmes de D (x [1: m], y [2: n]) sont D (x [2: m], y [3: n]), D (x [1: m], y [3 : n]) et D (x [2: m], y [2: n])
  3. Les sous-problèmes de D (x [2: m], y [1: n]) sont D (x [3: m], y [2: n]), D (x [2: m], y [2 : n]) et D (x [3: m], y [1: n])

Dans les trois cas, l'un des sous-problèmes est D (x [2: m], y [2: n]). Au lieu de calculer cela trois fois comme nous le faisons dans l'implémentation naïve, nous pouvons calculer cela une fois et réutiliser le résultat chaque fois que nécessaire.

Ce problème a beaucoup de sous-problèmes qui se chevauchent, mais si nous connaissons la solution aux sous-problèmes, nous pouvons facilement trouver la réponse au problème d'origine. Par conséquent, nous avons les deux propriétés nécessaires à la formulation d'une solution de programmation dynamique, c'est-à-dire des sous-problèmes superposés et une sous-structure optimale.

Nous pouvons optimiser l'implémentation naïve en introduisant la mémorisation, c'est-à-dire stocker le résultat des sous-problèmes dans un tableau et réutiliser les résultats mis en cache.

Alternativement, nous pouvons également l'implémenter de manière itérative en utilisant une approche basée sur une table:

static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } 

Cet algorithme fonctionne nettement mieux que l'implémentation récursive. Cependant, cela implique une consommation de mémoire importante.

Cela peut en outre être optimisé en observant que nous n'avons besoin que de la valeur de trois cellules adjacentes dans le tableau pour trouver la valeur de la cellule actuelle.

6. Conclusion

Dans cet article, nous avons décrit ce qu'est la distance de Levenshtein et comment elle peut être calculée à l'aide d'une approche récursive et basée sur la programmation dynamique.

La distance de Levenshtein n'est qu'une des mesures de la similitude des chaînes, certaines des autres mesures sont la similarité cosinus (qui utilise une approche basée sur des jetons et considère les chaînes comme des vecteurs), le coefficient de dés, etc.

Comme toujours, l'implémentation complète des exemples peut être trouvée sur GitHub.