Comparaison des chaînes de similarité en Java

Je veux comparer plusieurs chaînes entre elles et trouver celles qui sont les plus similaires. Je me demandais s'il existe une bibliothèque, une méthode ou une meilleure pratique qui me renverrait quelles chaînes sont plus similaires à d'autres chaînes. Par exemple:

• "Le renard rapide a sauté" -> "Le renard a sauté"
• "Le renard rapide a sauté" -> "Le renard"

Cette comparaison renverrait que le premier est plus similaire que le second.

Je suppose que j'ai besoin d'une méthode telle que:

double similarityIndex(String s1, String s2)

Y a-t-il une telle chose quelque part?

EDIT: Pourquoi est-ce que je fais ça? J'écris un script qui compare la sortie d'un fichier MS Project à la sortie d'un système hérité qui gère les tâches. Étant donné que l'ancien système a une largeur de champ très limitée, lorsque les valeurs sont ajoutées, les descriptions sont abrégées. Je veux un moyen semi-automatisé pour trouver quelles entrées de MS Project sont similaires aux entrées du système afin que je puisse obtenir les clés générées. Il présente des inconvénients, car il doit encore être vérifié manuellement, mais cela économiserait beaucoup de travail

Oui, il existe de nombreux algorithmes bien documentés comme:

• Similitude cosinus
• Similitude Jaccard
• Coefficient de dés
• Similitude correspondante
• Chevauchement de similarité
• etc

Un bon résumé ("Sam's String Metrics") peut être trouvé ici (lien original mort, donc il renvoie à Internet Archive)

Vérifiez également ces projets:

• Simmetrics
• jtmt

La manière courante de calculer la similitude entre deux chaînes de 0% à 100% , telle qu'elle est utilisée dans de nombreuses bibliothèques, est de mesurer combien (en%) il faudrait changer la chaîne la plus longue pour la transformer en la plus courte:

/**
 * Calculates the similarity (a number within 0 and 1) between two strings.
 */
public static double similarity(String s1, String s2) {
  String longer = s1, shorter = s2;
  if (s1.length() < s2.length()) { // longer should always have greater length
    longer = s2; shorter = s1;
  }
  int longerLength = longer.length();
  if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
  return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}
// you can use StringUtils.getLevenshteinDistance() as the editDistance() function
// full copy-paste working code is below

Calcul du editDistance():

La editDistance()fonction ci-dessus devrait calculer la distance d'édition entre les deux chaînes. Il existe plusieurs implémentations à cette étape, chacune pouvant mieux convenir à un scénario spécifique. Le plus courant est l' algorithme de distance de Levenshtein et nous l'utiliserons dans notre exemple ci-dessous (pour les très grandes chaînes, d'autres algorithmes sont susceptibles de mieux fonctionner).

Voici deux options pour calculer la distance d'édition:

• Vous pouvez utiliser l' implémentation de la distance Levenshtein par Apache Commons Text : apply(CharSequence left, CharSequence rightt)
• Mettez-le en œuvre vous-même. Vous trouverez ci-dessous un exemple d'implémentation.

Exemple de travail:

Voir la démo en ligne ici.

public class StringSimilarity {

  /**
   * Calculates the similarity (a number within 0 and 1) between two strings.
   */
  public static double similarity(String s1, String s2) {
    String longer = s1, shorter = s2;
    if (s1.length() < s2.length()) { // longer should always have greater length
      longer = s2; shorter = s1;
    }
    int longerLength = longer.length();
    if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
    /* // If you have Apache Commons Text, you can use it to calculate the edit distance:
    LevenshteinDistance levenshteinDistance = new LevenshteinDistance();
    return (longerLength - levenshteinDistance.apply(longer, shorter)) / (double) longerLength; */
    return (longerLength - editDistance(longer, shorter)) / (double) longerLength;

  }

