Как реализовать словарь в C / C ++ с помощью автозамены, автозаполнения, проверки орфографии

Question

Я должен написать код C / C ++ для реализации словаря со следующими функциями:

Есть в основном определения (1 или более) для слов.

1) Вставка

2) Поиск (как можно быстрее)

3) Автозаполнение

4) Автокоррекция

5) Проверка орфографии

Так что мне нужно знать, КАК ДЕЛАТЬ ТАК?

Какие структуры данных должны быть наиболее эффективными? Три или Хаст стол или что-то еще

Какую технику поиска использовать ...?

Как эффективно реализовать автозаполнение и проверку орфографии ..?

Answer 1

Обычно вы используете дерево слов, упорядоченное в соответствии с расстоянием редактирования друг от друга, например BK tree .

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

РЕДАКТИРОВАТЬ: задним числом, эта статья, на которую я ссылался, гораздо лучше объясняет, чем я. Я просто рекомендовал бы прочитать это для хорошего объяснения подхода.

Answer 2

Конечно, вам нужна база данных со списком слов, затем вам нужно разбить текст на слова и посмотреть, существуют ли они в базе данных.

Для автозаполнения вы можете просто проверить, что введенный текст соответствует словам в словаре (с предложением LIKE txt + '%'), реализованным с помощью вызова AJAX.