¿Cómo calcular la medida de similitud de distancia de dos cadenas dadas?

Question

Necesito calcular la similitud entre 2 cadenas. Entonces, ¿qué quiero decir exactamente? Me explico con un ejemplo:

• La palabra real: hospital
• palabra equivocada: haspita

Ahora mi objetivo es determinar cuántos personajes tengo que modificar la palabra equivocada para obtener el palabra real. En este ejemplo, necesito modificar 2 letras. Entonces, ¿cuál sería el porcentaje? Tomo la longitud de la palabra real siempre. Entonces se convierte en 2/8 = 25%, por lo que estos 2 DSM de cuerda dados son 75%.

¿Cómo puedo lograr esto teniendo en cuenta el rendimiento?

Answer 1

Lo que está buscando se llama editar distancia o Levenshtein distance. El artículo de wikipedia explica cómo se calcula, y tiene una buena pieza de pseudocódigo en la parte inferior para ayudarte a codificar este algoritmo en C# muy fácilmente.

Aquí es una implementación del primer sitio vinculado a continuación:

private static int CalcLevenshteinDistance(string a, string b) 
    { 
    if (String.IsNullOrEmpty(a) || String.IsNullOrEmpty(b)) return 0; 

    int lengthA = a.Length; 
    int lengthB = b.Length; 
    var distances = new int[lengthA + 1, lengthB + 1]; 
    for (int i = 0; i <= lengthA; distances[i, 0] = i++); 
    for (int j = 0; j <= lengthB; distances[0, j] = j++); 

    for (int i = 1; i <= lengthA; i++) 
     for (int j = 1; j <= lengthB; j++) 
      { 
      int cost = b[j - 1] == a[i - 1] ? 0 : 1; 
      distances[i, j] = Math.Min 
       (
       Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1), 
       distances[i - 1, j - 1] + cost 
       ); 
      } 
    return distances[lengthA, lengthB]; 
    } 

Answer 2

Hay un gran número de algoritmos de distancia de similitud de cadenas que se pueden utilizar. Algunos señaladas aquí (pero que no figuran de manera exhaustiva son):

• Levenstein
• Needleman Wunch
• Smith Waterman
• Smith Waterman Gotoh
• Jaro, Jaro Winkler
• Jaccard Similarity
• Euclidean Distance
• Dados Similitud
• Cosine Similarity
• Monge Elkan

Una biblioteca que contiene la aplicación de todos estos se llama SimMetrics que tiene tanto Java y C# implementaciones.

Answer 3

Acabo de abordar este mismo problema hace unas semanas. Como alguien está preguntando ahora, compartiré el código. En mis exhaustivas pruebas, mi código es aproximadamente 10 veces más rápido que el ejemplo de C# en Wikipedia, incluso cuando no se proporciona una distancia máxima. Cuando se proporciona una distancia máxima, esta ganancia de rendimiento aumenta a 30x - 100x +. Tenga en cuenta un par de puntos clave para el rendimiento:

• Si necesita comparar las mismas palabras una y otra vez, primero convierta las palabras en matrices de enteros. El algoritmo Damerau-Levenshtein incluye muchas>, <, == comparaciones, y ints se comparan mucho más rápido que chars.
• Incluye un mecanismo de cortocircuito con renunciar si la distancia supera un máximo proporcionado
• utilizar un conjunto rotativo de tres matrices en lugar de una matriz masiva como en todas las implementaciones que he visto en otros lugares
• Asegúrese de que su las matrices cortan el ancho de palabra más corto.

Código (funciona igual la exacta si se reemplaza int[] con String en las declaraciones de parámetros:

/// <summary> 
/// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of 
/// integers, where each integer represents the code point of a character in the source string. 
/// Includes an optional threshhold which can be used to indicate the maximum allowable distance. 
/// </summary> 
/// <param name="source">An array of the code points of the first string</param> 
/// <param name="target">An array of the code points of the second string</param> 
/// <param name="threshold">Maximum allowable distance</param> 
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns> 
public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) { 

    int length1 = source.Length; 
    int length2 = target.Length; 

    // Return trivial case - difference in string lengths exceeds threshhold 
    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; } 

    // Ensure arrays [i]/length1 use shorter length 
    if (length1 > length2) { 
     Swap(ref target, ref source); 
     Swap(ref length1, ref length2); 
    } 

    int maxi = length1; 
    int maxj = length2; 

    int[] dCurrent = new int[maxi + 1]; 
    int[] dMinus1 = new int[maxi + 1]; 
    int[] dMinus2 = new int[maxi + 1]; 
    int[] dSwap; 

    for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; } 

    int jm1 = 0, im1 = 0, im2 = -1; 

    for (int j = 1; j <= maxj; j++) { 

     // Rotate 
     dSwap = dMinus2; 
     dMinus2 = dMinus1; 
     dMinus1 = dCurrent; 
     dCurrent = dSwap; 

     // Initialize 
     int minDistance = int.MaxValue; 
     dCurrent[0] = j; 
     im1 = 0; 
     im2 = -1; 

     for (int i = 1; i <= maxi; i++) { 

      int cost = source[im1] == target[jm1] ? 0 : 1; 

      int del = dCurrent[im1] + 1; 
      int ins = dMinus1[i] + 1; 
      int sub = dMinus1[im1] + cost; 

      //Fastest execution for min value of 3 integers 
      int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del); 

      if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2]) 
       min = Math.Min(min, dMinus2[im2] + cost); 

      dCurrent[i] = min; 
      if (min < minDistance) { minDistance = min; } 
      im1++; 
      im2++; 
     } 
     jm1++; 
     if (minDistance > threshold) { return int.MaxValue; } 
    } 

    int result = dCurrent[maxi]; 
    return (result > threshold) ? int.MaxValue : result; 
} 

