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

Question

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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