尝试优化模糊匹配

我有 2,500,000 个产品名称，我想尝试将它们组合在一起，即查找具有相似名称的产品。 例如，我可以有三个产品：

• 亨氏焗豆 400g;
• 赫兹豆 400克;
• 亨氏豆 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 小时;
• 主要改进是预处理数据，只考虑附加了相当多的销售量的项目。不是很好，但它使工作量大大减小;
• 我的笔记本电脑过热了，所以我在一个周末用冰箱里的笔记本电脑完成了大部分工作。在这样做的过程中，我了解到冰箱不适合笔记本电脑（太潮湿），大约一周后我的笔记本电脑就死了;
• 最终结果是我实现了我打算做的事情，也许没有我希望的那么全面，但总的来说，我会认为它是成功的;
• 为什么我不接受答案？好吧，下面的答案实际上都没有完全解决我最初的问题，尽管它们大多有帮助（在我第一次发布这个问题多年后出现的一些答案肯定没有帮助），但我觉得选择一个作为"答案"是不公平的。