Четыре алгоритма нечеткого поиска в c#. Сравнение строк

Перевод статьи Four Functions for Finding Fuzzy String Matches in C# Extensions

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

В поисках ответов на эти вопросы, я нашёл единственный полезный ресурс от George M. Brown на www.codeguru.com, который реализовал четыре широко известных и мощных алгоритмов для нечеткого сравнения строк для VBA.

Ссылки на Wikipedia на описание алгоритмов:

• Dice Coefficient
• Levenshtein Distance
• Longest Common Subsequence
• Double Metaphone

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

Совпадение имен для (опечатка намеренно): «Jensn»
Первый набор результатов теста представляет собой результат работы алгоритмов сверку моей фамилия с очепяткой  со списком других фамилий. Я выделил лучший результат.

Dice Coefficient для Jensn:
.00000 для Adams
.46154 для Benson
.00000 для Geralds
.37500 для Johannson
.42857 для Johnson
.76923 для Jensen
.30769 для Jordon
.30769 для Madsen
.00000 для Stratford
.14286 для Wilkins

Levenshtein Edit Distance для Jensn:
    4 для Adams
2 для Benson
5 для Geralds
5 для Johannson
3 для Johnson
1 для Jensen
4 для Jordon
4 для Madsen
8 для Stratford
6 для Wilkins

Longest Common Subsequence для Jensn:
    .04000, s для Adams
.33333, ensn для Benson
.05714, es для Geralds
.08889, jnsn для Johannson
.17143, jnsn для Johnson
.56667, jensn для Jensen
    .06667, jn для Jordon
.13333, en для Madsen
.02222, s для Stratford
.11429, ns для Wilkins

Double Metaphone для Jensn: ANSN
    ATMS metaphone для Adams
PNSN metaphone для Benson
JRLT metaphone для Geralds
AHNS metaphone для Johannson
    ANSN metaphone для Johnson
    ANSN metaphone для Jensen
    ARTN metaphone для Jordon
MTSN metaphone для Madsen
STTR metaphone для Stratford
FLKN metaphone для Wilkins

Поиск совпадения адреса для «2130 South Fort Union Blvd.»
Второй тест ищет совпадения для адреса. Смотрим результаты:

Dice Coefficient for 2130 South Fort Union Blvd.:
.16000 для 2689 East Milkin Ave.
.10000 для 85 Morrison
.27273 для 2350 North Main
.07843 для 567 West Center Street
 .66667 для 2130 Fort Union Boulevard
 .61538 для 2310 S. Ft. Union Blvd.
.42553 для 98 West Fort Union
.12245 для Rural Route 2 Box 29
.05000 для PO Box 3487
.04444 для 3 Harvard Square

Levenshtein Edit Distance for 2130 South Fort Union Blvd.:
18 для 2689 East Milkin Ave.
22 для 85 Morrison
18 для 2350 North Main
22 для 567 West Center Street
11 для 2130 Fort Union Boulevard
8 для 2310 S. Ft. Union Blvd.
14 для 98 West Fort Union
19 для Rural Route 2 Box 29
22 для PO Box 3487
22 для 3 Harvard Square

Longest Common Subsequence для 2130 South Fort Union Blvd.:
.02116, 2 st in v. для 2689 East Milkin Ave.
.02020,  son для 85 Morrison
.04444, 230 oth in для 2350 North Main
.01010,  st t  для 567 West Center Street
.25481, 2130 fort union blvd для 2130 Fort Union Boulevard
.25765, 230 s ft union blvd. для 2310 S. Ft. Union Blvd.
.25514,  st fort union для 98 West Fort Union
.02593,  out  o  для Rural Route 2 Box 29
.01347, o o  для PO Box 3487
.01389, 3 hrvd для 3 Harvard Square

Double Metaphone for 2130 South Fort Union Blvd.: STFR
STML metaphone для 2689 East Milkin Ave.
MRSN metaphone для 85 Morrison
NRTM metaphone для 2350 North Main
SSNT metaphone для 567 West Center Street
FRTN metaphone для 2130 Fort Union Boulevard
SFTN metaphone для 2310 S. Ft. Union Blvd.
STFR metaphone для 98 West Fort Union
RRLR metaphone для Rural Route 2 Box 29
PPKS metaphone для PO Box 3487
RFRT metaphone для 3 Harvard Square

Как видите алгоритм Double Metaphone не столь полезен сам по себе как другие алгоритмы, но в связке с другими можно получить мощный результат.

Пример использования алгоритмов:

private static void NameMatching()
{
    //name matching
    string input = "Jensn";
    string[] surnames = new string[] { 
        "Adams",
        "Benson",
        "Geralds",
        "Johannson",
        "Johnson",
        "Jensen",
        "Jordon",
        "Madsen",
        "Stratford",
        "Wilkins"
        };

    Console.WriteLine("Dice Coefficient for Jensn:");
    foreach (var name in surnames)
    {
        double dice = input.DiceCoefficient(name);
        Console.WriteLine("\t{0} against {1}", 
            dice.ToString("###,###.00000"), name);
    }

    Console.WriteLine();
    Console.WriteLine("Levenshtein Edit Distance for Jensn:");
    foreach (var name in surnames)
    {
        int leven = input.LevenshteinDistance(name);
        Console.WriteLine("\t{0} against {1}", leven, name);
    }

    Console.WriteLine();
    Console.WriteLine("Longest Common Subsequence for Jensn:");
    foreach (var name in surnames)
    {
        var lcs = input.LongestCommonSubsequence(name);
        Console.WriteLine("\t{0}, {1} against {2}", 
            lcs.Item2.ToString("###,###.00000"), lcs.Item1, name);
    }

    Console.WriteLine();
    string mp = input.ToDoubleMetaphone();
    Console.WriteLine("Double Metaphone for Jensn: {0}", mp);
    foreach (var name in surnames)
    {
        string nameMp = name.ToDoubleMetaphone();
        Console.WriteLine("\t{0} metaphone for {1}", nameMp, name);
    }
}

Скачать исходники:  Алгоритмы нечеткого поиска (2056 Загрузок)