检测相似电子邮件地址的最佳方法是什么？

Question

我有一个 ~20,000 个电子邮件地址的列表，其中一些是为了绕过“每个电子邮件1次”的限制而故意制造的欺诈性尝试，例如 [e-mail]、[e-mail]、[e-mail] 等。我希望找到类似的电子邮件地址进行评估。目前我正在使用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);
        }
    }
}

编辑: 我想要捕获的一些内容看起来像这样：

[e-mail]
[e-mail]
[e-mail]
[e-mail]
[e-mail]
[e-mail]
[e-mail]
[e-mail]
[e-mail]

- Chris

---

当您有两个属于不同人的相似电子邮件时会发生什么？ - JYelton

这就是为什么我会将列表提供给人类进行评估的原因... - Chris

不要费力了。一旦用户发现你正在寻找类似的地址，他们就会创建其他地址。你可以从mailinator.com（和它支持的众多别名）获得一百万个地址。 - Samuel Neff

同意Sam的说法，你不能太在意这个。我可以注册[e-mail]和[e-mail]，而你的系统也不会收到它们。最好禁止所有mailinator地址（@mailinator.com + 它们提供的其他10个域名...），或者连那些slopsbox地址（他们提供了100多个不同的域名，所以要更长一点）都一并禁止。此外，有可能你会阻止一些真实的用户，例如一个不太奇怪的情况是，[e-mail]和[e-mail]其实是两个不同的人。即使你之后将列表交给一个人来判断，他怎么分辨呢？ - nico

分析器告诉你瓶颈在哪里？ - Eric Lippert

Answer 1

你可以先对需要比较的邮件进行一些优先级排序。

性能受限的一个关键原因是每个地址都要与其他每个电子邮件地址进行比较，这种算法的性能为O(n²)。 优先排序是提高这种搜索算法性能的关键。

例如，您可以将所有长度类似（+/-某些量）的电子邮件分为一组，并首先比较该子集。您还可以从电子邮件中删除所有特殊字符（数字、符号），并查找在此缩减后相同的电子邮件。

您还可以从数据中创建Trie（字典树），而不是逐行处理它，并使用它来查找共享一组公共后缀/前缀的所有电子邮件，并从该缩减驱动您的比较逻辑。从您提供的示例中，看起来您正在寻找其中一个地址的一部分可能出现为另一个地址的子字符串的地址。 Tries（和后缀树）是执行这些类型搜索的有效数据结构。

优化此算法的另一个可能方法是使用电子邮件帐户创建日期（假设您知道它）。如果创建重复电子邮件，则很可能在彼此之间的短时间内创建 - 这可能有助于您减少查找重复项时要执行的比较数量。

- LBushkin

Answer 2

您可以进行一些优化，假设Levenshtein差异是瓶颈所在。

1）当Levenshtein距离为2时，电子邮件之间的长度将在2个字符以内，因此，除非abs(length(email1)-length(email2)) <= 2，否则不要进行距离计算。

2）同样，对于距离为2，不会有超过2个字符不同，因此您可以创建电子邮件中字符的哈希集，并获取两者的并集长度减去交集的长度。 （我相信这是SymmetricExceptWith）。 如果结果> 2，则跳到下一个比较。

或者

编写自己的Levenshtein距离算法。 如果您只对长度http://en.wikipedia.org/wiki/Levenshtein_distance。

- Jeff B

Answer 3

您可以添加一些优化措施：

1）保留一个已知欺诈者列表并首先进行比较。在算法运行后，您可能能够更快地与此列表匹配而不是主列表。

2）首先对列表进行排序。相比之下，这不会花费太长时间，并且会增加匹配字符串前面的机会。将其按域名首先排序，然后按用户名排序。也许将每个域放在自己的桶中，然后进行排序并与该域进行比较。

3）考虑通常剥离域名。例如，[e-mail]和[e-mail]永远不会触发您的标记。

- corsiKa

---

我实际上已经在做第一和第二点。第三点似乎更多考虑准确性而非性能。 - Chris

你经常使用 toLower。考虑在开始之前对整个数组执行 toLower，这样就不必每次都执行它了。 - corsiKa

Answer 4

如果您可以将其映射到某个k维空间，并在该空间中定义适当的范数，那么这就简化为所有最近邻问题，可以在O(n log n)时间内解决。

然而，找到这样的映射可能很困难。也许有人会拿这个部分答案并运用它。

- Thomas

Answer 5

为了完整起见，您还应考虑电子邮件地址的语义，包括：

1. Gmail将user.name和username视为相同，因此两者都是属于同一用户的有效电子邮件地址。其他服务也可能会这样做。LBushkin建议去除特殊字符可以帮助解决此问题。

2. 子地址可能会使您的过滤器失效，如果用户意识到这一点。在比较之前，您需要删除子地址数据。

- roguesys

---

我会建议（以Gmail为例）解析地址或加号，并从+到@之间的所有内容删除，然后删除“.”，最后去除所有重复项。显然，你无法从这个过程中倒推回去，所以它将变成一个元组，其中第一个是唯一键，第二个是原始值，第三个是修改后的值，然后使用元组的第三个序列的列表进行操作。不知道，这就是我的方法，但要根据可用提供者的潜在子地址方案来确定。当然，用户可以轻松地生成他们想要的任何地址，因为他们拥有自己的域名。 - jcolebrand

Answer 6

你可能想查看完整的数据集，以查看那些存在欺骗邮件的账户之间是否存在其他共性。

我不知道你的应用程序具体功能，但如果有其他关键点，则可以使用这些点来筛选要比较的地址。

- NotMe

Answer 7

首先将所有内容排序到哈希表中。键应该是电子邮件的域名；“gmail.com”。从值中剥离特殊字符，如上所述。

然后将所有gmail.com与彼此进行比较。这应该会快得多。不要比较长度相差超过3个字符的内容。

作为第二步，检查所有键并将它们分组。 （例如，gmail.com == googlemail.com。）

- Dean J

Answer 8

我同意其他人关于比较电子邮件地址并不是很有帮助的评论，因为用户可以创建看起来完全不同的欺诈性地址。

我认为更好的方法是提出其他解决方案，例如限制每小时/每天您可以写下的电子邮件数量，或者在您收到这些地址和发送给用户之间的时间。基本上，以一种舒适的方式处理，每天发送几个邀请可能会很容易，但是如果要发送很多邀请，则会非常麻烦。我想大多数用户会忘记/放弃这样做，如果他们必须在相对长的时间内这样做才能获得免费赠品。

- Francisco Noriega

Answer 9

你有没有办法检查创建电子邮件的人的IP地址。这将是一种简单的方法来确定或者至少为您提供关于不同电子邮件地址是否来自同一人的附加信息。

- Andrew Campion