Der beste Weg, ähnliche E-Mail-Adressen zu erkennen?

Question

Ich habe eine Liste von ~ 20.000 E-Mail-Adressen, wissen von denen ich einige betrügerische Versuche zu sein, eine „1 per E-Mail“ zu bekommen um zu begrenzen, wie username1@gmail.com, username1a@gmail.com, username1b @ gmail.com, usw. ich möchte ähnliche E-Mail-Adressen für die Auswertung zu finden. Ich bin ein Levenshtein-Algorithmus jede E-Mail gegenüber den anderen in der Liste zur Zeit und jede mit einem Bearbeitungs Abstand von weniger als 2 Allerdings berichten zu überprüfen, ist dies mühsam langsam. Gibt es einen effizienteren Ansatz?

Der Testcode ich benutze jetzt ist:

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);
        }
    }
}

Edit: Einige der Sachen zu fangen sieht aus wie ich versuche:

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

Sie durch die Anwendung einiger Priorisierung, auf die beginnen könnte E-Mails miteinander zu vergleichen.

Ein wesentlicher Grund für die Leistungsbeschränkungen ist die O (n ² ) Leistung jede Adresse zu jeder anderen E-Mail-Adresse zu vergleichen. Die Priorisierung ist der Schlüssel Leistung dieser Art von Suchalgorithmus zu verbessern.

Zum Beispiel könnten Sie alle E-Mails Eimer, die eine ähnliche Länge haben (+/- gewisse Menge) und vergleichen Sie zuerst, dass die Teilmenge. Sie könnten auch sämtliche Charaters Streifen (Zahlen, Symbole) von E-Mail und solche, die gleich nach dieser Reduktion finden.

Sie können auch eher einen Trie aus den Daten zu erstellen, als es die Verarbeitung Zeile für Zeile, und die Nutzung, dass alle E-Mails zu finden, die einen gemeinsamen Satz von Suffixen / Präfixen teilen und fahren Sie Ihre Vergleichslogik von dieser Reduktion. Aus den Beispielen Sie zur Verfügung gestellt, es sieht aus wie Sie Adressen suchen, in dem ein Teil einer Adresse als Teil innerhalb eines anderen erscheinen könnte. Tries (und Suffix Bäume ) ist eine effiziente Datenstruktur für diese Art von Suche durchgeführt wird.

Eine andere Möglichkeit, diesen Algorithmus zu optimieren, wäre das Datum zu verwenden, wenn das E-Mail-Konto erstellt wird (vorausgesetzt, Sie wissen es). Wenn doppelte E-Mails erstellt werden, würden sie wahrscheinlich innerhalb kurzer Zeit voneinander erstellt werden. - dies kann Ihnen helfen, die Anzahl der Vergleiche reduzieren auszuführen, wenn Sie nach Duplikaten suchen

Answer 2

Nun können Sie einige Optimierungen machen, unter der Annahme, dass die Levenshtein Differenz Ihr Engpass ist.

1) Mit einem Levenshtein Abstand von 2, werden die E-Mails innerhalb von 2 Zeichen Länge voneinander sein, also nicht der Mühe, die Entfernungsberechnungen, es sei denn abs(length(email1)-length(email2)) <= 2

zu tun

2) wieder mit einem Abstand von 2, es ist nicht mehr als 2 Zeichen, anders sein, so dass Sie HashSets die Charaktere in den E-Mail, und nehmen Sie die Länge der Vereinigung minus die Länge der Kreuzung machen der beiden. (Ich glaube, dass dies ein SymmetricExceptWith ist) Wenn das Ergebnis> 2, um zum nächsten Vergleich überspringen.

oder

Code Verwenden Sie Ihre eigenen Levenshtein-Distanz-Algorithmus. Wenn Sie nur in Längen http://en.wikipedia.org/wiki/Levenshtein_distance .

Answer 3

Sie können einige Optimierungen hinzufügen:

1) eine Liste der bekannten Betrügereien halten und vergleichen zu diesem ersten. Nachdem Sie in Ihrem Algorithmus loslegen, können Sie möglicherweise Hit gegen diese Liste schneller als Sie die Haupttrefferliste.

