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

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

Input: kava
Output: java

Input: ruby
Output: ruby

Input: clujuro
Output: clojure


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" Commented Aug 8, 2011 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. Commented Aug 8, 2011 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. Commented Aug 8, 2011 at 11:13

2 Answers 2


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. Commented Aug 8, 2011 at 9:18

You could use google's "did you mean?" API...


Your Answer

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

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