Dónde Swap es:

static void Swap<T>(ref T arg1,ref T arg2) { 
    T temp = arg1; 
    arg1 = arg2; 
    arg2 = temp; 
} 

Answer 4

Aquí es un enfoque alternativo:

Esto es demasiado largo para un comentario.

Un método típico para encontrar similitudes es la distancia de Levenshtein, y no hay duda de que hay una biblioteca con código disponible.

Lamentablemente, esto requiere una comparación con cada cadena. Es posible que pueda escribir una versión especializada del código para provocar un cortocircuito en el cálculo, si la distancia es mayor que algún umbral, aún tendría que hacer todas las comparaciones.

Otra idea es usar alguna variante de trigramas o n-grams. Estas son secuencias de n caracteres (o n palabras o n secuencias genómicas o n lo que sea). Mantenga un mapeo de trigramas en cadenas y elija los que tienen la mayor superposición. Una elección típica de n es "3", de ahí el nombre.

Por ejemplo, Inglés tendría estos trigramas:

• Eng
• ngl
• gli
• lis
• ish

E Inglaterra tendría:

• Eng
• ngl
• gla
• lan
• y

Bueno, 2 de 7 (o 4 de 10) partido. Si esto funciona para usted, puede indexar la tabla trigram/string y obtener una búsqueda más rápida.

También puede combinar esto con Levenshtein para reducir el conjunto de comparación a aquellos que tienen un número mínimo de n-grams en común.

Answer 5

Aquí está mi implementación de Damerau Levenshtein Distance, que no solo devuelve el coeficiente de similitud, sino que también devuelve ubicaciones de error en la palabra corregida (esta característica se puede usar en editores de texto). También mi implementación admite diferentes pesos de errores (sustitución, eliminación, inserción, transposición).

public static List<Mistake> OptimalStringAlignmentDistance(
    string word, string correctedWord, 
    bool transposition = true, 
    int substitutionCost = 1, 
    int insertionCost = 1, 
    int deletionCost = 1, 
    int transpositionCost = 1) 
{ 
    int w_length = word.Length; 
    int cw_length = correctedWord.Length; 
    var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1]; 
    var result = new List<Mistake>(Math.Max(w_length, cw_length)); 

    if (w_length == 0) 
    { 
     for (int i = 0; i < cw_length; i++) 
      result.Add(new Mistake(i, CharMistakeType.Insertion)); 
     return result; 
    } 

    for (int i = 0; i <= w_length; i++) 
     d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None); 

    for (int j = 0; j <= cw_length; j++) 
     d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None); 

    for (int i = 1; i <= w_length; i++) 
    { 
     for (int j = 1; j <= cw_length; j++) 
     { 
      bool equal = correctedWord[j - 1] == word[i - 1]; 
      int delCost = d[i - 1, j].Key + deletionCost; 
      int insCost = d[i, j - 1].Key + insertionCost; 
      int subCost = d[i - 1, j - 1].Key; 
      if (!equal) 
       subCost += substitutionCost; 
      int transCost = int.MaxValue; 
      if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1]) 
      { 
       transCost = d[i - 2, j - 2].Key; 
       if (!equal) 
        transCost += transpositionCost; 
      } 

      int min = delCost; 
      CharMistakeType mistakeType = CharMistakeType.Deletion; 
      if (insCost < min) 
      { 
       min = insCost; 
       mistakeType = CharMistakeType.Insertion; 
      } 
      if (subCost < min) 
      { 
       min = subCost; 
       mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution; 
      } 
      if (transCost < min) 
      { 
       min = transCost; 
       mistakeType = CharMistakeType.Transposition; 
      } 

      d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType); 
     } 
    } 

    int w_ind = w_length; 
    int cw_ind = cw_length; 
    while (w_ind >= 0 && cw_ind >= 0) 
    { 
     switch (d[w_ind, cw_ind].Value) 
     { 
      case CharMistakeType.None: 
       w_ind--; 
       cw_ind--; 
       break; 
      case CharMistakeType.Substitution: 
       result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution)); 
       w_ind--; 
       cw_ind--; 
       break; 
      case CharMistakeType.Deletion: 
       result.Add(new Mistake(cw_ind, CharMistakeType.Deletion)); 
       w_ind--; 
       break; 
      case CharMistakeType.Insertion: 
       result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion)); 
       cw_ind--; 
       break; 
      case CharMistakeType.Transposition: 
       result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition)); 
       w_ind -= 2; 
       cw_ind -= 2; 
       break; 
     } 
    } 
    if (d[w_length, cw_length].Key > result.Count) 
    { 
     int delMistakesCount = d[w_length, cw_length].Key - result.Count; 
     for (int i = 0; i < delMistakesCount; i++) 
      result.Add(new Mistake(0, CharMistakeType.Deletion)); 
    } 

    result.Reverse(); 

    return result; 
} 

