Comparación de cadenas de similitud en Java

Quiero comparar varias cadenas entre sí y encontrar las que sean más similares. Me preguntaba si hay alguna biblioteca, método o mejor práctica que me devuelva qué cadenas son más similares a otras cadenas. Por ejemplo:

• "El zorro rápido saltó" -> "El zorro saltó"
• "El zorro rápido saltó" -> "El zorro"

Esta comparación devolvería que el primero es más similar que el segundo.

Supongo que necesito algún método como:

double similarityIndex(String s1, String s2)

¿Existe tal cosa en alguna parte?

EDITAR: ¿Por qué estoy haciendo esto? Estoy escribiendo un script que compara la salida de un archivo de MS Project con la salida de algún sistema heredado que maneja tareas. Debido a que el sistema heredado tiene un ancho de campo muy limitado, cuando se agregan los valores, las descripciones se abrevian. Quiero alguna forma semiautomática de encontrar qué entradas de MS Project son similares a las entradas en el sistema para poder obtener las claves generadas. Tiene inconvenientes, ya que todavía tiene que verificarse manualmente, pero ahorraría mucho trabajo

Sí, hay muchos algoritmos bien documentados como:

• Similitud de coseno
• Similitud de Jaccard
• Coeficiente de dados
• Similitud coincidente
• Similitud de superposición
• etcétera etcétera

Puede encontrar un buen resumen ("Métricas de cadenas de Sam") aquí (el enlace original está inactivo, por lo que se enlaza con Internet Archive)

Consulte también estos proyectos:

• Simmetrics
• jtmt

La forma común de calcular la similitud entre dos cadenas de una manera 0% -100% , como se usa en muchas bibliotecas, es medir cuánto (en%) tendrías que cambiar la cadena más larga para convertirla en la más corta:

/**
 * 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

Calcular el editDistance():

Se editDistance()espera que la función anterior calcule la distancia de edición entre las dos cadenas. Hay varias implementaciones para este paso, cada una puede adaptarse mejor a un escenario específico. El más común es el algoritmo de distancia de Levenshtein y lo usaremos en nuestro ejemplo a continuación (para cadenas muy grandes, es probable que otros algoritmos funcionen mejor).

Aquí hay dos opciones para calcular la distancia de edición:

• Puede utilizar la implementación de Apache Commons Text de la distancia de Levenshtein: apply(CharSequence left, CharSequence rightt)
• Impleméntelo en su propia cuenta. A continuación encontrará una implementación de ejemplo.

Ejemplo de trabajo:

Vea la demostración en línea aquí.

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");
  }

}

Salida:

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"

Traduje el algoritmo de distancia 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];
};

Puede usar la distancia de Levenshtein para calcular la diferencia entre dos cadenas. http://en.wikipedia.org/wiki/Levenshtein_distance

De hecho, existen muchas medidas de similitud de cadenas:

• Distancia de edición de Levenshtein;
• Distancia Damerau-Levenshtein;
• Similitud Jaro-Winkler;
• Distancia de edición de la subsecuencia común más larga;
• Q-Gram (Ukkonen);
• distancia de n-gramos (Kondrak);
• Índice de Jaccard;
• Coeficiente de Sorensen-Dice;
• Similitud de coseno;
• ...

Puede encontrar una explicación y la implementación de Java de estos aquí: https://github.com/tdebatty/java-string-similarity

Puede lograr esto usando la biblioteca java de apache commons . Eche un vistazo a estas dos funciones dentro de él:
- getLevenshteinDistance
- getFuzzyDistance

Teóricamente, puede comparar distancias de edición .

Normalmente, esto se hace mediante una medida de distancia de edición . La búsqueda de "java de distancia de edición" muestra una serie de bibliotecas, como esta .

Me suena como un buscador de plagio si su cadena se convierte en un documento. Tal vez la búsqueda con ese término arroje algo bueno.

"Programación de la inteligencia colectiva" tiene un capítulo sobre la determinación de si dos documentos son similares. El código está en Python, pero es limpio y fácil de portar.

Gracias al primer contestador, creo que hay 2 cálculos de computeEditDistance (s1, s2). Debido al gran gasto de tiempo, decidió mejorar el rendimiento del código. Entonces:

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]);
    }


 }
}

También puede usar el algoritmo z para encontrar similitudes en la cadena. Haga clic aquí https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/