Структура индексации, используемая в wordweb (английский словарь)

Question

Один из моих друзей столкнулся с этим в своем недавнем интервью. Я публикую 2 вопроса здесь для лучшего решения и к вашему сведению.

- скажем, если вы набираете «light», предложения в выпадающем меню в основном начинаются со слова «light» и появляются по мере ввода и изменения для каждого символа, но если вы набираете «tigress» или «possi», предложения включают "Отступление" или несколько других (то же самое звуковое слово?). Как эта функция предложений может быть достигнута?

- как лучше всего хранить и извлекать синонимы, антонимы, типы, typeof и т. Д., Посмотрите на эти вкладки.

Я не думаю, что это можно решить простым словарным алгоритмом (поправьте меня, если я не прав). Несмотря на то, что его не просили написать какой-либо пример кода, для меня это кажется сложным вопросом.

Answer 1

Первый вопрос:

Я бы использовал структуру данных Trie, основанную на общем свойстве префикса, и построил бы ее, чтобы получить ligh -> light.Я полагаю, что когда мы должны пойти по другому пути, tigress -> digress, построить Trie, используя свойство общего суффикса.То есть, вместо построения три, символ за символом, слева направо, строим его справа налево.

Таким образом, tigress будет разбираться как: s-> s-> e->r-> g-> i-> t И отступление будет проанализировано как: s-> s-> e-> r-> g-> i-> d

Я думаю, что это будет работать для предложений наначало.Но я хотел бы узнать, как мы можем поддержать suggesting next character как в начале, так и в конце.

Answer 2

Re ваш первый вопрос.

расстояние редактирования дает меру того, насколько "разные" два слова.Простая реализация могла бы работать, сравнивая запись с основным списком слов (словарь), а затем предлагая в качестве подсказок лучшие N слов с минимальным количеством баллов.

Answer 3

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

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