У меня есть список примерно из 20 000 адресов электронной почты, некоторые из которых, как я знаю, являются мошенническими попытками обойти ограничение «1 на адрес электронной почты», например, [email protected], [email protected], username1b@gmail. com и т. д. Я хочу найти похожие адреса электронной почты для оценки. В настоящее время я использую алгоритм Левенштейна, чтобы сверять каждое электронное письмо с другими в списке и сообщать о любом с расстоянием редактирования менее 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);
}
}
}
Редактировать: кое-что из того, что я пытаюсь уловить, выглядит так:
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
01234@ gmail.com
[email protected]
[email protected]
O(n), а неO(n^2). - person Travis Gockel schedule 11.05.2010