Попытка оптимизировать нечеткое соответствие

У меня есть 250000 наименований продуктов, и я хочу попробовать сгруппировать их, то есть найти продукты с похожими названиями. Например, я мог бы иметь три продукта:

• Heinz Запеченная фасоль 400 г;
• Гц Bkd Фасоль 400 г;
• Хайнц Фасоль 400г

которые на самом деле являются одним и тем же продуктом и могут быть объединены вместе.

Мой план состоял в том, чтобы использовать реализацию расстояния Яро-Винклера для поиска совпадений. Процесс работает следующим образом:

• составить большой список всех наименований товаров в памяти;
• выбрать первый товар в списке;
• сравните его с каждым продуктом, который идет после него в списке, и рассчитайте "Jaro Score";
• сообщается о любых продуктах с высоким соответствием (скажем, 0,95f или выше);
• перейти к следующему продукту.

Так что это имеет некоторую оптимизацию в том смысле, что он соответствует каждому продукту только в одну сторону, экономя половину времени обработки.

Я закодировал это и проверил. Он отлично работает и нашел десятки совпадений для расследования.

Для сравнения 1 продукта с 2 500 000 других продуктов и расчета "показателя Jaro" требуется примерно 20 секунд. Если предположить, что мои расчеты верны, это означает, что на обработку потребуется лучшая часть года.

Очевидно, это не практично.

У меня были коллеги, изучавшие код, и им удалось на 20% улучшить скорость вычисления Jaro Score. Они сделали процесс многопоточным, и это сделало его немного быстрее. Мы также удалили некоторые части хранимой информации, сократив ее до списка названий продуктов и уникальных идентификаторов; это, казалось, не имело никакого значения для времени обработки.

С этими улучшениями мы все еще думаем, что это займет несколько месяцев, и нам нужно, чтобы это заняло часы (или несколько дней максимум).

Я не хочу вдаваться в подробности, поскольку считаю, что это не совсем актуально, но я загружаю информацию о продукте в список:

private class Product
{
    public int MemberId;
    public string MemberName;
    public int ProductId;
    public string ProductCode;
    public string ProductName;
}
private class ProductList : List<Product> { }
private readonly ProductList _pl = new ProductList();

Затем я использую следующее для обработки каждого продукта:

{Outer loop...
var match = _pl[matchCount];

for (int count = 1; count < _pl.Count; count++)
{
    var search = _pl[count];
    //Don't match products with themselves (redundant in a one-tailed match)
    if (search.MemberId == match.MemberId && search.ProductId == match.ProductId)
        continue;
    float jaro = Jaro.GetJaro(search.ProductName, match.ProductName);

    //We only log matches that pass the criteria
    if (jaro > target)
    {
        //Load the details into the grid
        var row = new string[7];
        row[0] = search.MemberName;
        row[1] = search.ProductCode;
        row[2] = search.ProductName;
        row[3] = match.MemberName;
        row[4] = match.ProductCode;
        row[5] = match.ProductName;
        row[6] = (jaro*100).ToString("#,##0.0000");
        JaroGrid.Rows.Add(row);
    }
}

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

Любые идеи для лучшего способа нечеткого соответствия этого списка продуктов?

Мне интересно, есть ли "умный" способ предварительной обработки списка для получения большинства совпадений в начале процесса сопоставления. Например, если для сравнения всех продуктов требуется 3 месяца, а для сравнения "вероятных" - всего 3 дня, мы могли бы с этим смириться.

Хорошо, две общие вещи подходят. Во-первых, да, я пользуюсь преимуществом одного процесса сопоставления. Настоящий код для этого:

for (int count = matchCount + 1; count < _pl.Count; count++)

Я сожалею о публикации исправленной версии; Я пытался немного упростить это (плохая идея).

Во-вторых, многие люди хотят видеть код Jaro, поэтому здесь идет речь (он довольно длинный и изначально не был моим - я мог бы даже где-то найти его здесь?). Кстати, мне нравится идея выйти до завершения, как только будет указано плохое совпадение. Я начну смотреть на это сейчас!

using System;
using System.Text;

namespace EPICFuzzyMatching
{
    public static class Jaro
    {
        private static string CleanString(string clean)
        {
            clean = clean.ToUpper();
            return clean;
        }

        //Gets the similarity of the two strings using Jaro distance
        //param string1 the first input string
        //param string2 the second input string
        //return a value between 0-1 of the similarity
        public static float GetJaro(String string1, String string2)
        {
            //Clean the strings, we do some tricks here to help matching
            string1 = CleanString(string1);
            string2 = CleanString(string2);

            //Get half the length of the string rounded up - (this is the distance used for acceptable transpositions)
            int halflen = ((Math.Min(string1.Length, string2.Length)) / 2) + ((Math.Min(string1.Length, string2.Length)) % 2);

            //Get common characters
            String common1 = GetCommonCharacters(string1, string2, halflen);
            String common2 = GetCommonCharacters(string2, string1, halflen);

            //Check for zero in common
            if (common1.Length == 0 || common2.Length == 0)
                return 0.0f;

            //Check for same length common strings returning 0.0f is not the same
            if (common1.Length != common2.Length)
                return 0.0f;

            //Get the number of transpositions
            int transpositions = 0;
            int n = common1.Length;
            for (int i = 0; i < n; i++)
            {
                if (common1[i] != common2[i])
                    transpositions++;
            }
            transpositions /= 2;

            //Calculate jaro metric
            return (common1.Length / ((float)string1.Length) + common2.Length / ((float)string2.Length) + (common1.Length - transpositions) / ((float)common1.Length)) / 3.0f;
        }

        //Returns a string buffer of characters from string1 within string2 if they are of a given
        //distance seperation from the position in string1.
        //param string1
        //param string2
        //param distanceSep
        //return a string buffer of characters from string1 within string2 if they are of a given
        //distance seperation from the position in string1
        private static String GetCommonCharacters(String string1, String string2, int distanceSep)
        {
            //Create a return buffer of characters
            var returnCommons = new StringBuilder(string1.Length);

            //Create a copy of string2 for processing
            var copy = new StringBuilder(string2);

            //Iterate over string1
            int n = string1.Length;
            int m = string2.Length;
            for (int i = 0; i < n; i++)
            {
                char ch = string1[i];

                //Set boolean for quick loop exit if found
                bool foundIt = false;

                //Compare char with range of characters to either side
                for (int j = Math.Max(0, i - distanceSep); !foundIt && j < Math.Min(i + distanceSep, m); j++)
                {
                    //Check if found
                    if (copy[j] == ch)
                    {
                        foundIt = true;
                        //Append character found
                        returnCommons.Append(ch);
                        //Alter copied string2 for processing
                        copy[j] = (char)0;
                    }
                }
            }
            return returnCommons.ToString();
        }
    }
}