Ric*_*ell 15 c# algorithm grouping duplicates fuzzy-logic
我有2,500,000个产品名称,我想尝试将它们组合在一起,即找到名称相似的产品.例如,我可以有三种产品:
这实际上是相同的产品,可以合并在一起.
我的计划是使用Jaro Winkler的距离算法来实现匹配.该过程如下:
所以这有一些优化,因为它只对每个产品进行单向匹配,节省了一半的处理时间.
我把它编码并测试了它.它运作完美,并发现了数十个匹配的调查.
将1个产品与2,500,000个其他产品进行比较需要大约20秒钟,并计算出"Jaro评分".假设我的计算是正确的,这意味着它将花费一年的最佳时间来完成处理.
显然这不实用.
我让同事们查看代码,他们设法将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();
}
}
}
首先，它看起来像“外循环”也在循环_pl，因为你有一个matchCount然后从中取出一个match。
如果我是正确的，那么你的循环计数器count应该从 开始matchCount，这样你就不会测试 a 与 b，然后再测试 b 与 a。它将消除您在循环顶部检查某个项目本身的需要，并将迭代次数减少一半。
有些人说你应该预处理你的匹配字符串，这样你就不会重复类似的操作ToUpper。如果你这样做了，你还可以做一些其他的事情（可能很小）。
在匹配字符串中搜索双字母。如果找到任何内容，请将它们从匹配字符串中删除，但标记您已这样做（存储字母加倍的索引列表）。在 内部GetCommonCharacters，与该字母的单个剩余实例进行比较时，只需在循环结束条件中添加 1 即可。随后的比较也需要针对丢失的字母进行调整。具体来说，让你的循环从i - distanceSep到i + distanceSep + 1（当然保留最小和最大检查）。
假设您string1包含“ee”，其中distanceSep1 个。您无需进行 6 次比较，而是节省了 4 个，即 33%。越高，节省的金额就越大distanceSep。如果是 2，您将从 10 减少到 6，节省 40%。
如果这令人困惑的话，举个例子。string1有“ee”，string2只有“abcd”，所以它不匹配。distanceSep是 1. 不必比较“e/a”、“e/b”、“e/c”...然后比较“e/b”、“e/c”、“e/d”，而是杀死第二个“e” string1，并且仅将 e 与所有四个字母进行比较。