  // Example implementation of the Levenshtein Edit Distance
  // See http://rosettacode.org/wiki/Levenshtein_distance#Java
  public static int editDistance(String s1, String s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[] costs = new int[s2.length() + 1];
    for (int i = 0; i <= s1.length(); i++) {
      int lastValue = i;
      for (int j = 0; j <= s2.length(); j++) {
        if (i == 0)
          costs[j] = j;
        else {
          if (j > 0) {
            int newValue = costs[j - 1];
            if (s1.charAt(i - 1) != s2.charAt(j - 1))
              newValue = Math.min(Math.min(newValue, lastValue),
                  costs[j]) + 1;
            costs[j - 1] = lastValue;
            lastValue = newValue;
          }
        }
      }
      if (i > 0)
        costs[s2.length()] = lastValue;
    }
    return costs[s2.length()];
  }

  public static void printSimilarity(String s, String t) {
    System.out.println(String.format(
      "%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t));
  }

  public static void main(String[] args) {
    printSimilarity("", "");
    printSimilarity("1234567890", "1");
    printSimilarity("1234567890", "123");
    printSimilarity("1234567890", "1234567");
    printSimilarity("1234567890", "1234567890");
    printSimilarity("1234567890", "1234567980");
    printSimilarity("47/2010", "472010");
    printSimilarity("47/2010", "472011");
    printSimilarity("47/2010", "AB.CDEF");
    printSimilarity("47/2010", "4B.CDEFG");
    printSimilarity("47/2010", "AB.CDEFG");
    printSimilarity("The quick fox jumped", "The fox jumped");
    printSimilarity("The quick fox jumped", "The fox");
    printSimilarity("kitten", "sitting");
  }

}

Production:

1.000 is the similarity between "" and ""
0.100 is the similarity between "1234567890" and "1"
0.300 is the similarity between "1234567890" and "123"
0.700 is the similarity between "1234567890" and "1234567"
1.000 is the similarity between "1234567890" and "1234567890"
0.800 is the similarity between "1234567890" and "1234567980"
0.857 is the similarity between "47/2010" and "472010"
0.714 is the similarity between "47/2010" and "472011"
0.000 is the similarity between "47/2010" and "AB.CDEF"
0.125 is the similarity between "47/2010" and "4B.CDEFG"
0.000 is the similarity between "47/2010" and "AB.CDEFG"
0.700 is the similarity between "The quick fox jumped" and "The fox jumped"
0.350 is the similarity between "The quick fox jumped" and "The fox"
0.571 is the similarity between "kitten" and "sitting"

J'ai traduit l' algorithme de distance de Levenshtein en JavaScript:

String.prototype.LevenshteinDistance = function (s2) {
    var array = new Array(this.length + 1);
    for (var i = 0; i < this.length + 1; i++)
        array[i] = new Array(s2.length + 1);

    for (var i = 0; i < this.length + 1; i++)
        array[i][0] = i;
    for (var j = 0; j < s2.length + 1; j++)
        array[0][j] = j;

    for (var i = 1; i < this.length + 1; i++) {
        for (var j = 1; j < s2.length + 1; j++) {
            if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1];
            else {
                array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1);
                array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1);
            }
        }
    }
    return array[this.length][s2.length];
};

Vous pouvez utiliser la distance de Levenshtein pour calculer la différence entre deux chaînes. http://en.wikipedia.org/wiki/Levenshtein_distance

Il existe en effet de nombreuses mesures de similarité de chaînes:

• Distance d'édition de Levenshtein;
• Distance Damerau-Levenshtein;
• Similitude Jaro-Winkler;
• Distance d'édition la plus longue de la sous-séquence commune;
• Q-Gram (Ukkonen);
• distance n-gramme (Kondrak);
• Index Jaccard;
• Coefficient Sorensen-Dice;
• Similitude cosinus;
• ...

Vous pouvez trouver une explication et une implémentation java de ceux-ci ici: https://github.com/tdebatty/java-string-similarity

