Comparando cadenas con tolerancia

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

¿Hay algún tipo de marco que pueda realizar tal 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í.

    Podría usar el algoritmo de Distancia de Levenshtein .

    “La distancia de 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 permitidas como inserción, eliminación o sustitución de un solo carácter”. – Wikipedia.com

    Este es de dotnetperls.com :

    using System; ///  /// Contains approximate string matching ///  static class LevenshteinDistance { ///  /// Compute the distance between two strings. ///  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")); } } 

    De hecho, puede preferir utilizar el algoritmo de distancia Damerau-Levenshtein , que también permite la transposición de caracteres, que es un error humano común en la entrada de datos. Aquí encontrará una implementación de C #.

    No hay nada en el marco de .NET 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í, eso 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 implementaciones .NET de este algoritmo . Es bastante simple, pero te da valores reales que puedes comparar el uno con el otro.

    Otro 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 probablemente sea la implementación de Java del algoritmo de Metaphone .

    Cabe señalar que el algoritmo Metaphone ha pasado por revisiones. Hay Double Metaphone (que tiene una implementación de .NET ) 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).

    Su otra opción es comparar fonéticamente usando 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 .

    Aquí hay dos métodos que calculan la distancia de Levenshtein entre cadenas.

    La distancia de 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 permitidas como inserción, eliminación o sustitución de un solo carácter.

    Una vez que tenga el resultado, deberá 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.

      ///  /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. ///  /// The first string, used as a source. /// The second string, used as a target. /// The number of changes that need to be made to convert the first string to the second. ///  /// From http://www.merriampark.com/ldcsharp.htm ///  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]; } 

    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 que se encuentra en este artículo de wikipedia 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.

     ///  /// Calculate percentage similarity of two strings /// Source String to Compare with /// Targeted String to Compare /// Return Similarity between two strings from 0 to 1.0 ///  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))); } 

    Puede encontrar implementaciones de los algoritmos de distancia de soundex y levenshtein en el proyecto de código abierto CommonLibrary.NET .