Проверка орфографии с использованием дерева троичного поиска

Question

Я сделал проверку орфографии, используя троичное дерево поиска (TST). Кто-нибудь может сказать мне, как найти следующее возможное слово в TST?

например: если я хочу найти слово "мужественный" в средстве проверки правописания и если слово отсутствует в TST, чтобы оно выводило слова рядом со следующими:

ВЫ ЗНАЧИТЕ: "Человек", "Манго".

Вот код для реализации троичного дерева поиска. Может ли любое тело, пожалуйста, изменить, чтобы найти ближайшее возможное слово. http://www.geeksforgeeks.org/ternary-search-tree/

Answer 1

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

В вашем примере (при условии, что "мужественного" нет в вашем словаре, хотя это слово), предложение "главным образом" гораздо более вероятно, чем "манго", но оно не будет найдено при сканировании, начиная с самого длинного соответствующий префикс.

Однако, если вы хотите, чтобы сканирование начиналось с самого длинного префикса соответствия:

1) Измените searchTST, чтобы он возвращал struct Node*и замените последнее предложение else на:

else if (*(word+1) == '\0')
  return root;
else {
  struct Node* child = searchTST(root->eq, word+1);
  return child ? child : root;
}

2) searchTST теперь вернет корень для самого длинного совпадающего префикса к цели. Вызывающий должен проверить, есть ли у возвращенного узла isEndOfString флаг установлен.

3) Вы можете использовать что-то вроде traverseTST на узле, возвращенном searchTST чтобы произвести все слова, начинающиеся с этого префикса.

Answer 2

Вы можете попробовать подстановочный знак. Например, замените где-нибудь в вашем поисковом слове букву подстановочным знаком, затем разбейте слово на две подстроки и вставьте их в TST. Затем найдите все шаблоны, а не только точное совпадение. Это работает, создавая все префиксы словарного слова. Но я рекомендую попробовать алгоритм aho-corasick с TST.