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

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而不是逐行处理它,并使用它来查找共享一组通用后缀/前缀的所有电子邮件,并从该减少中驱动您的比较逻辑.从您提供的示例中,您看起来正在寻找一个地址的一部分可能在另一个地址中显示为子字符串的地址.尝试(和后缀树)是用于执行这些类型的搜索的有效数据结构.

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

Answer 2

假设Levenshtein差异是你的瓶颈,你可以做一些优化.

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

2)同样,距离为2时,不会有超过2个字符的不同,因此您可以在电子邮件中创建字符的HashSets,并使用union的长度减去两者的交集长度.(我相信这是一个SymmetricExceptWith)如果结果> 2,跳到下一个比较.

要么

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