Comment calculer la similarité de chaînes en Java en utilisant la distance de Levenshtein ?

Comparaison de chaînes de similarité en Java

Comprendre la nécessité de mesures de similarité

Lorsque vous travaillez avec données texte, il devient crucial d’évaluer la similarité entre les chaînes. Cela peut s'avérer utile dans des tâches telles que l'identification du contenu en double, la recherche des résultats de recherche les plus similaires ou même l'extraction d'informations significatives à partir d'un texte. Heureusement, il existe des méthodes efficaces et bien établies en Java pour calculer la similarité des chaînes.

Présentation de la fonction de similarité

L'approche la plus courante de comparaison de chaînes consiste à calculer un indice de similarité qui quantifie le degré de ressemblance entre deux chaînes. Une mesure de similarité largement utilisée est la Distance de Levenshtein, qui calcule le nombre minimum de modifications (insertions, suppressions ou substitutions) requises pour transformer une chaîne en une autre. Cette métrique de distance est généralement normalisée dans une plage comprise entre 0 et 1, où une valeur plus élevée indique une plus grande similarité.

Mise en œuvre de la distance de Levenshtein

Une façon de calculer la distance de Levenshtein La distance s'effectue en utilisant la méthode **String.getLevenshteinDistance()** fournie par la bibliothèque **Apache Commons Text**, qui implémente le Algorithme standard de Levenshtein. Alternativement, vous pouvez également implémenter manuellement l'algorithme comme indiqué dans le code ci-dessous :

public static int editDistance(String s1, String s2) {
  int n = s1.length() + 1;
  int m = s2.length() + 1;
  int[][] matrix = new int[n][m];

  for (int i = 0; i < n; i++) {
    matrix[i][0] = i;
  }

  for (int j = 0; j < m; j++) {
    matrix[0][j] = j;
  }

  for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
      int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1, // deletion
        Math.min(
          matrix[i][j - 1] + 1, // insertion
          matrix[i - 1][j - 1] + cost // substitution
        )
      );
    }
  }

  return matrix[n - 1][m - 1];
}

Calcul de l'indice de similarité

Une fois la distance de Levenshtein calculée, la similarité l'indice peut être obtenu en le normalisant à la longueur du plus long string :

public static double similarity(String s1, String s2) {
  double longerLength = Math.max(s1.length(), s2.length());
  return 1.0 - (editDistance(s1, s2) / longerLength);
}

Conclusion

En implémentant la distance de Levenshtein et la fonction de similarité en Java, vous obtenez un outil puissant pour évaluer la similarité entre les chaînes. Cette technique trouve de nombreuses applications dans le traitement du langage naturel, l'analyse de données et d'autres domaines où la comparaison de contenus textuels est essentielle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!