使用Levenstein距离优化来自两个大数据集的匹配元素(将每个元素与其他元素进行比较)

Question

我目前正在处理一个问题，从另一个名为"ListB"的列表中查找列表中数据的最佳匹配项，即"ListA"。每当我发现"ListA"的元素与"ListB"中置信度和准确度为70%或更高的任何元素匹配时，我都会将列表B中匹配的字符串和列表a中的字符串添加到元组中，并将其进一步保存在数据库中。

Levenstien算法给了我一个数字，我将其与我的阈值70进行比较，如果返回的值等于或大于70%的阈值，我会将其添加到"ListA"的原始字符串元素中。

如果"ListA"one_answers"ListB"中的记录在数千个值以内，并且如果我将记录增加到一百万，那么我为这个过程编写的代码可以很好地工作。计算ListA中每个元素的距离大约需要一个小时。

我需要为巨大的数据集优化流程。请告诉我在哪里需要改进。

到目前为止，我的流程代码看起来像这个

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)的计算。随着项目数量的增加，这种情况的规模总是非常大。

您可以将其并行化，但这只是执行所需时间的一个常数。

你能找到其他基于平等的标准吗？在这种情况下，您可以使用基于哈希的算法来非常快速地创建用于检查的候选者。例如，假设你正在匹配文本文章，并且你希望几乎所有的Levenstein匹配都发生在同一日历日写的文章中，那么你可以先按日期匹配(使用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();

您可以丢弃为此编写的所有复杂代码。在处理并发或并行时，仔细考虑一下最佳设计往往是值得的。通常，常见问题都有高度紧凑的解决方案。