c# - 检测相似电子邮件地址的最佳方法？

Question

我有一个包含大约 20,000 个电子邮件地址的列表，我知道其中一些是试图绕过“每封电子邮件 1 个”限制的欺诈性尝试，例如 username1@gmail.com、username1a@gmail.com、username1b @gmail.com 等。我想找到类似的电子邮件地址进行评估。目前，我正在使用 Levenshtein 算法来对照列表中的其他电子邮件检查每封电子邮件，并报告任何编辑距离小于 2 的电子邮件。但是，这非常慢。有没有更有效的方法？

我现在使用的测试代码是:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

namespace LevenshteinAnalyzer
{
    class Program
    {
        const string INPUT_FILE = @"C:\Input.txt";
        const string OUTPUT_FILE = @"C:\Output.txt";

        static void Main(string[] args)
        {
            var inputWords = File.ReadAllLines(INPUT_FILE);
            var outputWords = new SortedSet<string>();

            for (var i = 0; i < inputWords.Length; i++)
            {
                if (i % 100 == 0) 
                    Console.WriteLine("Processing record #" + i);

                var word1 = inputWords[i].ToLower();
                for (var n = i + 1; n < inputWords.Length; n++)
                {
                    if (i == n) continue;
                    var word2 = inputWords[n].ToLower();

                    if (word1 == word2) continue;
                    if (outputWords.Contains(word1)) continue;
                    if (outputWords.Contains(word2)) continue;
                    var distance = LevenshteinAlgorithm.Compute(word1, word2);

                    if (distance <= 2)
                    {
                        outputWords.Add(word1);
                        outputWords.Add(word2);
                    }
                }
            }

            File.WriteAllLines(OUTPUT_FILE, outputWords.ToArray());
            Console.WriteLine("Found {0} words", outputWords.Count);
        }
    }
}

编辑:我试图捕捉的一些东西看起来像:

01234567890@gmail.com
0123456789@gmail.com
012345678@gmail.com
01234567@gmail.com
0123456@gmail.com
012345@gmail.com
01234@gmail.com
0123@gmail.com
012@gmail.com

Answer 1

您可以首先对要相互比较的电子邮件应用一些优先级。

性能限制的一个关键原因是将每个地址与其他每个电子邮件地址进行比较的 O(n²) 性能。 优先级排序是提高此类搜索算法性能的关键。

例如，您可以将所有具有相似长度(+/- 某个数量)的电子邮件存储起来，然后首先比较该子集。您还可以从电子邮件中去除所有特殊字符(数字、符号)，并在减少后找到相同的字符。

您可能还想根据数据创建一个 trie，而不是逐行处理它，并使用它来查找共享一组通用后缀/前缀的所有电子邮件，并从该缩减中驱动您的比较逻辑。从您提供的示例来看，您似乎正在寻找一个地址的一部分可能显示为另一个地址中的子字符串的地址。 Tries (和 suffix trees )是执行这些类型搜索的有效数据结构。

优化此算法的另一种可能方法是使用创建电子邮件帐户的日期(假设您知道)。如果创建了重复的电子邮件，它们很可能会在短时间内彼此创建 - 这可以帮助您减少查找重复项时要执行的比较次数。