11

I am working over a OCR Application where I need to select a option based on user text input.

Ex:
Available Options:
["python", "ruby", "java", "clojure", "haskell"]

Input: kava
Output: java

Input: ruby
Output: ruby

Input: clujuro
Output: clojure

etc.. 

my application is python based, is there a algorithm already exist to solve this problem.

  • 1
    It may not be worth it to correct now but IMO a more appropriate title would be "how to determine distance (difference) between strings" – Jeff Welling Aug 8 '11 at 9:22
  • 3
    @Jeff: and then I would never find this question, because I wouldn't have any idea that what I need might be called "the distance difference"... And that's not the only reason not to put the solution you need in the question. It may preclude people from suggesting alternate solutions to the problem you are actually having. Case in point: loudsight's answer. – Marjan Venema Aug 8 '11 at 10:28
  • 1
    My point was, now that you do know, using a more accurate title may help attract answers from people who don't know what "how to select a most probable..." means but who would recognize "distance between strings", but to each his own. It was just a suggestion. I didn't know what you meant and nearly didn't click on your question because of it is all. – Jeff Welling Aug 8 '11 at 11:13
10

This is done by algorithms of the "approximate string matching" category. A common measure to compare two strings is called the Levenshtein distance. There's a python implementation available here.

You basically compare the input to the possible outputs and choose the one with the smallest distance to the desired output.

The wikipedia article also mentions various other algorithms which you can try in case you need something more specific.

  • I had a similar problem in ruby and this is exactly how I solved it. – Jeff Welling Aug 8 '11 at 9:18
7

You could use google's "did you mean?" API...
http://pygoogle.sourceforge.net/dist/doc/public/google-module.html#doSpellingSuggestion

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.