Come Usare un Reverse Trie per il Rilevamento Rapido di Domini Email Usa e Getta

Scritto da Francesco Di Donato • 5 dicembre 2022 • 3 minuti di lettura

Le email usa e getta possono causare problemi come iscrizioni false e spam. L’utente prende un indirizzo da uno dei migliaia di generatori di email temporanee e lo fornisce. Nemmeno la regex per email GOAT 🔗 può salvarti qui.

Personalmente, trovo che avere una grande lista di tutti i domini email usa e getta sia la soluzione più semplice ma anche la più efficace. Ma prima di creare quella lista e iniziare un ciclo for…of per controllarla, pensa alla complessità O(n)!

Un ottimo modo per identificarli è usare un reverse Trie, una struttura dati efficiente per ricerche veloci.

Cos’è un Reverse Trie?

Innanzitutto, capiamo cos’è un Trie. È una struttura dati in cui le stringhe sono:

spezzettate, carattere per carattere
assemblate in una struttura ad albero

Ad esempio, se inseriamo boa, bro, brie, li assemblerebbe usando una Mappa come:

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

Questo approccio consente ricerche dirette senza scorrere l’intera lista. Ogni carattere guida la ricerca più in profondità.

Scambia la memoria con l’efficienza. Il tempo necessario per trovare la stringa non dipende dalla dimensione della lista, ma dalla lunghezza della stringa!

Un reverse Trie memorizza le stringhe in ordine inverso, ideale per i domini:

mailinator.com diventa moc.rotanliam
trashmail.com diventa moc.liambhsart

Nota su Questa Implementazione

Invertendo i domini, le ricerche iniziano dal TLD 🔗 (ad es. .com), che è condiviso da molti domini. Per ottimizzare ulteriormente, memorizza i TLD come una singola chiave (com), invece di dividerli in caratteri. Il resto del dominio segue una struttura Trie standard.

Implementazione del Reverse Trie per i Domini

Poiché si tratta di una struttura ad albero, ogni nodo farà riferimento ai suoi figli:

type TrieNode = Map<string, TrieNode>;

Innanzitutto, una funzione di utilità per dividere il TLD dal resto del dominio:

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

L’uso di lastIndexOf assicura che i sottodomini come foo.bar.baz.com vengano gestiti correttamente.

Successivamente, il costruttore assemblerà il Trie:

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

	// ...

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

			// Mantieni il riferimento al nodo TLD per l'impostazione finale
			let node = this.root.get(TLD);
			if (!node) node = new Map();

			// Inizia dal nodo TLD, percorri la stringa in ordine inverso
			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);
		}
	}
}

Per verificare se un dominio è usa e getta, attraversa il 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)
            console.log(i, char, childNode)
            if (!childNode) return false
            currentNode = childNode
            if (i === 0) {
                isFullDomainFound = currentNode.size === 0;
            }
        }

        return isFullDomainFound
    }
}

Conclusione

L’uso di un reverse Trie offre diversi vantaggi:

Ricerche Veloci: Attraversa i caratteri passo dopo passo per risultati rapidi.
Efficienza della Memoria: I suffissi comuni come .com vengono memorizzati una sola volta.
Scalabilità: Gestisce grandi liste di domini senza sforzo.

Se hai a che fare con email usa e getta, questa è una soluzione intelligente e scalabile da implementare.