CODEWITHSUNDEEP
stringalgorithmcomparison
user379468
user379468

Reputation: 4039

Most efficient algorithm for comparing a string with a group of strings

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.

Upvotes: 2

Views: 1488

Answers (3)

Erdinç Taşkın
Erdinç Taşkın

Reputation: 1578

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

Upvotes: 0

recursive
recursive

Reputation: 86172

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.

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 373482

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!

Upvotes: 3

Related Questions