Are there any algorithms that would find the closest match to a string from a collection of strings?

Question

Are there any algorithms that would find the closest match to a string from a collection of strings? For example:

string_to_match = 'What color is the sky?'

strings = [
  'What colour is the sea?', 
  'What colour is the sky?', 
  'What colour is grass?', 
  'What colour is earth?'
]

answer = method_using_string_matching_algorithm(string_to_match, strings)
answer # returns strings[1] 'What colour is the sky?'

Possible duplicate : http://stackoverflow.com/questions/49263/approximate-string-matching-algorithms — DhruvPathak, Apr 27 '12 at 10:21
Have you tried [Wikipedia](http://en.wikipedia.org/wiki/Approximate_string_matching)? — Richard Inglis, Apr 27 '12 at 10:22
Why can't you run string matching on each of the strings one by one ? — axiom, Apr 27 '12 at 10:23
@DhruvPathak they're duplicate questions, the distance can be defined as [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance) — pengdu, Apr 27 '12 at 10:46
@RichardInglis thanks, previous searches on the topic hadn't included the word 'Approximate'. The Wikipedia page looks like a good starting point. — Neil, Apr 27 '12 at 17:15

score 5 · Accepted Answer · answered May 31 '12 at 13:22

The search terms you're looking for are "string distance algorithms" and "approximate string matching." A quick check of Google turns up interesting options such as:

Sift3 Distance
Levenshtein Distance
Optimal String Alignment Distance
Damerau-Levenshtein Distance
Qwerty Keyboard Distance

Some useful links include:

As of this writing, Debian-based Linux distributions also include agrep and TRE-agrep in their repositories.

thanks for the keywords and links. I've been using the Ruby Amatch gem which includes Levenshtein http://flori.github.com/amatch/ — Neil, May 31 '12 at 17:40

Are there any algorithms that would find the closest match to a string from a collection of strings?

1 Answers1