17

約20,000通のメールアドレスのリストがあります。そのうちのいくつかは、username1 @ gmail.com、username1a @ gmail.com、username1b @ gmailなど、「メールごとに1つ」の制限を回避しようとする不正な試みであることがわかっています。 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

4

9 に答える 9

10

相互に比較する電子メールに何らかの優先順位を適用することから始めることができます。

パフォーマンスが制限される主な理由は、各アドレスを他のすべての電子メール アドレスと比較する際の O(n 2 ) パフォーマンスです。優先順位付けは、この種の検索アルゴリズムのパフォーマンスを改善するための鍵です。

たとえば、同様の長さ (+/- ある程度) を持つすべての電子メールをバケット化し、そのサブセットを最初に比較することができます。また、すべての特殊文字 (数字、記号) を電子メールから削除し、削減後に同一のものを見つけることもできます。

データを行ごとに処理するのではなく、データからトライを作成し、それを使用して共通のサフィックス/プレフィックスのセットを共有するすべての電子メールを検索し、その削減から比較ロジックを駆動することもできます。あなたが提供した例から、あるアドレスの一部が別のアドレスの部分文字列として現れる可能性のあるアドレスを探しているようです。トライ(および接尾辞ツリー) は、これらのタイプの検索を実行するための効率的なデータ構造です。

このアルゴリズムを最適化するもう 1 つの方法は、メール アカウントが作成された日付を使用することです (わかっている場合)。重複した電子メールが作成された場合、それらは互いに短期間で作成される可能性があります。これは、重複を探すときに実行する比較の数を減らすのに役立つ場合があります。

于 2010-05-11T16:08:53.040 に答える
6

レーベンシュタインの違いがボトルネックであると仮定して、いくつかの最適化を行うことができます。

1）レーベンシュタイン距離が2の場合、電子メールは互いに2文字以内の長さになります。したがって、abs(length(email1)-length(email2))<= 2でない限り、わざわざ距離を計算しないでください。

2）繰り返しになりますが、距離が2の場合、2文字を超える違いはないため、電子メール内の文字のハッシュセットを作成し、和集合の長さから2つの交差の長さを引いた長さを取ることができます。 。（これはSymmetricExceptWithだと思います）結果が2より大きい場合は、次の比較にスキップします。

また

独自のレーベンシュタイン距離アルゴリズムをコーディングします。長さ<kのみに関心がある場合は、実行時間を最適化できます。Wikipediaページの「可能な改善」を参照してください：http：//en.wikipedia.org/wiki/Levenshtein_distance。

于 2010-05-11T16:24:17.237 に答える
2

いくつかの最適化を追加できます。

1) 既知の詐欺のリストを保持し、最初にそれと比較します。アルゴリズムを開始した後、メイン リストにヒットするよりも速く、このリストにヒットできる可能性があります。

2) 最初にリストを並べ替えます。(比較して) それほど時間はかからず、文字列の前部を最初に一致させる可能性が高くなります。最初にドメイン名で並べ替え、次にユーザー名で並べ替えます。おそらく、各ドメインを独自のバケットに入れ、ソートしてそのドメインと比較します。

3) 一般的にドメインを削除することを検討してください。spammer3@gmail.com と spammer3@hotmail.com がフラグをトリガーすることはありません。

于 2010-05-11T16:15:39.620 に答える
1

完全を期すために、次の観点から、電子メール アドレスのセマンティクスも考慮する必要があります。

  1. Gmail はuser.nameとusernameを同じものとして扱うため、どちらも同じユーザーに属する有効なメール アドレスです。他のサービスもこれを行う場合があります。ここでは、特殊文字を削除するというLBushkinの提案が役立ちます。

  2. サブアドレシングは、ユーザーが賢明であれば、フィルターを作動させる可能性があります。比較の前にサブアドレス データを削除する必要があります。

于 2010-05-11T16:33:52.867 に答える
1

ある k 次元空間への適切なマッピングとその空間での適切なノルムを定義できる場合、これは O(n log n) 時間で解決できるすべての最近傍問題になります。

ただし、そのようなマッピングを見つけるのは難しい場合があります。多分誰かがこの部分的な答えを取り、それを実行するでしょう。

于 2010-05-11T16:19:34.463 に答える
0

電子メールをスプーフィングしたアカウント間に他の共通点があるかどうかを確認するために、完全なデータセットを確認することをお勧めします。

アプリケーションが何をするのかわかりませんが、他に重要なポイントがある場合は、それらを使用して、比較するアドレスを絞り込みます。

于 2010-05-11T17:37:20.510 に答える
0

最初にすべてをハッシュテーブルに並べ替えます。キーは電子メールのドメイン名にする必要があります。「gmail.com」。上記のように、値から特殊文字を取り除きます。

次に、すべての gmail.com を相互にチェックします。それははるかに速いはずです。長さが 3 文字以上異なるものを比較しないでください。

2 番目のステップとして、すべてのキーを相互にチェックし、そこでグループ化を作成します。(gmail.com == googlemail.com など)。

于 2010-05-11T17:42:33.350 に答える
0

メールアドレスの比較は役に立たないという他のコメントに同意します.

1 時間/1 日あたりに書き留めることができるメールの量を制限したり、それらのアドレスが受信されてからユーザーに送信されるまでの時間を制限したりするなど、他の解決策を講じたほうがよいと思います。基本的に、1 日に数通の招待状を送信するのは快適ですが、多数送信するのは PITA になるように考えてください。景品を得るために比較的長い期間それをしなければならなかった場合、ほとんどのユーザーはそれを忘れたりあきらめたりすると思います.

于 2010-05-11T17:50:17.863 に答える
0

メールの作成者の IP アドレスを確認する方法はありますか。これは、別の電子メール アドレスが同じ人物からのものかどうかを判断する、または少なくとも追加情報を提供する簡単な方法です。

于 2010-06-09T15:13:27.813 に答える