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

в .NET framework нет ничего, что поможет вам с этим из коробки.

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

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

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

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

другое метафон. Хотя я не могу найти родную .NET-реализацию Metaphone, ссылка даны ссылки на несколько других реализаций, которые могут быть преобразованы. Самый простой для преобразования, вероятно, будет Java реализация алгоритма Metaphone.

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

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

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

вот два метода, которые вычисляют Расстояние Левенштейна между строк.

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

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

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

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

вы можете найти реализации алгоритмов soundex и расстояния Левенштейна в открытом исходном коде CommonLibrary.NET проект.