Ricerca per prefisso e Starts-With

Il vantaggio distintivo del Trie rispetto a una mappa hash è l'efficienza nelle query sui prefissi. Una query su un prefisso risponde a domande come: «quante parole memorizzate iniziano con questo prefisso?», «quali sono tutte le parole memorizzate con questo prefisso?» o, semplicemente, «esiste una parola con questo prefisso?». Queste query hanno complessità O(p), dove p è la lunghezza del prefisso, indipendentemente dal numero totale di parole memorizzate: per questo i Trie sono ideali per il completamento automatico e i suggerimenti di ricerca.

starts_with(prefix) restituisce True se una qualsiasi parola memorizzata inizia con il prefisso indicato. Si percorra il Trie seguendo ogni carattere del prefisso. Se è possibile seguire tutti i caratteri senza incontrare un arco mancante, il prefisso esiste e almeno una parola lo utilizza. L'implementazione è identica a quella di search, con l'unica differenza che si restituisce True non appena termina il percorso: non si verifica is_end.

Per implementare il completamento automatico, si percorra il Trie fino al nodo finale del prefisso, quindi si esegua una DFS, o una BFS, a partire da quel nodo per raccogliere tutte le parole che si diramano da esso. Si anteponga il prefisso a ogni suffisso raccolto per ricostruire le parole complete. Questa operazione ha complessità O(p + W), dove W è il numero totale di caratteri contenuti in tutte le parole corrispondenti.

Per ottenere un completamento automatico ordinato, si percorrano i figli in ordine alfabetico durante la DFS, iterando su sorted(node.children.items()). Poiché i figli sono memorizzati in un dict, questo aggiunge un overhead di O(ALPHABET_SIZE × depth), ma garantisce risultati ordinati lessicograficamente. Un Trie basato su array percorre sempre i figli in ordine alfabetico, poiché gli indici da 0 a 25 sono ordinati.

Per ottenere i top-k suggerimenti in base alla frequenza, si aggiunga a ogni nodo un conteggio del numero di volte in cui è stata cercata la parola che termina in quel nodo. Durante la raccolta dei suggerimenti, si utilizzi un max-heap di dimensione k. In questo modo si riduce a O(k) il risultato della DFS, che avrebbe dimensione O(W), senza materializzare tutte le corrispondenze. I motori di ricerca reali combinano il percorso dei prefissi nel Trie con i dati sulla frequenza per fornire suggerimenti rapidi e pertinenti.

LeetCode 208, «Implement Trie (Prefix Tree)», richiede esattamente: insert(word), search(word) che restituisce un booleano per la corrispondenza esatta e startsWith(prefix) che restituisce un booleano per la corrispondenza del prefisso. Questa è l'implementazione canonica di un Trie. Si ricordi: search richiede is_end=True; startsWith richiede soltanto che esista il percorso del prefisso.

Una scorciatoia elegante consiste nel memorizzare il Trie come dict annidati, usando una chiave sentinella speciale come '#' per contrassegnare la fine delle parole ed eliminando la necessità di una classe TrieNode. Questa soluzione è compatta e adatta ai colloqui, ma leggermente meno leggibile degli oggetti TrieNode espliciti. Entrambe le implementazioni sono accettabili; la versione con dict è più rapida da scrivere sotto pressione.

Per trovare il prefisso comune più lungo di un elenco di stringhe, si inseriscano tutte le stringhe nel Trie, quindi si percorra la struttura dalla radice seguendo l'unico percorso esistente finché: (1) il nodo corrente ha esattamente un figlio e (2) is_end è False. Ci si fermi quando una delle due condizioni non è più soddisfatta. Il percorso seguito è il prefisso comune più lungo.

Replace Words (LeetCode 648): dato un dizionario di parole radice e una frase, si sostituisca ogni parola della frase con la radice corrispondente più breve presente nel dizionario. Si inseriscano tutte le radici in un Trie. Per ogni parola della frase, si percorra il Trie finché non viene trovata la fine di una radice, quindi si restituisca quella radice come sostituzione. Se nessuna radice corrisponde, si mantenga la parola originale. La complessità è O(total chars), rispetto a O(n × m) dell'approccio esaustivo.

Map Sum (LeetCode 677): inserire coppie chiave-valore e restituire la somma di tutti i valori le cui chiavi hanno un determinato prefisso. Si aggiunga a ogni TrieNode un campo val. Per l'inserimento, si percorra il Trie fino alla fine e si imposti il valore; per le query di somma, si percorra il Trie fino al nodo finale del prefisso e si calcoli con una DFS la somma di tutti i campi val sottostanti. In alternativa, si memorizzi in ogni nodo la somma cumulativa durante l'inserimento, ottenendo query in O(p).

Nei sistemi di completamento automatico in produzione, restituire tutte le parole che iniziano con un prefisso non è pratico quando le corrispondenze sono migliaia. Si utilizza invece un max-heap di dimensione k durante l'attraversamento DFS: si mantengono le k parole con il punteggio più alto tra quelle trovate finora. Si interrompono in anticipo i rami DFS che non possono contenere una parola tra le prime k (potatura tramite un limite superiore del punteggio). In questo modo si ottiene O(p + k × log k) per query per k suggerimenti, un risultato molto migliore rispetto a raccogliere tutte le corrispondenze.

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: starts_with attraversa il percorso del prefisso e restituisce True se questo esiste; non è necessario verificare is_end, autocomplete raccoglie tramite DFS tutte le parole a partire dal nodo finale del prefisso, aggiungendo i caratteri man mano che scende e arricchire i nodi con conteggi o valori consente di eseguire query di somma e ottenere suggerimenti tra i primi k risultati. Prossimamente aggiungeremo la ricerca con caratteri jolly ed espressioni regolari al trie.