Usando algoritmos como leveinstein (leveinstein o difflib), es fácil encontrar coincidencias aproximadas.

>>> import difflib
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio()
0.8571428571428571

Las coincidencias difusas se pueden detectar al decidir un umbral según sea necesario.

Requisito actual: para encontrar una subcadena difusa basada en un umbral en una cadena más grande.

p.ej.

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
#result = "manhatan","manhattin" and their indexes in large_string

Una solución de fuerza bruta es generar todas las subcadenas de longitud N-1 a N + 1 (u otra longitud coincidente), donde N es la longitud de query_string, y usar levenstein en ellas una por una y ver el umbral.

¿Existe una mejor solución disponible en python, preferiblemente un módulo incluido en python 2.7, o un módulo externo disponible?

ACTUALIZAR : El módulo de expresiones regulares de Python funciona bastante bien, aunque es un poco más lento que el incorporadore Módulo para casos de subcadenas difusas, que es un resultado obvio debido a operaciones adicionales. La salida deseada es buena y el control sobre la magnitud de la borrosidad se puede definir fácilmente.

>>> import regex
>>> input = "Monalisa was painted by Leonrdo da Vinchi"
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE)
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)>