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

Question

Hii,

Я наткнулся на вопрос об использовании словаря, который может реализовывать функции автозаполнения, автокоррекции, проверки орфографии и т. Д. *

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

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

Answer 1

Попытки являются общей структурой для этого.Это особый случай конечных автоматов, которые также использовались для построения словаря и проверки орфографии .

Answer 2

Для такой проблемы есть один и тот же ответ: a Trie . Взгляните здесь ..

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

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