Используя такие алгоритмы, как leveinstein (leveinstein или difflib), легко найти приблизительные совпадения.

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

Нечеткие совпадения могут быть обнаружены путем определения порогового значения при необходимости.

Текущее требование: найти нечеткую подстроку на основе порога в большей строке.

например.

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

Одно из решений грубой силы состоит в том, чтобы сгенерировать все подстроки длиной от N-1 до N + 1 (или другой подходящей длины), где N - длина строки запроса, и использовать levenstein для них одну за другой и увидеть порог.

Есть ли лучшее решение, доступное в Python, предпочтительно включенный модуль в Python 2.7, или модуль, доступный извне.

ОБНОВИТЬ : Модуль регулярных выражений Python работает довольно хорошо, хотя он немного медленнее, чем встроенныйre модуль для случаев нечеткой подстроки, который является очевидным результатом из-за дополнительных операций. Требуемый выходной сигнал хорош, и контроль над степенью размытости может быть легко определен.

>>> 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)>