title: OCR'ed and real string similarity
body: <p>The problem:</p>
  
  <p>There is a set of word S = {W1,W2.. Wn} where n &lt; 10. This set just exists, we do not know its content.
  These words are drawn on some image and then recognized. The OCR algorytm is poor as well as dpi and as a result there are mistakes. So we have a second set of errorneous words S' = {W1',W2'..Wn'}</p>
  
  <p>Now we have a word W that is a member of original set S. And now I need and algorythm which, given W and S', return index of the word in S'. most similar to W.</p>
  
  <p>Example. S is {"alpha", "bravo", "charlie"}, S' is for example {"alPha","hravc","onarlio"} (these are real possible ocr erros).</p>
  
  <p>So the target function should return F("alpha") => 0, F("bravo") => 1, F("charlie") => 2</p>
  
  <p>I tried Levenshtein distance, but it does not work well, because it returns small numbers on small strings and OCRed string can be longer than original. 
  Example if W' is {'hornist','cornrnunist'} and the given word is 'communist' the Levenshtein distance is 4 for the both words, but the right one is second.</p>
  
  <p>Any suggestions?</p>