2

I have a scenario where a user can post a number of responses or phrases via a form field. I would like to be able to take the response and determine what they are asking for. For instance if the user types in car, train, bike, jet .... I can assume they are talking about a vehicle, and respond accordingly. I understand that I could use a switch statement or perhaps a regexp as well, however the larger the number of possible responses, the less efficient that computation will be. I'm wondering if there is an efficient algorithm for comparing a string with a group of strings. Any info would be great.

Improve this question

3 Answers 3

Reset to default
3

You may want to look into the Aho-Corasick algorithm. If you have a collection of strings that you want to search for, you can spend linear time doing preprocessing on those strings and from that point forward can, in O(n) time, check for all possible matches of those strings in a text corpus of length n. In other words, with a small preprocessing time to set up the algorithm once, you can extremely efficiently scan over numerous inputs again and again searching for those keywords.

Interestingly enough, the algorithm was specifically invented to build a fast index (that is, to look for a lot of different keywords in a huge body of text), and allegedly outperformed other methods by a factor of ten. I think it would work great in your application.

Hope this helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Fascinating. I'm beginning to suspect that FSMs are the single most underrated concept in computer science.
@SeanU- I love automata. They're just great. Aho-Corasick is definitely underrated.
3

If you have a large number of "magic" words, I would suggest splitting the query into words, and using a hash-based lookup to check whether the words are recognized.

Improve this answer

1 Comment

Interestingly, if you compare my approach and your approach, what you're proposing is a generalization of the Rabin-Karp algorithm and what I'm proposing is the generalization of Knuth-Morris-Pratt. :-)
0

You can check Trie structure. I think one of best solution for your problem.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.