Сравнение строк с допуском

Question

Я ищу способ сравнения строки с массивом строк. Выполнение точного поиска довольно легко, но я хочу, чтобы моя программа допускала орфографические ошибки, недостающие части строки и так далее.

Есть ли какие-либо рамки, которые могут выполнять такой поиск? У меня есть что-то в виду, что алгоритм поиска вернет несколько результатов по проценту соответствия или что-то вроде этого.

Answer 1

Вы можете использовать Levenshtein Distance algorithm.

«Расстояние Левенштейна между двумя строками определяется как минимальное количество исправлений, необходимых для преобразования одной строки в другую, причем допустимые операции редактирования включают вставку, удаление или замену одного символа». - Wikipedia.com

Это один из 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")); 
    } 
} 

Вы можете на самом деле предпочитают использовать Damerau-Levenshtein distance algorithm, который также позволяет персонажам транспонировать, которая является общей человеческой ошибки при вводе данных. Вы найдете реализацию C# here.

Answer 2

Ниже представлены два метода, которые вычисляют Levenshtein Distance между строками.

Левенштейна расстояние между двумя строками определяется как минимальное количество исправлений, необходимых для преобразования одной строки в другую, с допустимыми операций редактирования, являющихся вставка, удаление или замена одного символа.

Как только у вас есть результат, вам нужно определить, какое значение вы хотите использовать в качестве порога для соответствия или нет. Запустите функцию на кучу выборочных данных, чтобы получить представление о том, как она работает, чтобы принять решение о вашем конкретном пороге.

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

В .NET Framework ничего нет, что поможет вам с этим готовым к использованию.

Наиболее распространенными орфографическими ошибками являются те, где буквы являются достойным фонетическим представлением слова, но не правильное написание слова. Например, можно утверждать, что слова sword и sord (да, это слово) имеют одинаковые фонетические корни (они звучат одинаково, когда вы их произносите).

Это, как говорится, есть ряд алгоритмов, которые можно использовать для перевода слов (даже неправильно принятых) в фонетические варианты.

Первый - Soundex. Это довольно просто реализовать, и существует довольно много .NET implementations of this algorithm. Это довольно просто, но это дает вам реальные ценности, которые вы можете сравнить друг с другом.

Другое Metaphone. Хотя я не могу найти встроенную .NET-версию Metaphone, предоставленная ссылка имеет ссылки на ряд других реализаций, которые могут быть преобразованы. Проще всего конвертировать, вероятно, будет Java implementation of the Metaphone algorithm.

Следует отметить, что алгоритм Metaphone прошел ревизии.Существует Double Metaphone (у которого есть .NET implementation) и Metaphone 3. Metaphone 3 - это коммерческое приложение, но имеет коэффициент точности 98% по сравнению со скоростью 89% точности для алгоритма Double Metaphone при работе с базой данных общих английских слов. В зависимости от ваших потребностей вы можете захотеть найти (в случае Double Metaphone) или приобрести (в случае Metaphone 3) источник для алгоритма и преобразовать или получить доступ к нему через уровень P/Invoke (существуют реализации C++ имеются в большом количестве).

Метафон и Soundex отличаются тем, что Soundex производит цифровые клавиши фиксированной длины, тогда как Metaphone производит клавиши разной длины, поэтому результаты будут разными. В конце концов, оба будут делать то же самое сравнение для вас, вам просто нужно выяснить, что подходит вашим потребностям наилучшим образом, учитывая ваши требования и ресурсы (и уровни нетерпимости для орфографических ошибок, конечно).

Answer 4

Вы можете найти реализации алгоритмов soundex и levenshtein в открытом исходном коде CommonLibrary.NET project.

Answer 5

Ваш другой вариант - сравнить фонетически с помощью Soundex или Metaphone. Я только что закончил статью, в которой представлен код C# для обоих алгоритмов. Вы можете посмотреть его на http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex.

Answer 6

Вот реализация метода LevenshteinDistance, который использует гораздо меньше памяти при производстве тех же результатов. Это адаптация C# псевдокода, найденного в этом wikipedia article под заголовком «Итерация с двумя матричными строками».

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

Вот функция, которая даст вам процентное сходство.

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