我有250万个产品名称，想要将它们分组，即找到名称相似的产品。例如，我可能有三种产品：
- Heinz烤豆400g； - Hz Bkd Beans 400g； - Heinz Beans 400g。
实际上它们是同一种产品，可以合并在一起。
我的计划是使用Jaro-Winkler距离的实现来查找匹配项。该过程如下：
- 在内存中制作所有产品名称的大列表； - 选择列表中的第一个产品； - 将其与列表中其后的每个产品进行比较，并计算“Jaro分数”； - 报告任何具有高匹配度（例如0.95f或更高）的产品； - 移动到下一个产品。
因此，这样做在优化方面有一些好处，它只单向匹配每个产品，节省了一半的处理时间。
然后我使用以下内容来处理每个产品：
我认为在这个问题的目的上，我们可以假设Jaro.GetJaro方法是一个“黑盒子”，也就是说，它的工作方式并不重要，因为这部分代码已经尽可能地进行了优化，我无法想象如何改进它。
是否有更好的方法来模糊匹配这个产品列表呢？
我想知道是否有一种“聪明”的方法来预处理列表，以便在匹配过程的开始时获得大多数匹配项。例如，如果比较所有产品需要3个月，但只需要3天来比较“可能”的产品，那么我们可以接受这种情况。
好的，有两个常见的事情出现了。首先，是的，我确实利用了单尾匹配过程。真正的代码是：
我后悔发布修改版；我试图简化一下（这是个坏主意）。
其次，很多人想看Jaro代码，那么这里就是（它相当长，它原本不是我的 - 我甚至可能在这里找到它？）。顺便说一句，我喜欢在指示出不匹配的情况下，在完成之前退出的想法。我现在会开始研究它！
- Heinz烤豆400g； - Hz Bkd Beans 400g； - Heinz Beans 400g。
实际上它们是同一种产品，可以合并在一起。
我的计划是使用Jaro-Winkler距离的实现来查找匹配项。该过程如下：
- 在内存中制作所有产品名称的大列表； - 选择列表中的第一个产品； - 将其与列表中其后的每个产品进行比较，并计算“Jaro分数”； - 报告任何具有高匹配度（例如0.95f或更高）的产品； - 移动到下一个产品。
因此，这样做在优化方面有一些好处，它只单向匹配每个产品，节省了一半的处理时间。
我编写了这个程序并进行了测试。它完美地工作，并找到了数十个匹配项需要调查。
将一个产品与其他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小时;
- 主要改进是预处理数据，只考虑与其相关联的销售数量相当高的项目。不是很好，但工作量大大减小;
- 我的笔记本电脑过热，所以我在冰箱里放了一个周末来运行大部分工作。通过这样做，我学到了冰箱不是笔记本电脑的好环境（太潮湿），我的笔记本电脑在大约一周后就死了;
- 最终结果是我达到了我想做的事情，也许不如我希望的全面，但总体上我认为它是成功的;
- 为什么我没有接受答案？嗯，实际上以下答案都没有完全解决我的初始问题，尽管它们大多有所帮助（在我首次发布此问题几年后提出的一些答案当然没有帮助），但我觉得挑选一个作为“答案”是不公平的。
O(n)而不是O(n^2)。您可能会发现这样做会使一些项变成string.Equal，这样检查起来更快。我不知道在您的领域中什么样的规范形式，但它可能涉及使用ToUpper()，纠正拼写错误和替换缩写，删除“and”等。 - Rob