17

我有一个大约 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

4

9 回答 9

10

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

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

例如，您可以存储所有具有相似长度（+/- 一定数量）的电子邮件并首先比较该子集。您还可以从电子邮件中删除所有特殊字符（数字、符号），并找到那些在减少后相同的字符。

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

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

于 2010-05-11T16:08:53.040 回答
6

好吧，假设 Levenshtein 差异是您的瓶颈，您可以进行一些优化。

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

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

或者

编写您自己的 Levenshtein 距离算法。如果您只对长度 < k 感兴趣，则可以优化运行时间。请参阅 Wikipedia 页面上的“可能的改进”：http ://en.wikipedia.org/wiki/Levenshtein_distance 。

于 2010-05-11T16:24:17.237 回答
2

您可以添加一些优化：

1) 保留已知欺诈的清单并首先进行比较。在你开始你的算法之后，你可能会比你击中主列表更快地击中这个列表。

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

3) 一般考虑剥离域。spammer3@gmail.com 和 spammer3@hotmail.com 永远不会触发您的标记。

于 2010-05-11T16:15:39.620 回答
1

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

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

于 2010-05-11T16:19:34.463 回答
1

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

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

  2. 如果用户明智的话，子地址可能会触发您的过滤器。您希望在比较之前删除子地址数据。

于 2010-05-11T16:33:52.867 回答
0

您可能想查看完整的数据集，以了解在具有欺骗性电子邮件的帐户之间是否存在其他共性。

我不知道您的应用程序是做什么的，但如果还有其他关键点，请使用它们来过滤您要比较的地址。

于 2010-05-11T17:37:20.510 回答
0

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

然后检查所有 gmail.com 的相互对照。那应该快得多。不要比较长度不同超过 3 个字符的内容。

作为第二步，将所有键相互检查，并在那里进行分组。（例如，gmail.com == googlemail.com。）

于 2010-05-11T17:42:33.350 回答
0

我同意其他关于比较电子邮件地址没有帮助的评论，因为用户也可以创建欺诈性的不同外观地址。

我认为最好使用其他解决方案，例如限制您每小时/每天可以写下的电子邮件数量，或者限制您收到这些地址与发送给用户之间的时间。基本上，以一种每天发送一些邀请很舒服的方式来解决它，但是一个 PITA 可以发送很多。我想大多数用户会忘记/放弃这样做，如果他们不得不在相对较长的时间内完成它以获得他们的免费赠品。

于 2010-05-11T17:50:17.863 回答
0

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

于 2010-06-09T15:13:27.813 回答