如何使用反向查找树进行快速一次性电子邮件域检测-js教程-PHP中文网

如何使用反向查找树进行快速一次性电子邮件域检测

DDD

发布： 2024-12-14 03:42:09

原创

591 人浏览过

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

了解如何使用反向 Trie 有效检测一次性电子邮件域。使用专为快速、精确的结果而定制的可扩展、内存高效的解决方案来优化您的域名查找。

阅读我网站上的文章
使用免费的一次性电子邮件域名检测器

一次性电子邮件可能会导致虚假注册和垃圾邮件等问题。用户从数千个临时电子邮件生成器之一中获取一个地址并将其交给。即使是电子邮件正则表达式的 GOAT 也无法拯救您。

就我个人而言，我发现拥有所有一次性电子邮件域的大列表是最简单但最有效的解决方案。但在组装该列表并启动 for ... of 循环来检查它之前，请考虑一下 O(n) 复杂度！

识别它们的一个好方法是使用反向 Trie，这是一种用于快速查找的高效数据结构。

什么是反向特里树？

首先，我们来了解一下什么是 Trie。它是一种数据结构，其中字符串为：

切碎，逐个字符
组装成树形结构

例如，如果我们喂蟒蛇、兄弟、布里干酪，它会使用 Map 将它们组装为：

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

登录后复制

这种方法允许直接查找，而无需循环遍历整个列表。每个角色都引导着更深入的搜索。

它以内存换取效率。查找字符串所花费的时间并不取决于列表的大小，而是取决于字符串的长度！

反向 Trie 以相反的顺序存储字符串，非常适合域：

mailinator.com 变为 moc.rotanliam
垃圾邮件.com 变为 moc.liambhsart

关于此实施的注意事项

通过反转域名，搜索从 TLD（例如 .com）开始，该域名在许多域名之间共享。为了进一步优化，它将 TLD 存储为单个键 (com)，而不是将其拆分为字符。域的其余部分遵循标准的 Trie 结构。

反向 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 这样的子域得到正确处理。

接下来，构造函数将组装 Trie：

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

登录后复制

要检查域是否是一次性的，请遍历 Trie：

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

登录后复制