Python中简单的模糊字符串匹配算法是什么？

Question

我正在寻找一种好的模糊字符串匹配算法。直接匹配对我来说不太管用——因为如果我的字符串不完全相同，匹配就会失败。Levenshtein 方法对字符串的处理效果也不好，因为它是按字符来比较的。我想找一种按单词来匹配的算法，比如：

字符串 A: The quick brown fox.

字符串 B: The quick brown fox jumped over the lazy dog.

这两个字符串应该可以匹配，因为字符串 A 中的所有单词都在字符串 B 中出现。

当然，这只是一个简单的例子，但有没有人知道一种好的、能按单词级别进行模糊匹配的算法呢？

Answer 1

如果你只是想测试一个字符串里的所有单词是否都和另一个字符串匹配，那其实只需要一行代码就可以搞定：

if not [word for word in b.split(' ') if word not in a.split(' ')]:
    print 'Match!'

如果你想给这些匹配的单词打分，而不是简单地判断匹配与否，那你可以这样做：

（匹配的单词数量）/（较大字符串中的单词数量） * （较小字符串中的单词数量）/（较大字符串中的单词数量）

这样就能得到一个分数了。

如果你想要更复杂一点的匹配方式，也可以对每个字符串进行模糊匹配。

Answer 2

看看这个Python库，这是SeatGeek昨天开源的。显然，这类问题通常跟具体情况有关，但这个库可能会对你有帮助。

from fuzzywuzzy import fuzz

s1 = "the quick brown fox"
s2 = "the quick brown fox jumped over the lazy dog"
s3 = "the fast fox jumped over the hard-working dog"

fuzz.partial_ratio(s1, s2)
> 100

fuzz.token_set_ratio(s2, s3)
> 73

SeatGeek网站

还有Github仓库

Answer 3

我喜欢Drew的回答。

你可以使用difflib这个库来找到最长的匹配部分：

a = 'The quick brown fox.'
b = 'The quick brown fox jumped over the lazy dog.'
import difflib
s = difflib.SequenceMatcher(None, a, b)
s.find_longest_match(0,len(a),0,len(b))
# Match(a=0, b=0, size=19) # returns NamedTuple (new in v2.6)

或者你可以设定一个最小匹配的标准。比如：

difflib.SequenceMatcher(None, a, b).ratio()
# 0.61538461538461542