在我的工作中,我得到了很好的结果,使用了近似字符串匹配算法,如Damerau-Levenshtein距离,使我的代码不易受到拼写错误的影响.
现在我需要将字符串与简单的正则表达式匹配TV Schedule for \d\d (Jan|Feb|Mar|...).这意味着字符串TV Schedule for 10 Jan应返回0,同时T Schedule for 10. Jan应返回2.
这可以通过在正则表达式中生成所有字符串(在这种情况下为100x12)并找到最佳匹配来完成,但这并不实用.
您有任何想法如何有效地做到这一点？
使用像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是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)>
什么是最好的模糊匹配算法(模糊逻辑,N-Gram,Levenstein,Soundex ....,)能够在更短的时间内处理超过100000条记录？