2) zuerst die Liste sortieren. Es wird nicht zu lange dauern (im Vergleich) und wird zunächst die Möglichkeit der Anpassung der Vorderseite der Saite zu erhöhen. Haben sie sortieren nach Domain-Namen zuerst, dann nach Benutzernamen ein. Vielleicht jede Domain in seinem eigenen Eimer gelegt, dann sortieren und auch vergleichen gegen diese Domäne.

3) Betrachten Sie die Domäne im Allgemeinen Strippen. spammer3@gmail.com und spammer3@hotmail.com nie Ihre Flagge auslösen.

Answer 4

Wenn Sie eine geeignete Zuordnung zu einem gewissen k-dimensionalen Raum definieren, und eine geeignete Norm auf diesen Raum, reduziert dies auf den Alle Nearest Neighbors Problem , die in O gelöst werden kann (n log n) Zeit.

Eine solche Abbildung zu finden, könnte jedoch schwierig sein. Vielleicht nehmen Sie jemand diese Teilantwort und laufen mit ihm.

Answer 5

Nur der Vollständigkeit halber, sollten Sie die Semantik von E-Mail-Adressen betrachten als auch in Bezug auf:

1. Google Mail behandelt user.name und username als die gleiche ist, so dass beide gültige E-Mail-Adressen, die zu dem gleichen Benutzer sind. Andere Dienste können auch tun. LBushkin 'Vorschlag von Sonderzeichen strippen würde helfen hier.

2. Sub-adrressing können möglicherweise Ihre Filter auslösen wenn Benutzer weist bis zu ihm. Sie würden wollen, bevor ein Vergleich der Unteradressdaten löschen.

Answer 6

Sie können an dem vollständigen Datensatz suchen mögen, um zu sehen, ob es andere Gemeinsamkeit zwischen Konten, die E-Mails gefälscht hat.

ich weiß nicht, was Ihre Anwendung tut, aber wenn es andere wichtige Punkte sind, dann diejenigen verwenden, um Filter auf, was Adressen, die Sie gehen zu vergleichen.

Answer 7

Sortieren alles in eine Hash-Tabelle zuerst. Der Schlüssel sollte der Domain-Name der E-Mail; "Gmail.com". Streifen aus Sonderzeichen aus den Werten wurde, wie oben erwähnt.

Dann schauen Sie sich alle die gmail.com die gegeneinander. Das sollte viel schneller. Vergleichen Sie nicht Dinge, die mehr als 3 Zeichen unterschiedlich lang sind.

Als zweiter Schritt, überprüfen Sie alle die Schlüssel gegeneinander, und es Gruppierungen entwickeln. (Gmail.com == googlemail.com, zum Beispiel.)

Answer 8

Ich stimme mit anderen Kommentaren über E-Mail-Adressen zu vergleichen nicht hilfreich sein, da die Nutzer könnten nur als gut betrügerische disimilar suchen Adressen erstellen.

Ich denke, eine bessere mit anderen Lösungen zu kommen, wie die Menge an E-Mails zu begrenzen Sie pro Stunde / Tag aufschreiben kann, oder die Zeit zwischen diesen Adressen von Ihnen empfangen werden und an die Nutzer gesendet werden. Grundsätzlich arbeiten sie in einer Weise, wo es bequem ist zu senden ein paar lädt pro Tag zu senden, aber ein PITA viele auszusenden. Ich denke, die meisten Benutzer vergessen / aufgeben, es zu tun, wenn sie es tun mußten, durch aus einem relativ langen Zeitraum, um ihre Werbegeschenke zu erhalten.

Answer 9

Gibt es eine Möglichkeit Sie eine Überprüfung der IP-Adresse der Person, die E-Mail zu schaffen machen kann. Das wäre ein einfacher Weg sein, um zu bestimmen, oder zumindest gibt Sie Auskunft darüber, ob die verschiedenen E-Mail-Adressen von der gleichen Person sind gekommen, hinzugefügt.