реализации словаря

Question

Hii,

я натыкался на интервью вопрос о реализации словаря, который можно реализовать функции автоматического завершения, авто - коррекция, проверка орфографии и т.д. ...

Я на самом деле хотел знать, какая структура данных является наилучшим для реализации словаря и как один приближается необходимые выше черты ...

Любые ссылки, которые ведут меня на этом приветствуются ...

Answer 1

Существует так же ответ на этот вид проблемы: a описание товара Trie. Посмотрите here ..

Также суффикс деревья (или Patricia Деревья) могут быть полезны для этих целей ..

Answer 2

Tries являются общая структура для этого. Они являются частным случаем автоматов с конечным состоянием, которые также использовались для dictionary construction и spell checking.

Answer 3

Вы можете получить автоматическое завершение с любым отсортированных контейнером, например, набор строк:

#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); 
}