Cómo implementar la función de autocompletar texto usando el árbol de búsqueda ternario

Dado un conjunto de strings S y una string patt , la tarea es autocompletar la string patt con las strings de S que tienen patt como prefijo, utilizando un árbol de búsqueda ternario . Si ninguna string coincide con el prefijo dado, imprima «Ninguno» .
Ejemplos: 
 

Entrada: S = {“wallstreet”, “geeksforgeeks”, “wallmart”, “walmart”, “waldomort”, “word”], 
patt = “wall” 
Salida: 
wallstreet 
wallmart 
Explicación: 
Solo dos strings {“wallstreet”, “ wallmart”} de S coincide con el patrón dado “wall”.
Entrada: S = {“word”, “wallstreet”, “wall”, “wallmart”, “walmart”, “waldo”, “won”}, patt = “geeks” 
Salida: Ninguno 
Explicación: 
Dado que ninguno de word of set coincide con el patrón, por lo que se imprimirá una lista vacía. 
 

Enfoque Trie: consulte este artículo para obtener información sobre la implementación mediante la estructura de datos Trie . Enfoque del
árbol de búsqueda ternario Siga los pasos a continuación para resolver el problema: 
 

  • Inserte todos los caracteres de las strings en S en el árbol de búsqueda ternario según las siguientes condiciones: 
    1. Si el carácter que se va a insertar es más pequeño que el valor del Node actual, recorra el subárbol izquierdo.
    2. Si el carácter que se va a insertar es mayor que el valor del Node actual, recorra el subárbol derecho hasta.
    3. Si el carácter que se va a insertar es el mismo que el del valor del Node actual, recorra el subárbol igual si no es el final de la palabra. Si es así, marque el Node como el final de la palabra.
  • Siga un enfoque similar para extraer sugerencias.
  • Atraviese el árbol para buscar el prefijo patt dado siguiendo una técnica de recorrido similar a la mencionada anteriormente.
  • Si no se encuentra el prefijo proporcionado, imprima «Ninguno».
  • Si se encuentra el prefijo dado, recorra el árbol desde el Node donde termina el prefijo. Atraviese el subárbol izquierdo y genere sugerencias seguidas por los subárboles derecho e igual de cada Node.
  • Cada vez que se encuentra un Node que tiene establecida la variable endofWord , indica que se ha obtenido una sugerencia. Inserte esa sugerencia en palabras .
  • Devuelve palabras después de generar todas las sugerencias posibles.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ Program to generate
// autocompleted texts from
// a given prefix using a
// Ternary Search Tree
#include <bits/stdc++.h>
using namespace std;
 
// Define the Node of the
// tree
struct Node {
 
    // Store the character
    // of a string
    char data;
    // Store the end of
    // word
    int end;
    // Left Subtree
    struct Node* left;
 
    // Equal Subtree
    struct Node* eq;
 
    // Right Subtree
    struct Node* right;
};
 
// Function to create a Node
Node* createNode(char newData)
{
    struct Node* newNode = new Node();
    newNode->data = newData;
    newNode->end = 0;
    newNode->left = NULL;
    newNode->eq = NULL;
    newNode->right = NULL;
    return newNode;
}
 
// Function to insert a word
// in the tree
void insert(Node** root,
            string word,
            int pos = 0)
{
 
    // Base case
    if (!(*root))
        *root = createNode(word[pos]);
 
    // If the current character is
    // less than root's data, then
    // it is inserted in the
    // left subtree
 
    if ((*root)->data > word[pos])
        insert(&((*root)->left), word,
               pos);
 
    // If current character is
    // more than root's data, then
    // it is inserted in the right
    // subtree
 
    else if ((*root)->data < word[pos])
        insert(&((*root)->right), word,
               pos);
 
    // If current character is same
    // as that of the root's data
 
    else {
        // If it is the end of word
 
        if (pos + 1 == word.size())
            // Mark it as the
            // end of word
            (*root)->end = 1;
 
        // If it is not the end of
        // the string, then the
        // current character is
        // inserted in the equal subtree
 
        else
            insert(&((*root)->eq), word, pos + 1);
    }
}
 
// Function to traverse the ternary search tree
void traverse(Node* root,
              vector<string>& ret,
              char* buff,
              int depth = 0)
{
    // Base case
    if (!root)
        return;
    // The left subtree is
    // traversed first
    traverse(root->left, ret,
             buff, depth);
 
    // Store the current character
    buff[depth] = root->data;
 
    // If the end of the string
    // is detected, store it in
    // the final ans
    if (root->end) {
        buff[depth + 1] = '\0';
        ret.push_back(string(buff));
    }
 
    // Traverse the equal subtree
    traverse(root->eq, ret,
             buff, depth + 1);
 
    // Traverse the right subtree
    traverse(root->right, ret,
             buff, depth);
}
 
// Utility function to find
// all the words
vector<string> util(Node* root,
                    string pattern)
{
    // Stores the words
    // to suggest
    char buffer[1001];
 
    vector<string> ret;
 
    traverse(root, ret, buffer);
 
    if (root->end == 1)
        ret.push_back(pattern);
    return ret;
}
 
// Function to autocomplete
// based on the given prefix
// and return the suggestions
vector<string> autocomplete(Node* root,
                            string pattern)
{
    vector<string> words;
    int pos = 0;
 
    // If pattern is empty
    // return an empty list
    if (pattern.empty())
        return words;
 
    // Iterating over the characters
    // of the pattern and find it's
    // corresponding node in the tree
 
    while (root && pos < pattern.length()) {
 
        // If current character is smaller
        if (root->data > pattern[pos])
            // Search the left subtree
            root = root->left;
 
        // current character is greater
        else if (root->data < pattern[pos])
            // Search right subtree
            root = root->right;
 
        // If current character is equal
        else if (root->data == pattern[pos]) {
           
            // Search equal subtree
              // since character is found, move to the next character in the pattern
            root = root->eq;
            pos++;
        }
 
        // If not found
        else
            return words;
 
    }
 
    // Search for all the words
    // from the current node
    words = util(root, pattern);
 
    return words;
}
 
// Function to print
// suggested words
 
void print(vector<string> sugg,
           string pat)
{
    for (int i = 0; i < sugg.size();
         i++)
        cout << pat << sugg[i].c_str()
             << "\n";
}
 
// Driver Code
int main()
{
    vector<string> S
        = { "wallstreet", "geeksforgeeks",
            "wallmart", "walmart",
            "waldormort", "word" };
 
    Node* tree = NULL;
 
    // Insert the words in the
    // Ternary Search Tree
    for (string str : S)
        insert(&tree, str);
 
    string pat = "wall";
 
    vector<string> sugg
        = autocomplete(tree, pat);
 
    if (sugg.size() == 0)
        cout << "None";
 
    else
        print(sugg, pat);
 
    return 0;
}
Producción

wallmart
wallstreet

Complejidad de tiempo: O(L* log N) donde L es la longitud de la palabra más larga. 
El espacio es proporcional a la longitud de la string a almacenar.
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por thesyncoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *