Función de autocompletar usando Trie

Nos dan un Trie con un conjunto de strings almacenadas en él. Ahora que el usuario escribe un prefijo de su consulta de búsqueda, debemos darle todas las recomendaciones para completar automáticamente su consulta en función de las strings almacenadas en el Trie. Suponemos que Trie almacena búsquedas anteriores de los usuarios.
Por ejemplo, si la tienda Trie {“abc”, “abcd”, “aa”, “abbbaba”} y el usuario escribe “ab”, entonces se le debe mostrar {“abc”, “abcd”, “abbbaba”}.
Prerrequisito Trie Buscar e Insertar .
 

Dado un prefijo de consulta, buscamos todas las palabras que tengan esta consulta. 
 

1. Busque la consulta dada utilizando el algoritmo de búsqueda Trie estándar.
2. Si el prefijo de consulta en sí no está presente, devuelva -1 para indicar lo mismo.
3. Si la consulta está presente y es el final de una palabra en Trie, imprima la consulta. Esto se puede verificar rápidamente al ver si el último Node coincidente tiene establecido el indicador isEndWord . Usamos esta bandera en Trie para marcar el final de los Nodes de palabras con el propósito de buscar.
4. Si el último Node coincidente de la consulta no tiene elementos secundarios, regrese.
5. De lo contrario, imprima recursivamente todos los Nodes debajo de un subárbol del último Node coincidente.

A continuación se muestran algunas implementaciones de los pasos anteriores.
 

// C++ program to demonstrate auto-complete feature
// using Trie data structure.
#include <bits/stdc++.h>
using namespace std;
 
// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
 
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
 
// trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // isWordEnd is true if the node represents
    // end of a word
    bool isWordEnd;
};
 
// Returns new trie node (initialized to NULLs)
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
    pNode->isWordEnd = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// If not present, inserts key into trie.  If the
// key is prefix of trie node, just marks leaf node
void insert(struct TrieNode* root, const string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int level = 0; level < key.length(); level++) {
        int index = CHAR_TO_INDEX(key[level]);
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // mark last node as leaf
    pCrawl->isWordEnd = true;
}
 
// Returns 0 if current node has a child
// If all children are NULL, return 1.
bool isLastNode(struct TrieNode* root)
{
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i])
            return 0;
    return 1;
}
 
// Recursive function to print auto-suggestions for given
// node.
void suggestionsRec(struct TrieNode* root,
                    string currPrefix)
{
    // found a string in Trie with the given prefix
    if (root->isWordEnd)
        cout << currPrefix << endl;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i]) {
            // child node character value
            char child = 'a' + i;
            suggestionsRec(root->children[i],
                           currPrefix + child);
        }
}
 
// print suggestions for given query prefix.
int printAutoSuggestions(TrieNode* root, const string query)
{
    struct TrieNode* pCrawl = root;
    for (char c : query) {
        int ind = CHAR_TO_INDEX(c);
 
        // no string in the Trie has this prefix
        if (!pCrawl->children[ind])
            return 0;
 
        pCrawl = pCrawl->children[ind];
    }
    // If prefix is present as a word, but
    // there is no subtree below the last
    // matching node.
    if (isLastNode(pCrawl)) {
        cout << query << endl;
        return -1;
    }
    suggestionsRec(pCrawl, query);
    return 1;
}
 
// Driver Code
int main()
{
    struct TrieNode* root = getNode();
    insert(root, "hello");
    insert(root, "dog");
    insert(root, "hell");
    insert(root, "cat");
    insert(root, "a");
    insert(root, "hel");
    insert(root, "help");
    insert(root, "helps");
    insert(root, "helping");
    int comp = printAutoSuggestions(root, "hel");
 
    if (comp == -1)
        cout << "No other strings found with this prefix\n";
 
    else if (comp == 0)
        cout << "No string found with this prefix\n";
 
    return 0;
}

# Python3 program to demonstrate auto-complete
# feature using Trie data structure.
# Note: This is a basic implementation of Trie
# and not the most optimized one.
 
 
class TrieNode():
    def __init__(self):
        # Initialising one node for trie
        self.children = {}
        self.last = False
 
 
