title: Find best substring match
body: <p>I'm looking for a library or a method using existing libraries( <a href="https://docs.python.org/2/library/difflib.html"><code>difflib</code></a>, <a href="https://github.com/seatgeek/fuzzywuzzy"><code>fuzzywuzzy</code></a>, <a href="https://github.com/ztane/python-Levenshtein/"><code>python-levenshtein</code></a>) to find the closest match of a string (<code>query</code>) in a text (<code>corpus</code>)</p>
  
  <p>I've developped a method based on <code>difflib</code>, where I split my <code>corpus</code> into ngrams of size <code>n</code> (length of <code>query</code>).</p>
  
  <pre><code>import difflib
  from nltk.util import ngrams
  
  def get_best_match(query, corpus):
      ngs = ngrams( list(corpus), len(query) )
      ngrams_text = [''.join(x) for x in ngs]
      return difflib.get_close_matches(query, ngrams_text, n=1, cutoff=0)
  </code></pre>
  
  <p>it works as I want when the difference between the query and the matched string are just character replacements.</p>
  
  <pre><code>query = "ipsum dolor"
  corpus = "lorem 1psum d0l0r sit amet"
  
  match = get_best_match(query, corpus)
  # match = "1psum d0l0r"
  </code></pre>
  
  <p>But when the difference is character deletion, it is not.</p>
  
  <pre><code>query = "ipsum dolor"
  corpus = "lorem 1psum dlr sit amet"
  
  match = get_best_match(query, corpus)
  # match = "psum dlr si"
  # expected_match = "1psum dlr"
  </code></pre>
  
  <p>Is there a way to get a more flexible result size ( as for <code>expected_match</code> ) ?</p>
  
  <h2>EDIT 1:</h2>
  
  <ul>
  <li>The actual use of this script is to match queries (strings) with a
  messy ocr output.</li>
  <li>As I said in the question, the ocr can confound characters, and even miss them.</li>
  <li>If possible consider also the case when a space is missing between words.</li>
  <li>A best match, is the one that does not include characters from other words than those on the query.</li>
  </ul>
  
  <h2>EDIT 2:</h2>
  
  <p>The solution I use now is to extend the ngrams with <code>(n-k)-grams for k = {1,2,3}</code> to prevent 3 deletions. It's much better than the first version, but not efficient in terms of speed, as we have more than 3 times the number of ngrams to check. It is also a non generalizable solution.</p>