Лучший способ обнаружить подобные адреса электронной почты?
У меня есть список ~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
9 ответов
Вы можете начать с определения приоритетов при сравнении писем друг с другом.
Ключевой причиной ограничения производительности является O(n2) производительность сравнения каждого адреса с каждым другим адресом электронной почты. Расстановка приоритетов - ключ к повышению производительности такого алгоритма поиска.
Например, вы можете отбирать все электронные письма, имеющие одинаковую длину (+/- некоторое количество), и сравнивать это подмножество первым. Можно также удалить из писем все специальные символы (цифры, символы) и найти те, которые идентичны после такого сокращения.
Возможно, вы также захотите создать тройку из данных, а не обрабатывать их построчно, и использовать ее для поиска всех писем, имеющих общий набор суффиксов/префиксов, и управлять логикой сравнения на основе этого сокращения. Судя по приведенным вами примерам, похоже, что вы ищете адреса, в которых часть одного адреса может оказаться подстрокой в другом. Tries (и суффиксные деревья) являются эффективной структурой данных для выполнения таких типов поиска.
Другим возможным способом оптимизации этого алгоритма было бы использование даты создания учетной записи электронной почты (при условии, что она вам известна). Если будут созданы дубликаты электронных писем, они, скорее всего, будут созданы в течение короткого промежутка времени друг от друга - это может помочь вам сократить количество сравнений при поиске дубликатов.
Вы можете добавить несколько оптимизаций:
1) Сохраните список известных случаев мошенничества и сравните его в первую очередь. После того, как вы начнете работать со своим алгоритмом, вы сможете попасть в этот список быстрее, чем по основному списку.
2) Сначала отсортируйте список. Это не займет слишком много времени (в сравнении) и увеличит вероятность совпадения первой строки строки. Сначала отсортируйте его по доменному имени, а затем по имени пользователя. Возможно, поместите каждый домен в отдельную корзину, затем отсортируйте и сравните с этим доменом.
3) Рассмотрите возможность удаления области в целом. (скрытый) и (скрытый) никогда не активируют ваш флаг.
Если вы можете определить подходящее отображение в некоторое k-мерное пространство и подходящую норму в этом пространстве, это сведется к Задаче всех ближайших соседей , которую можно решить за O (n log n) время.
Однако найти такое отображение может быть сложно. Может быть, кто-то возьмет этот частичный ответ и побежит с ним.
Для полноты картины следует также рассмотреть семантику адресов электронной почты в следующих терминах:
Gmail рассматривает
user.nameиusernameкак одно и то же, поэтому оба являются действительными адресами электронной почты, принадлежащими одному и тому же пользователю. Другие службы также могут делать это. Здесь поможет предложение LBushkin об удалении специальных символов.Sub-adrressing может потенциально сбить ваш фильтр, если пользователи догадаются об этом. Вы захотите отбросить данные субадреса перед сравнением.
Возможно, вы захотите просмотреть полный набор данных, чтобы узнать, есть ли другие общие черты между аккаунтами, в которых есть поддельные электронные письма.
Я не знаю, что делает ваше приложение, но если есть другие ключевые моменты, используйте их, чтобы отфильтровать адреса, которые вы собираетесь сравнивать.
Сначала отсортируйте все в хеш-таблицу. Ключ должен быть доменным именем электронной почты; "gmail.com". Удалите специальные символы из значений, как упоминалось выше.
Затем сравните все gmail.com друг с другом. Это должно быть намного быстрее. Не сравнивайте объекты, длина которых различается более чем на 3 символа.
В качестве второго шага сравните все ключи друг с другом и создайте там группы. (например, gmail.com == googlemail.com.)
Ну, вы можете сделать некоторые оптимизации, предполагая, что разница Левенштейна является вашим узким местом.
1) При расстоянии по Левенштейну, равном 2, электронные письма будут находиться в пределах 2 символов друг от друга, так что не утруждайте себя вычислениями расстояния, если abs(length(email1)-length(email2)) <= 2
2) Опять же, при расстоянии в 2, не будет больше 2 символов, так что вы можете сделать HashSets из символов в электронных письмах, и взять длину объединения минус длину пересечения двух. (Если результат > 2, переходим к следующему сравнению.
ИЛИ
Напишите свой собственный алгоритм расстояния Левенштейна. Если вас интересуют только длины < k, вы можете оптимизировать время работы. См. раздел "Возможные улучшения" на странице Википедии: http://en.wikipedia.org/wiki/Levenshtein_distance.
Я согласен с другими комментариями о том, что сравнение адресов электронной почты не слишком полезно, так как пользователи могут просто создать поддельные непохожие адреса.
Я думаю, что лучше придумать другие решения, например, ограничить количество писем, которые вы можете записать в час/день, или время между получением этих адресов вами и отправкой пользователям. В общем, сделать так, чтобы было удобно отправлять несколько приглашений в день, но хлопотно рассылать много. Я думаю, что большинство пользователей забудут/откажутся это делать, если им придется делать это в течение относительно длительного периода времени, чтобы получить свои бесплатные призы.
Можно ли как-то проверить IP-адрес человека, создающего письмо. Это был бы простой способ определить или, по крайней мере, дать дополнительную информацию о том, исходят ли разные адреса электронной почты от одного и того же человека.