Наиболее эффективный алгоритм сравнения строки с группой строк

Question

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

Answer 1

Если у вас большое количество «волшебных» слов, я бы предложил разбить запрос на слова и использовать поиск на основе хеша, чтобы проверить, распознаются ли слова.

Answer 2

Возможно, вы захотите изучить алгоритм Aho-Corasick . Если у вас есть набор строк, которые вы хотите найти, вы можете потратить линейное время на предварительную обработку этих строк и с этого момента в течение O (n) времени проверить все возможные совпадения этих строк в текстовом корпусе. длиной n. Другими словами, с небольшим временем предварительной обработки, чтобы настроить алгоритм один раз, вы можете чрезвычайно эффективно сканировать многочисленные входные данные снова и снова в поисках этих ключевых слов.

Интересно, что алгоритм был специально придуман для создания быстрого индекса (то есть для поиска множества различных ключевых слов в огромном объеме текста) и, как утверждается, превосходил другие методы в десять раз. Я думаю, что это будет отлично работать в вашем приложении.

Надеюсь, это поможет!

Answer 3

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