Hai visto le parole AutoSuggestions / Completamento automatico durante la ricerca in base al prefisso della stringa? Come sotto:
Questi suggerimenti sono anche molto rapidi ed efficienti .
Sai come sono venuti questi suggerimenti? Con quale struttura dati possiamo renderlo efficiente e veloce?
La maggior parte di noi pensa che l’indicizzazione della colonna / chiave risolverà questo problema. I grandi sistemi con enormi set di dati non possono fare affidamento solo su questa cosa.
La migliore struttura di dati da utilizzare per questo problema è ”Trie”
Cos’è la struttura dei dati Trie? Quale sarà il numero massimo di nodi dalla radice? Se con s ider solo caratteri alfabetici, il numero massimo di nodi figlio da root solo è 26 (a-z). Se consideriamo anche i numeri, possiamo pensare che il numero sarà 36 (a-z + 0–9) – Non utilizzato generalmente. Perché considerare Trie se abbiamo già set e hashmap? Con i set e le mappe hash, la complessità temporale non è efficiente. Anche con le mappe hash dobbiamo considerare anche le collisioni di hash. In Confronto per ricerca / inserimento Trie la complessità temporale è O (P) dove P è la lunghezza della stringa del prefisso. Implementazione di Trie: Finora abbiamo affrontato solo la parte teorica. Creiamo una struttura trie di esempio e saremo in grado di digerire tutto ciò di cui abbiamo discusso: Prendi un sistema di dipendenti con un elenco di nomi contenente: [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”]. Rappresentazione del set di dati di cui sopra con Trie: Nell’istantanea sopra possiamo vedere r è al nodo radice e tutti i percorsi successivi che abbiamo disegnato. Ora prova a trovare tutte le parole che iniziano con il prefisso “ra”. Guarda come funziona: Ora considera set con diversi prefissi parole come [“rahul”, “raju”, “rishabh”, “radhe”, “rockey”, “javascript”, “trie”]. Secondo il nostro approccio, dobbiamo creare un Trie separato per ogni prefisso. Quindi questo approccio non è del tutto corretto. L’approccio corretto è avere un elemento nullo alla radice e quindi aggiungere gli elementi successivi nell’albero. Se non esiste, creane uno nuovo e collegalo a root. Codice Trie per inserimento, suggerimento automatico e verifica se Word esiste: Nota: alcune applicazioni utilizzano Trie con alcune modifiche come l’assegnazione del ranking alle parole più cercate. In base al posizionamento, restituiremo i suggerimenti di ricerca più comuni in caso di suggerimenti limitati. Applicazioni di Trie: Il codice è disponibile su: https://github.com/rishabhjj/Datastructure_Algorithm/blob/master/LinkedList/Geeks/Trie.js In caso di domande e suggerimenti, si prega di mettersi in contatto con me <”https://www.linkedin.com/in/rishabh-jain-a5978583/ o invia una mail @ rishabh171192 @ gmail.com 
