Find best substring match
<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>