Проверка нечеткой / приблизительной подстроки, существующей в более длинной строке, в Python?
Используя такие алгоритмы, как 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