Эффективный алгоритм поиска подходящих подстрок
Пример: у меня есть много таких шаблонов:
sexy hello
sex every
sex example
...
У меня есть такой запрос:
hello, sexygirl.
Этот запрос будет соответствовать первому шаблону. Потому что он содержит сексуальный и привет.
Внимание: секси и девушка не имеют бланка.
Есть ли эффективный способ решить эту проблему?
Решение
Это может помочь вам, даже если это в c, многие концепции одинаковы:
Какой самый быстрый алгоритм поиска подстроки?
Начнем с того, что большинство шаблонов, которые у вас есть, содержат слово «секс», поэтому не имеет смысла включать это в ваш запрос. Итак, вы должны токенизировать запрос и удалить все стоп-слова. Это оставит вас с простыми сравнениями строк, и, поскольку вполне вероятно, что ваши шаблоны будут иметь данные в паре с ними, например, текстовый ответ, вы можете использовать хеш-функцию для сравнения строк и затем манипулировать данными, которые соответствуют шаблону , (например: ответить на «Hello sexygirl», превратив его в [«Hello», «sexygirl»], затем [«Hello»], и проверив это на предмет unordered_map, который отвечал бы всем, что у вас на уме)
Еще одна вещь, на которую вы можете обратить внимание — это цепочка Маркова, которая обычно используется для генерации текста, но может помочь в этом случае.
Небольшой пример того, что могут цепи Маркова делать
Другие решения
Других решений пока нет …