リバーストライを使用して使い捨て電子メールドメインを高速に検出する方法-jsチュートリアル-php.cn

リバーストライを使用して使い捨て電子メールドメインを高速に検出する方法

DDD

リリース： 2024-12-14 03:42:09

オリジナル

591 人が閲覧しました

How to Use a Reverse Trie for Fast Disposable Email Domain Detection

逆トライを使用して使い捨て電子メールドメインを効率的に検出する方法を学びます。高速で正確な結果を得るために調整された、スケーラブルでメモリ効率の高いソリューションを使用してドメイン検索を最適化します。

私のウェブサイトで記事を読む
無料の使い捨て電子メールドメイン検出ツールを使用する

使い捨てメールは、偽のサインアップやスパムなどの問題を引き起こす可能性があります。ユーザーは、何千もの一時的な電子メールジェネレーターの 1 つからアドレスを取得し、それを渡します。電子メール正規表現の GOAT でも、ここからは救われません。

個人的には、すべての使い捨て電子メールドメインの大きなリストを作成することが、最も簡単で効果的な解決策だと思います。ただし、そのリストを組み立てて for ... of ループを開始してそれをチェックする前に、O(n) の複雑さについて考えてください!

それらを識別する優れた方法は、高速検索のための効率的なデータ構造である逆トライを使用することです。

リバーストライとは何ですか?

まず、トライとは何かを理解しましょう。これは、文字列が次のようなデータ構造です:

みじん切り、チャーごと
ツリー構造で組み立てられています

例として、ボア、ブロ、ブリーに餌を与える場合、Map を使用して次のように組み立てられます。

b
 ├── o ── a
 └── r ── o  
     └─── i ── e

ログイン後にコピー

このアプローチにより、リスト全体を循環することなく直接検索が可能になります。それぞれのキャラクターが探索をさらに深く導きます。

効率性のためにメモリを犠牲にします。文字列の検索にかかる時間は、リストのサイズではなく、文字列の長さに依存します!

リバーストライは、文字列を逆の順序で保存します。これはドメインに最適です。

mailinator.com が moc.rotanliam になります
trashmail.com が moc.liambhsart になります

この実装に関する注意事項

ドメインを反転すると、多くのドメイン間で共有される TLD (例: .com) から検索が開始されます。さらに最適化するために、TLD を文字に分割するのではなく、単一のキー (com) として保存します。ドメインの残りの部分は、標準の Trie 構造に従います。

リバーストライドメインの実装

これはツリー構造であるため、各ノードはその子を参照します。

type TrieNode = Map<string, TrieNode>;

ログイン後にコピー

まず、ドメインの残りの部分から TLD を分割するユーティリティ関数:

private splitTLDFromRest(input: string) {
    const dot = input.lastIndexOf('.');
    const TLD = input.substring(dot + 1);
    const rest = input.substring(0, dot);
    return [TLD, rest];
}

ログイン後にコピー

lastIndexOf を使用すると、foo.bar.baz.com などのサブドメインが正しく処理されます。

次に、コンストラクターはトライをアセンブルします。

export class ReverseTrieDomains {
    private root: TrieNode = new Map();

    // ...

    constructor(...domains: string[]) {
        for (const domain of domains) {
            // For "didof.dev"
            const [TLD, rest] = this.splitTLDFromRest(domain);
            // dev, didof

            // Keep the refence to the TLD node for final set
            let node = this.root.get(TLD);
            if (!node) node = new Map();

            // Start from TLD node, walk along the string in reverse
            let currentNode: TrieNode = node;
            for (let i = rest.length - 1; i >= 0; i--) {
                const char = rest[i];
                let childNode = currentNode.get(char);
                if (!childNode) {
                    childNode = new Map();
                    currentNode.set(char, childNode);
                }
                currentNode = childNode;
            }

            this.root.set(TLD, node);
        }
    }
}

ログイン後にコピー

ドメインが使い捨てかどうかを確認するには、トライを走査します。

export class ReverseTrieDomains {
    // ...

    public has(domain: string) {
        const [TLD, rest] = this.splitTLDFromRest(domain)

        const node = this.root.get(TLD)
        if (!node) return false

        let currentNode: TrieNode = node
        let isFullDomainFound = false
        for (let i = rest.length - 1; i >= 0; i--) {
            const char = rest[i]
            const childNode = currentNode.get(char)
            if (!childNode) return false
            currentNode = childNode
            if (i === 0) {
                isFullDomainFound = currentNode.size === 0;
            }
        }

        return isFullDomainFound
    }
}

ログイン後にコピー