public struct Mistake 
{ 
    public int Position; 
    public CharMistakeType Type; 

    public Mistake(int position, CharMistakeType type) 
    { 
     Position = position; 
     Type = type; 
    } 

    public override string ToString() 
    { 
     return Position + ", " + Type; 
    } 
} 

public enum CharMistakeType 
{ 
    None, 
    Substitution, 
    Insertion, 
    Deletion, 
    Transposition 
} 

Este código es una parte de mi proyecto: Yandex-Linguistics.NET.

escribí algunos tests y se está me parece que el método funciona.

Pero los comentarios y observaciones son bienvenidos.

Answer 6

Aquí hay una aplicación VB.net:

Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer 
    Dim cost(v1.Length, v2.Length) As Integer 
    If v1.Length = 0 Then 
     Return v2.Length    'if string 1 is empty, the number of edits will be the insertion of all characters in string 2 
    ElseIf v2.Length = 0 Then 
     Return v1.Length    'if string 2 is empty, the number of edits will be the insertion of all characters in string 1 
    Else 
     'setup the base costs for inserting the correct characters 
     For v1Count As Integer = 0 To v1.Length 
      cost(v1Count, 0) = v1Count 
     Next v1Count 
     For v2Count As Integer = 0 To v2.Length 
      cost(0, v2Count) = v2Count 
     Next v2Count 
     'now work out the cheapest route to having the correct characters 
     For v1Count As Integer = 1 To v1.Length 
      For v2Count As Integer = 1 To v2.Length 
       'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required) 
       'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 
       'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and 
       cost(v1Count, v2Count) = Math.Min(
        cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1), 
        Math.Min(
         cost(v1Count - 1, v2Count) + 1, 
         cost(v1Count, v2Count - 1) + 1 
        ) 
       ) 
      Next v2Count 
     Next v1Count 

     'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix 
     'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length) 
     Return cost(v1.Length, v2.Length) 
    End If 
End Function 

Answer 7

he encontrado que Levenshtein y Jaro Winkler son grandes para las pequeñas diferencias betwen cadenas como:

• errores de ortografía; o
• ö en lugar de o en nombre de una persona.

Sin embargo al comparar algo así como títulos de los artículos en trozos significativos del texto sería el mismo pero con "ruido" en los bordes, Smith-Waterman-Gotoh ha sido fantástica:

comparar estos 2 títulos (que son los mismos pero redactado de manera diferente a partir de diferentes fuentes):

Un endonucleasa de Escherichia coli que introduce escisiones de cadena de polinucleótido única en el ADN ultravioleta irradiados

endonucleasa III: una endonucleasa de Escherichia coli que introduce escisiones única cadena de polinucleótido en ultravioleta irradiados ADN

This site that provides algorithm comparison de las cadenas de muestra:

• Levenshtein: 81
• Smith- Waterman Gotoh
• Jaro Winkler 78

Jaro Winkler y Levenshtein no son tan competentes como los de Smith Waterman Gotoh en la detección de la similitud. Si comparamos dos títulos que no son el mismo artículo, pero tienen algunos textos coincidentes:

Metabolismo de las grasas en las plantas superiores. La función de tioesterasas de acilo en el metabolismo de acil-coenzimas A y proteína portadora de acilo-acil s

metabolismo de grasa en las plantas superiores. La determinación de proteína portadora acil-acilo y acil coenzima A en una mezcla de lípidos complejo

Jaro Winkler da un falso positivo, pero Smith Waterman Gotoh no:

• Levenshtein: 54
• Smith-Waterman Gotoh
• Jaro Winkler 89

Como se mencionó Anastasiosyal, SimMetrics tiene el código java para estos algoritmos. Tuve éxito usando el SmithWatermanGotoh java code from SimMetrics.