la mise en œuvre d'un dictionnaire

Question

Hii,

je suis tombé sur une question d'entrevue de mettre en œuvre un dictionnaire qui peut mettre en œuvre les caractéristiques de l'auto-complétion, auto - correction, vérifier l'orthographe etc ...

, je voulais savoir quelle structure de données est le meilleur pour la mise en œuvre d'un dictionnaire et comment on se rapproche des caractéristiques ci-dessus nécessaires ...

Tous les liens qui me guident ce sont les bienvenus ...

Answer 1

Il y a juste la même réponse pour cette genre de problème: un Trie. Jetez un oeil here ..

aussi des arbres suffixe (ou Patricia Trees) peuvent être utiles pour ce but ..

Answer 2

Tries sont une structure commune pour cela. Il s'agit d'un cas particulier d'automates à états finis, qui ont également été utilisés pour dictionary construction et spell checking.

Answer 3

Vous pouvez obtenir l'auto-complétion avec un conteneur triés, par exemple un ensemble de chaînes:

#include <limits> 
#include <set> 
#include <string> 
#include <vector> 

int main() 
{ 
    std::set<std::string> words = {"foo", "bar", "barber", "baz", "quux"}; 

    std::string starting_with = "ba"; 
    auto lower = words.lower_bound(starting_with); 
    auto upper = words.upper_bound(starting_with + std::numeric_limits<char>::max()); 

    std::vector<std::string> suggested_words(lower, upper); 
}