Comparación de cadenas con tolerancia

Question

Estoy buscando una forma de comparar una cadena con una matriz de cadenas. Hacer una búsqueda exacta es bastante fácil, por supuesto, pero quiero que mi programa tolere los errores ortográficos, las partes faltantes de la cadena, etc.

¿Existe algún tipo de marco que pueda realizar dicha búsqueda? Estoy teniendo algo en cuenta que el algoritmo de búsqueda devolverá algunos resultados ordenados por el porcentaje de coincidencia o algo así.

Answer 1

Puede utilizar el Levenshtein Distance algorithm.

"La distancia de Levenshtein entre dos cadenas se define como la cantidad mínima de ediciones necesarias para transformar una cadena en otra, con las operaciones de edición permitidas siendo la inserción, eliminación o sustitución de un solo carácter." - Wikipedia.com

Éste es de dotnetperls.com:

using System; 

/// <summary> 
/// Contains approximate string matching 
/// </summary> 
static class LevenshteinDistance 
{ 
    /// <summary> 
    /// Compute the distance between two strings. 
    /// </summary> 
    public static int Compute(string s, string t) 
    { 
     int n = s.Length; 
     int m = t.Length; 
     int[,] d = new int[n + 1, m + 1]; 

     // Step 1 
     if (n == 0) 
     { 
      return m; 
     } 

     if (m == 0) 
     { 
      return n; 
     } 

     // Step 2 
     for (int i = 0; i <= n; d[i, 0] = i++) 
     { 
     } 

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

     // Step 3 
     for (int i = 1; i <= n; i++) 
     { 
      //Step 4 
      for (int j = 1; j <= m; j++) 
      { 
       // Step 5 
       int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 

       // Step 6 
       d[i, j] = Math.Min(
        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
        d[i - 1, j - 1] + cost); 
      } 
     } 
     // Step 7 
     return d[n, m]; 
    } 
} 

class Program 
{ 
    static void Main() 
    { 
     Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant")); 
     Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha")); 
     Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax")); 
    } 
} 

Es posible que, de hecho, prefieren utilizar el Damerau-Levenshtein distance algorithm, que también permite a los personajes pueden transponer, que es un error humano común en la entrada de datos. Encontrará una implementación de C# here.

Answer 2

Aquí hay dos métodos que calculan el Levenshtein Distance entre cadenas.

La distancia Levenshtein entre dos cadenas se define como el número mínimo de ediciones necesarias para transformar una cadena en la otra, con las operaciones de edición permisibles siendo inserción, deleción o sustitución de un solo carácter.

Una vez que tenga el resultado, tendrá que definir qué valor desea usar como umbral para una coincidencia o no. Ejecute la función en un grupo de datos de muestra para tener una buena idea de cómo funciona para ayudar a decidir sobre su umbral particular.

/// <summary> 
    /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. 
    /// </summary> 
    /// <param name="first">The first string, used as a source.</param> 
    /// <param name="second">The second string, used as a target.</param> 
    /// <returns>The number of changes that need to be made to convert the first string to the second.</returns> 
    /// <remarks> 
    /// From http://www.merriampark.com/ldcsharp.htm 
    /// </remarks> 
    public static int LevenshteinDistance(string first, string second) 
    { 
     if (first == null) 
     { 
      throw new ArgumentNullException("first"); 
     } 
     if (second == null) 
     { 
      throw new ArgumentNullException("second"); 
     } 

     int n = first.Length; 
     int m = second.Length; 
     var d = new int[n + 1, m + 1]; // matrix 

     if (n == 0) return m; 
     if (m == 0) return n; 

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

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

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

      for (int j = 1; j <= m; j++) 
      { 
       int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost 
       d[i, j] = Math.Min(
        Math.Min(
         d[i - 1, j] + 1, 
         d[i, j - 1] + 1), 
        d[i - 1, j - 1] + cost); 
      } 
     } 

     return d[n, m]; 
    } 

Answer 3

No hay nada en .NET framework que lo ayude con este out-of-the-box.

Los errores ortográficos más comunes son aquellos en los que las letras son una representación fonética decente de la palabra, pero no la ortografía correcta de la palabra.

