Comparación de cadenas de similitud en Java

111

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

Mario Ortegón
fuente

Respuestas:

82

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:

dfa
fuente
18
+1 El sitio de simmetrics ya no parece activo. Sin embargo, encontré el código en sourceforge: sourceforge.net/projects/simmetrics Gracias por el puntero.
Michael Merchant
7
El enlace "puede comprobar esto" está roto.
Kiril
1
Es por eso que Michael Merchant publicó el enlace correcto arriba.
Emilyk
2
El tarro para simmetrics en sourceforge está un poco desactualizado, github.com/mpkorstanje/simmetrics es la página de github actualizada con artefactos maven
tom91136
Para agregar al comentario de @MichaelMerchant, el proyecto también está disponible en github . Sin embargo, tampoco es muy activo allí, pero es un poco más reciente que sourceforge.
Ghurdyl
163

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:


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"
acdcjunior
fuente
11
El método de distancia de Levenshtein está disponible en org.apache.commons.lang3.StringUtils.
Cleankod
@Cleankod Ahora es parte de commons-text: commons.apache.org/proper/commons-text/javadocs/api-release/org/…
Luiz
15

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];
};
user493744
fuente
11

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

Florian Fankhauser
fuente
2
Levenshtein es ideal para unas pocas cadenas, pero no se escalará a comparaciones entre una gran cantidad de cadenas.
gasto
He usado Levenshtein en Java con cierto éxito. No he hecho comparaciones en listas enormes, por lo que puede haber un impacto en el rendimiento. También es un poco simple y podría necesitar algunos ajustes para elevar el umbral de palabras más cortas (como 3 o 4 caracteres) que tienden a verse como más similares de lo que deberían (son solo 3 ediciones de gato a perro) Tenga en cuenta que Editar distancias que se sugieren a continuación son prácticamente lo mismo: Levenshtein es una implementación particular de distancias de edición.
Ruibarbo
Aquí hay un artículo que muestra cómo combinar Levenshtein con una consulta SQL eficiente: literatejava.com/sql/fuzzy-string-search-sql
Thomas W
10

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

Thibault Debatty
fuente
3

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 .

Laurence Gonsalves
fuente
3

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.

duffymo
fuente
3

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


 }
}
Mohsen Abasi
fuente