代码之家 › 专栏 › 技术社区 › Chris

检测类似电子邮件地址的最佳方法?

levenshtein-distance c#

Chris · 技术社区 · 15 年前

我有大约20000个电子邮件地址的列表,其中一些我知道是欺诈性的尝试,以达到“每封电子邮件1个”的限制,例如username1@gmail.com、username1 a@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
0123@ Gmail
012@ Gmail

9 回复 | 直到 15 年前

LBushkin 15 年前

您可以先应用一些优先顺序来比较电子邮件。

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

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

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

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

Jeff B 15 年前

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

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

2)同样,如果距离为2,则不会有超过2个字符不同,因此您可以对电子邮件中的字符进行哈希集,并取联合的长度减去两个字符相交的长度。(我认为这是对称例外)如果结果为>2,请跳到下一个比较。

或

编写自己的Levenshtein距离算法。如果您只对长度感兴趣,可以优化运行时间。参见维基百科页面上的“可能的改进: http://en.wikipedia.org/wiki/Levenshtein_distance .

corsiKa 15 年前

您可以添加一些优化:

1)保留一份已知欺诈的清单,并与之进行比较。在你开始使用你的算法之后,你可能会比点击主列表更快地点击这个列表。

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

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

Thomas 15 年前

如果你能定义一个合适的映射到某个K维空间,并且在这个空间上定义一个合适的范数,这就减少到 All Nearest Neighbours Problem 它可以在O(n log n)时间内解决。

然而,找到这样的地图可能是困难的。也许有人会接受这个部分答案,然后用它来运行。

Community CDub 8 年前

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

Gmail处理 user.name 和 username 因为是相同的,所以两者都是属于同一用户的有效电子邮件地址。其他服务也可以做到这一点。 LBushkin 建议去掉特殊字符会有帮助。
Sub-adrressing 如果用户知道的话,可能会绊倒您的过滤器。在比较之前,您需要删除子地址数据。

ChrisLively 15 年前

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

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

Dean J 15 年前

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

然后检查所有的gmail.com。那应该是 许多的 更快。不要比较长度超过3个字符的内容。

作为第二步,检查所有键,并在那里开发分组。(例如,gmail.com==googlemail.com。)

Francisco Noriega 15 年前

我同意其他人关于比较电子邮件地址没有帮助的意见,因为用户也可以创建具有欺骗性的恶意地址。

我认为最好使用其他解决方案,例如限制您每小时/天可以写下的电子邮件数量,或者限制您收到这些地址与发送给用户之间的时间间隔。基本上,以一种每天发送几封邀请信比较舒服的方式进行计算,但是发送很多邀请信需要一个pita。我想大多数用户会忘记/放弃去做它,如果他们不得不做一个相对较长的时间,以获得他们的免费赠品。

Andrew Campion 15 年前

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