Por ejemplo, podría argumentarse que las palabras sword y sord (sí, que es una palabra) tienen las mismas raíces fonéticas (suenan igual cuando las pronuncias).

Dicho esto, hay una serie de algoritmos que puede utilizar para traducir palabras (incluso mal) en variantes fonéticas.

El primero es Soundex. Es bastante simple de implementar y hay un buen número de .NET implementations of this algorithm. Es bastante simple, pero te da valores reales que puedes comparar el uno con el otro.

Otra es Metaphone. Si bien no puedo encontrar una implementación .NET nativa de Metaphone, el enlace provisto tiene enlaces a otras implementaciones que podrían convertirse. El más fácil de convertir sería probablemente el Java implementation of the Metaphone algorithm.

Cabe señalar que el algoritmo de Metaphone ha pasado por revisiones.Hay Double Metaphone (que tiene un .NET implementation) y Metaphone 3. Metaphone 3 es una aplicación comercial, pero tiene una tasa de precisión del 98% en comparación con una tasa de precisión del 89% para el algoritmo Double Metaphone cuando se ejecuta en una base de datos de palabras comunes en inglés. Dependiendo de su necesidad, es posible que desee buscar (en el caso de Double Metaphone) o comprar (en el caso de Metaphone 3) la fuente para el algoritmo y convertirlo o acceder a él a través de la capa P/Invoke (hay implementaciones C++ abundar).

Metaphone y Soundex difieren en el sentido de que Soundex produce claves numéricas de longitud fija, mientras que Metaphone produce claves de diferente longitud, por lo que los resultados serán diferentes. Al final, ambos harán el mismo tipo de comparación para usted, solo tiene que averiguar cuál se adapta mejor a sus necesidades, dados sus requisitos y recursos (y los niveles de intolerancia para los errores ortográficos, por supuesto).

Answer 4

Puede encontrar implementaciones de los algoritmos de distancia de soundex y levenshtein en la fuente abierta CommonLibrary.NET project.

Answer 5

Su otra opción es comparar fonéticamente utilizando Soundex o Metaphone. Acabo de completar un artículo que presenta el código C# para ambos algoritmos. Puede verlo en http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex.

Answer 6

Aquí hay una implementación del método LevenshteinDistance que usa mucha menos memoria y produce los mismos resultados. Esta es una adaptación de C# del pseudo código encontrado en este wikipedia article bajo el encabezado "Iterativo con dos filas de matriz".

public static int LevenshteinDistance(string source, string target) 
{ 
    // degenerate cases 
    if (source == target) return 0; 
    if (source.Length == 0) return target.Length; 
    if (target.Length == 0) return source.Length; 

    // create two work vectors of integer distances 
    int[] v0 = new int[target.Length + 1]; 
    int[] v1 = new int[target.Length + 1]; 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for (int i = 0; i < v0.Length; i++) 
     v0[i] = i; 

    for (int i = 0; i < source.Length; i++) 
    { 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1; 

     // use formula to fill in the rest of the row 
     for (int j = 0; j < target.Length; j++) 
     { 
      var cost = (source[i] == target[j]) ? 0 : 1; 
      v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost)); 
     } 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     for (int j = 0; j < v0.Length; j++) 
      v0[j] = v1[j]; 
    } 

    return v1[target.Length]; 
} 

Aquí hay una función que le dará el porcentaje de similitud.

/// <summary> 
/// Calculate percentage similarity of two strings 
/// <param name="source">Source String to Compare with</param> 
/// <param name="target">Targeted String to Compare</param> 
/// <returns>Return Similarity between two strings from 0 to 1.0</returns> 
/// </summary> 
public static double CalculateSimilarity(string source, string target) 
{ 
    if ((source == null) || (target == null)) return 0.0; 
    if ((source.Length == 0) || (target.Length == 0)) return 0.0; 
    if (source == target) return 1.0; 

    int stepsToSame = LevenshteinDistance(source, target); 
    return (1.0 - ((double)stepsToSame/(double)Math.Max(source.Length, target.Length))); 
}