C # поиск с сходством / близостью

Question

Предположим, у нас есть IEnumerable Collection с 20 000 человек предметов. Затем предположим, что мы создали еще один объект Person.

Мы хотим перечислить всех лиц, которые составляют этого человека. Это означает, например, что если сродство Фамилия превышает 90% , добавьте этого Человека в список.

например. ("Андрей" против "Андре")

Какой самый эффективный / быстрый способ сделать это?

Итерация сбора и сравнения char по char с определением сходства? ИЛИ ЖЕ? Есть идеи?

Спасибо!

Answer 1

Вас может заинтересовать:

Алгоритм расстояния Левенштейна

Питер Норвиг - Как написать корректор орфографии (вам будет интересна часть, где он сравнивает слово с набором существующих слов)

Answer 2

Я предоставляю исходный код этого метода Affinity:

        /// <summary>
        /// Compute Levenshtein distance according to the Levenshtein Distance Algorithm
        /// </summary>
        /// <param name="s">String 1</param>
        /// <param name="t">String 2</param>
        /// <returns>Distance between the two strings.
        /// The larger the number, the bigger the difference.
        /// </returns>
        private static int Compare(string s, string t)
        {
            /* if both string are not set, its uncomparable. But others fields can still match! */
            if (string.IsNullOrEmpty(s) && string.IsNullOrEmpty(t)) return 0;

            /* if one string has value and the other one hasn't, it's definitely not match */
            if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return -1;

            s = s.ToUpper().Trim();
            t = t.ToUpper().Trim();

            int n = s.Length;
            int m = t.Length;
            int[,] d = new int[n + 1, m + 1];

            int cost;

            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++)
                {
                    cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);

                    d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                              d[i - 1, j - 1] + cost);
                }
            }

            return d[n, m];
        }

это означает, что если возвращается 0, 2 строки идентичны.

Answer 3

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

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

Базовая подпись для вашей функции привязки может выглядеть следующим образом:

bool IsAffinityMatch(string p1, string p2)

И тогда ваш поиск будет выглядеть так:

MyPersonCollection.Where(p => IsAffinityMatch(p.Surname, OtherPerson.Surname));

Answer 4

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

Тем не менее, вам придется реализовать логику сравнения самостоятельно, и если вам нужна большая степень гибкости (или если вам нужно найти работу над производительностью), вы можете посмотреть на что-то вроде Lucene .Net . Большинство механизмов текстового поиска, с которыми я встречался и работал, были в большей степени основаны на файлах, но я думаю, что вы также можете индексировать объекты в памяти (однако я не уверен в этом).

Удачи!