class Trie():
    def __init__(self):
 
        # Initialising the trie structure.
        self.root = TrieNode()
 
    def formTrie(self, keys):
 
        # Forms a trie structure with the given set of strings
        # if it does not exists already else it merges the key
        # into it by extending the structure as required
        for key in keys:
            self.insert(key)  # inserting one key to the trie.
 
    def insert(self, key):
 
        # Inserts a key into trie if it does not exist already.
        # And if the key is a prefix of the trie node, just
        # marks it as leaf node.
        node = self.root
 
        for a in key:
            if not node.children.get(a):
                node.children[a] = TrieNode()
 
            node = node.children[a]
 
        node.last = True
 
    def suggestionsRec(self, node, word):
 
        # Method to recursively traverse the trie
        # and return a whole word.
        if node.last:
            print(word)
 
        for a, n in node.children.items():
            self.suggestionsRec(n, word + a)
 
    def printAutoSuggestions(self, key):
 
        # Returns all the words in the trie whose common
        # prefix is the given key thus listing out all
        # the suggestions for autocomplete.
        node = self.root
 
        for a in key:
            # no string in the Trie has this prefix
            if not node.children.get(a):
                return 0
            node = node.children[a]
 
        # If prefix is present as a word, but
        # there is no subtree below the last
        # matching node.
        if not node.children:
            return -1
 
        self.suggestionsRec(node, key)
        return 1
 
 
# Driver Code
keys = ["hello", "dog", "hell", "cat", "a",
        "hel", "help", "helps", "helping"]  # keys to form the trie structure.
key = "h"  # key for autocomplete suggestions.
 
# creating trie object
t = Trie()
 
# creating the trie structure with the
# given set of strings.
t.formTrie(keys)
 
# autocompleting the given key using
# our trie structure.
comp = t.printAutoSuggestions(key)
 
if comp == -1:
    print("No other strings found with this prefix\n")
elif comp == 0:
    print("No string found with this prefix\n")
 
# This code is contributed by amurdia and muhammedrijnas

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class Trie {
 
    public class TrieNode {
        Map<Character, TrieNode> children;
        char c;
        boolean isWord;
 
        public TrieNode(char c) {
            this.c = c;
            children = new HashMap<>();
        }
 
        public TrieNode() {
            children = new HashMap<>();
        }
 
        public void insert(String word) {
            if (word == null || word.isEmpty())
                return;
            char firstChar = word.charAt(0);
            TrieNode child = children.get(firstChar);
            if (child == null) {
                child = new TrieNode(firstChar);
                children.put(firstChar, child);
            }
 
            if (word.length() > 1)
                child.insert(word.substring(1));
            else
                child.isWord = true;
        }
 
    }
 
    TrieNode root;
 
    public Trie(List<String> words) {
        root = new TrieNode();
        for (String word : words)
            root.insert(word);
 
    }
 
    public boolean find(String prefix, boolean exact) {
        TrieNode lastNode = root;
        for (char c : prefix.toCharArray()) {
            lastNode = lastNode.children.get(c);
            if (lastNode == null)
                return false;
        }
        return !exact || lastNode.isWord;
    }
 
    public boolean find(String prefix) {
        return find(prefix, false);
    }
 
    public void suggestHelper(TrieNode root, List<String> list, StringBuffer curr) {
        if (root.isWord) {
            list.add(curr.toString());
        }
 
        if (root.children == null || root.children.isEmpty())
            return;
 
        for (TrieNode child : root.children.values()) {
            suggestHelper(child, list, curr.append(child.c));
            curr.setLength(curr.length() - 1);
        }
    }
 
    public List<String> suggest(String prefix) {
        List<String> list = new ArrayList<>();
        TrieNode lastNode = root;
        StringBuffer curr = new StringBuffer();
        for (char c : prefix.toCharArray()) {
            lastNode = lastNode.children.get(c);
            if (lastNode == null)
                return list;
            curr.append(c);
        }
        suggestHelper(lastNode, list, curr);
        return list;
    }
   
 
    public static void main(String[] args) {
        List<String> words = List.of("hello", "dog", "hell", "cat", "a", "hel","help","helps","helping");
        Trie trie = new Trie(words);
     
        System.out.println(trie.suggest("hel"));
    }
 
}

hel
hell
hello
help
helping
helps

¿Cómo podemos mejorar esto?  
La cantidad de coincidencias puede ser demasiado grande, por lo que debemos ser selectivos al mostrarlas. Podemos limitarnos a mostrar solo los resultados relevantes. Por relevante, podemos considerar el historial de búsqueda anterior y mostrar solo las strings coincidentes más buscadas como resultados relevantes. 
Almacene otro valor para cada Node donde isleaf=True que contiene el número de aciertos para esa búsqueda de consulta. Por ejemplo, si «sombrero» se busca 10 veces, almacenamos este 10 en el último Node para «sombrero». Ahora, cuando queremos mostrar las recomendaciones, mostramos las k mejores coincidencias con los resultados más altos. Intenta implementar esto por tu cuenta.
Este artículo es una contribución de Hemang Sarkar. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.