Оптимизировать сопоставление элементов из двух больших наборов данных, используя расстояние Левенштейна (сравнивая каждый элемент друг с другом)

Question

В настоящее время я работаю над проблемой, чтобы найти наилучшие совпадения данных в списке, а именно «ListA» из другого списка под названием «ListB».Всякий раз, когда я нахожу совпадение элемента для «ListA» с любым элементом в «ListB», который имеет достоверность и точность с 70% или выше, я добавляю совпавшую строку из списка B и строку в списке A к кортежу, который я далеесохранить в базе данных.

Алгоритм Левенштьена дает мне число, которое я сравниваю с моим порогом 70, и если возвращаемые значения равны или превышают 70-процентный порог, я добавляю его к исходному строковому элементу «ListA».

Код, который я написал для этого процесса, работает нормально, если записи в «ListA» и «ListB» находятся в пределах тысяч значений, и если я увеличиваю записи до миллиона, для расчета расстояния для каждого из них требуется около часа.элемент списка А.

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

Мой код для процесса до сих пор выглядит следующим образом

  public static PerformFuzzyMatch()
  {
    // Fetch the ListA & List B from SQL tables
     var ListACount = await FuzzyMatchRepo.FetchListACount();
     var ListB = await FuzzyMatchRepo.FetchListBAsync();

    //Split the ListA data to smaller chunks and loop through those chunks 
     var splitGroupSize = 1000;
     var sourceDataBatchesCount = ListACount / splitGroupSize;

     // Loop through the smaller chunks of List A
     for (int b = 0; b < sourceDataBatchesCount; b++)
     {
       var currentBatchMatchedWords = new List<Tuple<string, string, double>>();
       int skipRowCount = b * splitGroupSize;
       int takeRowCount = splitGroupSize;

       // Get chunks of data from ListA according to the skipRowCount and takeRowCount
   var currentSourceDataBatch = FuzzyMatchRepository.FetchSourceDataBatch(skipRowCount, takeRowCount);

 //Loop through the ListB and parallely calculate the distance between chunks of List A and List B data
   for (int i = 0; i < ListB.Count; i++)
   {
     Parallel.For(
      0,
      currentSourceDataBatch.Count,
      new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 10 },
      cntr =>
      {
         try
         {
            //call the Levenshtien Algorithm to calculate the distance between each element of ListB and the smaller chunk of List A.
              int leven = LevenshteinDistance(currentSourceDataBatch[cntr], ListB[i]);
              int length = Math.Max(currentSourceDataBatch[cntr].Length, ListB[i].Length);
              double similarity = double similarity = 1.0 - (double)leven / length;
              if ((similarity * 100) >= 70)
              {
     currentBatchMatchedWords.Add(Tuple.Create(currentSourceDataBatch[cntr], ListB[i], similarity));
            }
          cntr++;
         }
        catch (Exception ex)
        {
         exceptions.Enqueue(ex);
        }
      });
     }
   }
  }

И алгоритм, который он вызывает, чтобы вычислить расстояние:

public static int LevenshteinDistance(this string input, string comparedTo, bool caseSensitive = false)
    {
        if (string.IsNullOrWhiteSpace(input) || string.IsNullOrWhiteSpace(comparedTo))
        {
            return -1;
        }

        if (!caseSensitive)
        {
            input = Common.Hashing.InvariantUpperCaseStringExtensions.ToUpperInvariant(input);
            comparedTo = Common.Hashing.InvariantUpperCaseStringExtensions.ToUpperInvariant(comparedTo);
        }

        int inputLen = input.Length;
        int comparedToLen = comparedTo.Length;

        int[,] matrix = new int[inputLen, comparedToLen];

        //initialize           
        for (var i = 0; i < inputLen; i++)
        {
            matrix[i, 0] = i;
        }
        for (var i = 0; i < comparedToLen; i++)
        {
            matrix[0, i] = i;
        }

        //analyze
        for (var i = 1; i < inputLen; i++)
        {
            ushort si = input[i - 1];
            for (var j = 1; j < comparedToLen; j++)
            {
                ushort tj = comparedTo[j - 1];
                int cost = (si == tj) ? 0 : 1;

                int above = matrix[i - 1, j];
                int left = matrix[i, j - 1];
                int diag = matrix[i - 1, j - 1];
                int cell = FindMinimumOptimized(above + 1, left + 1, diag + cost);

                //transposition
                if (i > 1 && j > 1)
                {
                    int trans = matrix[i - 2, j - 2] + 1;
                    if (input[i - 2] != comparedTo[j - 1])
                    {
                        trans++;
                    }
                    if (input[i - 1] != comparedTo[j - 2])
                    {
                        trans++;
                    }
                    if (cell > trans)
                    {
                        cell = trans;
                    }
                }
                matrix[i, j] = cell;
            }
        }
        return matrix[inputLen - 1, comparedToLen - 1];
    }

Реализация минимального оптимизированного поиска

public static int FindMinimumOptimized(int a, int b, int c)
    {
        return Math.Min(a, Math.Min(b, c));
    }

Answer 1

Это вычисление, которое по своей природе имеет квадратичную стоимость O(N^2).Это всегда будет очень плохо масштабироваться при увеличении количества элементов.

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

Можете ли вы найти некоторыеДругой критерий для сравнения основан на равенстве?В этом случае вы можете использовать алгоритм на основе хеша, чтобы очень быстро создать кандидатов для проверки.Например, если вы сопоставляете текстовые статьи и ожидаете, что почти все совпадения Левенштейна будут встречаться в статьях, написанных в один и тот же календарный день, то вы можете сначала сопоставить по дате (используя сложность O (N)) и только затем квадратично сравнить всепредметы этого дня.Вы также можете сравнить элементы за предыдущий и следующий день, чтобы учесть некоторый провал.

Если вы не можете этого сделать, вы должны принять квадратичное масштабирование.

Хороший шаблон кода таков:

var pairs = (from a in listA
             from b in listB //cross product
             select new { a, b });

var matches = 
 pairs
 .AsParallel()
 .Where(pair => IsLevenshteinMatch(pair))
 .ToList();

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