Как выбрать структуру данных для поиска предложений только с известными словами

Question

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

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

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

Answer 1

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

• буква
• , является ли это концом слова

Например, на root Уровень у вас будет узел "а", который является собственным словом. Одним из его потомков будет «s», что также является его собственным словом, потому что, читая его вместе с родителем, вы получаете «как» и так далее. Поиск слова в этом дереве займет максимум 26 + длина слова - 1.

Answer 2

Для решения этой проблемы лучше всего использовать go - использовать дерево. Я бы порекомендовал вам взглянуть на Tries или Radix деревьев . Они позволяют сократить время поиска до логарифмического c времени.