Лучший способ обнаружения похожих адресов электронной почты?

У меня есть список из ~ 20 000 адресов электронной почты, некоторые из которых я знаю как мошеннические попытки обойти ограничение "1 на электронную почту", например [email protected], [email protected], 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);
        }
    }
}

Изменить: Некоторые вещи, которые я пытаюсь уловить, выглядят следующим образом:

[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]

Ответы

Ответ 1

Вы можете начать с применения некоторой приоритизации, по которой электронные письма сравниваются друг с другом.

Ключевой причиной ограничений производительности является производительность O (n 2) для сравнения каждого адреса с любым другим адресом электронной почты. Приоритизация - это ключ к повышению производительности такого алгоритма поиска.

Например, вы можете загружать все электронные письма с одинаковой длиной (+/- некоторое количество) и сначала сравнивать это подмножество. Вы также можете удалить все специальные символы (цифры, символы) из электронных писем и найти те, которые идентичны после этого сокращения.

Вы также можете создать trie из данных, а не обрабатывать его по строкам, и использовать это, чтобы найти все электронные письма, которые совместно используют общий набор суффиксов/префиксов и приводят вашу логику сравнения из этого сокращения. Из приведенных вами примеров выглядит, что вы ищете адреса, где часть одного адреса может отображаться как подстрока в другом. Tries (и деревья суффикса) - эффективные данные структура для выполнения этих типов поиска.

Другим возможным способом оптимизации этого алгоритма будет использование даты создания учетной записи электронной почты (при условии, что вы ее знаете). Если будут созданы повторяющиеся электронные письма, они, скорее всего, будут созданы в течение короткого периода времени друг от друга - это может помочь вам уменьшить количество сравнений, выполняемых при поиске дубликатов.

Ответ 2

Хорошо, вы можете сделать некоторые оптимизации, считая, что разница Левенштейна - это ваше узкое место.

1) Если расстояние Левенштейна равняется 2, электронные письма будут находиться в пределах двух символов друг от друга, поэтому не делайте расчет расстояний, если abs(length(email1)-length(email2)) <= 2

2) Опять же, с расстоянием 2, не должно быть больше двух символов, поэтому вы можете сделать HashSets символов в письмах и взять длину объединения за вычетом длины пересечения из двух. (Я считаю, что это SymmetricExceptWith) Если результат > 2, перейдите к следующему сравнению.

ИЛИ

Составьте свой собственный алгоритм расстояния Левенштейна. Если вас интересуют только длины < k, вы можете оптимизировать время выполнения. См. "Возможные улучшения" на странице Википедии: http://en.wikipedia.org/wiki/Levenshtein_distance.

Ответ 3

Вы можете добавить несколько оптимизаций:

1) Сохраните список известных мошенников и сравните их с первым. После того, как вы пойдете в своем алгоритме, вы можете столкнуться с этим списком быстрее, чем попасть в основной список.

2) Сначала отсортируйте список. Это не займет слишком много времени (в сравнении) и увеличит вероятность совпадения фронта первой строки. Сначала выполните сортировку по имени домена, затем по имени пользователя. Возможно, поместите каждый домен в свое собственное ведро, затем отсортируйте и сравните с этим доменом.

3) Рассмотрим разделение области вообще. [email protected] и [email protected] никогда не будут запускать ваш флаг.

Ответ 4

Если вы можете определить подходящее отображение для некоторого k-мерного пространства и подходящую норму в этом пространстве, это сводится к Все проблемы ближайших соседей, которая может быть решена в O (n log n) времени.

Однако найти такое отображение может быть сложно. Возможно, кто-то возьмет этот частичный ответ и начнет с него.

Ответ 5

Просто для полноты вам следует рассмотреть семантику адресов электронной почты, а именно:

  • Gmail рассматривает user.name и username как одно и то же, поэтому оба являются действительными адресами электронной почты, принадлежащими одному и тому же пользователю. Другие службы могут это сделать. Предложение Л.Бушкина для выделения специальных символов поможет здесь.

  • Sub-adrressing может потенциально отключить ваш фильтр, если пользователи подойдут к нему. Вы хотите удалить данные суб-адреса перед сравнением.

Ответ 6

Вы можете посмотреть полный набор данных, чтобы узнать, существует ли другая общность между учетными записями, которые имеют поддельные письма.

Я не знаю, что делает ваше приложение, но если есть другие ключевые моменты, используйте их, чтобы отфильтровать, какие адреса вы собираетесь сравнивать.

Ответ 7

Сначала сортируйте все в хэш-таблицу. Ключ должен быть доменным именем электронной почты; "Gmail.com". Выделите специальные символы из значений, как было упомянуто выше.

Затем проверьте все gmail.com друг на друге. Это должно быть намного быстрее. Не сравнивайте вещи, длина которых превышает 3 символа.

В качестве второго шага проверьте все ключи друг против друга и создайте там группы. (например, gmail.com == googlemail.com.)

Ответ 8

Я согласен с другими комментариями о сравнении адресов электронной почты, которые не могут быть полезными, поскольку пользователи могут просто создавать мошеннические разного рода адреса.

Я думаю, что лучше приходить с другими решениями, такими как ограничение количества писем, которые вы можете записать в час/день, или время между этими адресами, полученными вами и отправляемыми пользователям. В основном, работайте так, чтобы было удобно отправлять несколько приглашений в день, но PITA посылать много. Я предполагаю, что большинство пользователей забудут/отступят, чтобы сделать это, если им нужно было сделать это через относительно длительный период времени, чтобы получить их бесплатную рекламу.

Ответ 9

Можно ли проверить IP-адрес человека, создавшего письмо. Это был бы простой способ определить или, по крайней мере, дать вам дополнительную информацию о том, пришли ли разные адреса электронной почты от одного и того же человека.