在Python中检查较长字符串中存在的模糊/近似子字符串？

使用像leveinstein（leveinstein或difflib）这样的算法，很容易找到近似匹配。

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

可以根据需要确定阈值来检测模糊匹配。

当前需求：根据较大字符串中的阈值查找模糊子字符串。

eg.

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 是 query_string 的长度，并对它们一一使用 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)>

新的正则表达式库很快就会取代 re ，其中包括模糊匹配。

https://pypi.python.org/pypi/regex/ https://pypi.python.org/pypi/regex/

模糊匹配语法看起来相当具有表现力，但这将为您提供一个或更少的插入/添加/删除的匹配。

import regex
regex.match('(amazing){e<=1}', 'amaging')