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

我试图找到一种很好的模糊字符串匹配算法。直接匹配不适用于我 - 这不太好，因为除非我的字符串100％相似，否则匹配会失败。对于字符串，Levenshtein方法工作得不好，因为它在字符级别上工作。我正在寻找符合词级匹配的东西，例如什么是Python中的简单模糊字符串匹配算法？

String A：快速的棕色狐狸。

字符串B：快速的棕色狐狸跃过了懒狗。

这些应该匹配在字符串中的所有单词都串B.现在

，这是一个过于简单的例子，但会有人知道一个良好的，模糊的字符串匹配算法，就一个字水平的作品。

来源

2010-05-27 Mridang Agarwalla

所以，你要知道，如果字符串A字符串B的近的子集？如果您交换字符串A和B，它*不匹配吗？ – Dolph 2010-05-27 17:38:01

我喜欢Drew's answer。

您可以使用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

来源

2010-05-27 17:50:42 bernie

我认为difflib更接近OP想要的东西。他说'模糊'，所以我认为他的例子只是一个特别简单的例子。 – 2010-05-27 18:01:38

'比例（）'也适用于序列项目（=字符）级别，所以您的答案需要更多的工作。 :) – badp 2010-05-27 18:02:36

@bp：谢谢。我又增加了一个更适合这个问题的例子。 – bernie 2010-05-27 18:03:26

如果你想要做的是测试所有的字符串的话是否一致另一个字符串，这是一个内衬：

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

如果你想得分它们而不是二进制测试，为什么不只是这样做：

（匹配单词（＃）/（在更大的串词＃））* （（在较小的串词）的＃/（在更大的串词＃））

？

如果你愿意，你可以更有爱心，并做每个字符串模糊匹配。

来源

2010-05-27 17:46:15

您可以修改Levenshtein算法来比较单词而不是字符。这不是一个非常复杂的算法，并且可以在线使用多种语言。

Levenshtein通过比较两个字符数组来工作。没有理由相同的逻辑不能应用于两个字符串数组。

来源

2010-05-27 18:02:39

我之前用C＃做过这个，我以前的问题是here。有兴趣的初学者算法，你可以很容易地将其转换为Python。

想法，你应该用写你自己的的算法是这样的：

与原来的“标题”列表（要匹配文字/句子）。

每个标题项目在单词/句子上应该具有最小的匹配分数，并忽略标题以及标题。

您还应该拥有全局最小匹配的最终结果百分比。

你应该计算每个单词Levenshtein距离。

您应该增加总重量匹配的话，如果在同一顺序去（敏捷的棕色VS敏捷的棕色，应该有明确更高的权重比棕色快与棕色快。）

来源

2010-05-27 18:07:31

取看看这个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 website

and Github repo

来源

2011-07-09 19:28:58 acslater00

您可以从https://github.com/frazenshtein/fastcd/blob/master/search.py尝试FuzzySearchEngine。

此模糊搜索仅支持搜索单词，并且对于单词有一个固定的允许误差（只有一个替换或两个相邻字符的换位）。

但是，例如你可以尝试这样的：

import search 

string = "Chapter I. The quick brown fox jumped over the lazy dog." 
substr = "the qiuck broqn fox." 

def fuzzy_search_for_sentences(substr, string): 
    start = None 
    pos = 0 
    for word in substr.split(" "): 
     if not word: 
      continue 
     match = search.FuzzySearchEngine(word).search(string, pos=pos) 
     if not match: 
      return None 
     if start is None: 
      start = match.start() 
     pos = match.end() 
    return start 

print(fuzzy_search_for_sentences(substr, string))

11将被打印

来源

2015-04-24 11:05:24

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

回答

相关问题