Vous pouvez y parvenir en utilisant la bibliothèque java apache commons . Jetez un œil à ces deux fonctions:
- getLevenshteinDistance
- getFuzzyDistance

Théoriquement, vous pouvez comparer les distances d'édition .

Cela se fait généralement à l'aide d'une mesure de distance d'édition . La recherche de «modifier la distance java» ouvre un certain nombre de bibliothèques, comme celle-ci .

Cela me semble être un outil de recherche de plagiat si votre chaîne se transforme en document. Peut-être qu'une recherche avec ce terme donnera quelque chose de bien.

"Programming Collective Intelligence" comprend un chapitre sur la question de savoir si deux documents sont similaires. Le code est en Python, mais il est propre et facile à porter.

Merci au premier répondant, je pense qu'il y a 2 calculs de computeEditDistance (s1, s2). En raison du temps passé, a décidé d'améliorer les performances du code. Alors:

public class LevenshteinDistance {

public static int computeEditDistance(String s1, String s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[] costs = new int[s2.length() + 1];
    for (int i = 0; i <= s1.length(); i++) {
        int lastValue = i;
        for (int j = 0; j <= s2.length(); j++) {
            if (i == 0) {
                costs[j] = j;
            } else {
                if (j > 0) {
                    int newValue = costs[j - 1];
                    if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
                        newValue = Math.min(Math.min(newValue, lastValue),
                                costs[j]) + 1;
                    }
                    costs[j - 1] = lastValue;
                    lastValue = newValue;
                }
            }
        }
        if (i > 0) {
            costs[s2.length()] = lastValue;
        }
    }
    return costs[s2.length()];
}

public static void printDistance(String s1, String s2) {
    double similarityOfStrings = 0.0;
    int editDistance = 0;
    if (s1.length() < s2.length()) { // s1 should always be bigger
        String swap = s1;
        s1 = s2;
        s2 = swap;
    }
    int bigLen = s1.length();
    editDistance = computeEditDistance(s1, s2);
    if (bigLen == 0) {
        similarityOfStrings = 1.0; /* both strings are zero length */
    } else {
        similarityOfStrings = (bigLen - editDistance) / (double) bigLen;
    }
    //////////////////////////
    //System.out.println(s1 + "-->" + s2 + ": " +
      //      editDistance + " (" + similarityOfStrings + ")");
    System.out.println(editDistance + " (" + similarityOfStrings + ")");
}

public static void main(String[] args) {
    printDistance("", "");
    printDistance("1234567890", "1");
    printDistance("1234567890", "12");
    printDistance("1234567890", "123");
    printDistance("1234567890", "1234");
    printDistance("1234567890", "12345");
    printDistance("1234567890", "123456");
    printDistance("1234567890", "1234567");
    printDistance("1234567890", "12345678");
    printDistance("1234567890", "123456789");
    printDistance("1234567890", "1234567890");
    printDistance("1234567890", "1234567980");

    printDistance("47/2010", "472010");
    printDistance("47/2010", "472011");

    printDistance("47/2010", "AB.CDEF");
    printDistance("47/2010", "4B.CDEFG");
    printDistance("47/2010", "AB.CDEFG");

    printDistance("The quick fox jumped", "The fox jumped");
    printDistance("The quick fox jumped", "The fox");
    printDistance("The quick fox jumped",
            "The quick fox jumped off the balcany");
    printDistance("kitten", "sitting");
    printDistance("rosettacode", "raisethysword");
    printDistance(new StringBuilder("rosettacode").reverse().toString(),
            new StringBuilder("raisethysword").reverse().toString());
    for (int i = 1; i < args.length; i += 2) {
        printDistance(args[i - 1], args[i]);
    }


 }
}

Vous pouvez également utiliser l'algorithme z pour rechercher une similitude dans la chaîne. Cliquez ici https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/