我有 2,500,000 个产品名称，我想尝试将它们组合在一起，即查找具有相似名称的产品。例如，我可以拥有三种产品：
- 亨氏焗豆 400g;
- Hz Bkd 豆 400g;
- 亨氏豆 400g。
它们实际上是相同的产品，可以合并在一起。
我的计划是使用Jaro-Winkler 距离的实现来查找匹配项。该过程如下：
- 列出内存中所有产品名称的大清单；
- 选择列表中的第一个产品；
- 将其与列表中紧随其后的每个产品进行比较并计算“Jaro 分数”；
- 报告任何具有高匹配度（例如 0.95f 或更高）的产品；
- 转到下一个产品。
所以这有一些优化，因为它只匹配每个产品的一种方式，节省了一半的处理时间。
我对此进行了编码并进行了测试。它运行良好，并找到了数十个匹配项进行调查。
将 1 个产品与 2,500,000 个其他产品进行比较并计算“Jaro 分数”大约需要 20 秒。假设我的计算是正确的，这意味着完成处理需要一年的大部分时间。
显然这是不切实际的。
我让同事检查了代码，他们设法将 Jaro 分数计算部分的速度提高了 20%。他们使该过程成为多线程的，这使它更快一点。我们还删除了一些存储的信息，将其简化为产品名称和唯一标识符列表；这似乎对处理时间没有任何影响。
有了这些改进，我们仍然认为这需要几个月的时间来处理，我们需要几个小时（或最多几天）。
我不想介绍太多细节，因为我认为这并不完全相关，但我将产品详细信息加载到列表中：
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();
}
}
}
看到这个问题仍然有一些观点，我想我会快速更新发生的事情：
- 我真的希望我最初发布了我正在使用的实际代码，因为人们仍然告诉我要进行一半的迭代（显然没有阅读超过第一段左右的内容）；
- 我采纳了这里提出的一些建议，以及 SO 以外的其他人提出的一些建议，并将运行时间缩短到 70 小时左右；
- 主要的改进是对数据进行预处理，只考虑具有相当高销售额的商品。不是很好，但它使工作量大大减少；
- 我的笔记本电脑过热时遇到了问题，所以我在一个周末用冰箱里的笔记本电脑完成了大部分工作。在这样做的过程中，我了解到冰箱不是笔记本电脑的好环境（太潮湿），大约一周后我的笔记本电脑就死了；
- 最终结果是我实现了我打算做的事情，也许没有我希望的那么全面，但总的来说，我认为这是成功的；
- 为什么我不接受答案？好吧，实际上下面的答案都没有完全解决我最初的问题，虽然它们大多有帮助（在我第一次发布这个问题后的几年里出现的一些答案肯定没有帮助），我觉得选择一个作为“答案”是不公平的”。