Implementar un diccionario usando Trie

Implemente un diccionario usando Trie de modo que si la entrada es una string que representa una palabra, el programa imprime su significado desde el diccionario preconstruido.

Ejemplos:

Entrada: str = “mapa”
Salida: una representación esquemática de un área

Entrada: str = “idioma”
Salida: el método de comunicación humana

Enfoque: podemos usar un Trie para almacenar strings de manera eficiente y buscarlas. Aquí, se discute una implementación de un diccionario usando Trie (optimización de memoria usando hash-map). Agregamos otro campo al Node Trie, una string que contendrá el significado de una palabra. Mientras buscamos el significado de la palabra requerida, buscamos la palabra en Trie y si la palabra está presente (es decir, isEndOfWord = true), devolvemos su significado; de lo contrario, devolvemos una string vacía.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Structure for Trie
struct Trie {
    bool isEndOfWord;
    unordered_map<char, Trie*> map;
    string meaning;
};
  
// Function to create a new Trie node
Trie* getNewTrieNode()
{
    Trie* node = new Trie;
    node->isEndOfWord = false;
    return node;
}
  
// Function to insert a word with its meaning
// in the dictionary built using a Trie
void insert(Trie*& root, const string& str,
            const string& meaning)
{
  
    // If root is null
    if (root == NULL)
        root = getNewTrieNode();
  
    Trie* temp = root;
    for (int i = 0; i < str.length(); i++) {
        char x = str[i];
  
        // Make a new node if there is no path
        if (temp->map.find(x) == temp->map.end())
            temp->map[x] = getNewTrieNode();
  
        temp = temp->map[x];
    }
  
    // Mark end of word and store the meaning
    temp->isEndOfWord = true;
    temp->meaning = meaning;
}
  
// Function to search a word in the Trie
// and return its meaning if the word exists
string getMeaning(Trie* root, const string& word)
{
  
    // If root is null i.e. the dictionary is empty
    if (root == NULL)
        return "";
  
    Trie* temp = root;
  
    // Search a word in the Trie
    for (int i = 0; i < word.length(); i++) {
        temp = temp->map[word[i]];
        if (temp == NULL)
            return "";
    }
  
    // If it is the end of a valid word stored
    // before then return its meaning
    if (temp->isEndOfWord)
        return temp->meaning;
    return "";
}
  
// Driver code
int main()
{
    Trie* root = NULL;
  
    // Build the dictionary
    insert(root, "language", "the method of human communication");
    insert(root, "computer", "A computer is a machine that can be \
    instructed to carry out sequences of arithmetic or \
logical operations automatically via computer programming");
    insert(root, "map", "a diagrammatic representation \
of an area");
    insert(root, "book", "a written or printed work \
consisting of pages glued or sewn together along one \
side and bound in covers.");
    insert(root, "science", "the intellectual and \
practical activity encompassing the systematic study \
of the structure and behaviour of the physical and \
natural world through observation and experiment.");
  
    string str = "map";
    cout << getMeaning(root, str);
  
    return 0;
}
Producción:

a diagrammatic representation of an area

Publicación traducida automáticamente

Artículo escrito por prajmsidc 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 *