232

我正在寻找一个可以进行简单模糊字符串比较的 Python 模块。具体来说,我想要字符串相似程度的百分比。我知道这可能是主观的,所以我希望找到一个可以进行位置比较以及最长相似字符串匹配等的库。

基本上,我希望找到足够简单的东西来产生一个百分比,同时仍然足够可配置,我可以指定要执行的比较类型。

4

12 回答 12

249

difflib可以做到。

文档中的示例:

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

看看这个。它还有其他功能可以帮助您构建自定义内容。

于 2009-03-25T16:34:09.017 回答
164

Levenshtein Python 扩展和 C 库。

https://github.com/ztane/python-Levenshtein/

Levenshtein Python C 扩展模块包含用于快速计算 - Levenshtein(编辑)距离和编辑操作 - 字符串相似度 - 近似中值字符串,通常是字符串平均 - 字符串序列和集合相似度的函数 它支持普通字符串和 Unicode 字符串。

$ pip install python-levenshtein
...
$ python
>>> import Levenshtein
>>> help(Levenshtein.ratio)
ratio(...)
    Compute similarity of two strings.

    ratio(string1, string2)

    The similarity is a number between 0 and 1, it's usually equal or
    somewhat higher than difflib.SequenceMatcher.ratio(), becuase it's
    based on real minimal edit distance.

    Examples:
    >>> ratio('Hello world!', 'Holly grail!')
    0.58333333333333337
    >>> ratio('Brian', 'Jesus')
    0.0

>>> help(Levenshtein.distance)
distance(...)
    Compute absolute Levenshtein distance of two strings.

    distance(string1, string2)

    Examples (it's hard to spell Levenshtein correctly):
    >>> distance('Levenshtein', 'Lenvinsten')
    4
    >>> distance('Levenshtein', 'Levensthein')
    2
    >>> distance('Levenshtein', 'Levenshten')
    1
    >>> distance('Levenshtein', 'Levenshtein')
    0
于 2009-03-26T07:18:51.370 回答
70

正如nosklo所说,使用 Python 标准库中的difflib模块。

difflib 模块可以使用SequenceMatcher()对象的ratio()方法返回序列相似性的度量。相似度以 0.0 到 1.0 范围内的浮点数形式返回。

>>> import difflib

>>> difflib.SequenceMatcher(None, 'abcde', 'abcde').ratio()
1.0

>>> difflib.SequenceMatcher(None, 'abcde', 'zbcde').ratio()
0.80000000000000004

>>> difflib.SequenceMatcher(None, 'abcde', 'zyzzy').ratio()
0.0
于 2010-03-10T17:03:57.327 回答
39

Jellyfish是一个 Python 模块,它支持许多字符串比较指标,包括语音匹配。与 Jellyfish 的实现相比,Levenstein 编辑距离的纯 Python 实现相当慢。

示例用法:

import jellyfish

>>> jellyfish.levenshtein_distance('jellyfish', 'smellyfish')
2 
>>> jellyfish.jaro_distance('jellyfish', 'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance('jellyfish', 'jellyfihs')
1
>>> jellyfish.metaphone('Jellyfish')
'JLFX'
>>> jellyfish.soundex('Jellyfish')
'J412'
>>> jellyfish.nysiis('Jellyfish')
'JALYF'
>>> jellyfish.match_rating_codex('Jellyfish')
'JLLFSH'`
于 2011-12-03T19:20:23.713 回答
23

我喜欢nosklo 的回答;另一种方法是Damerau-Levenshtein 距离

“在信息论和计算机科学中,Damerau-Levenshtein 距离是两个字符串之间的‘距离’(字符串度量),即有限的符号序列,通过计算将一个字符串转换为另一个字符串所需的最小操作数给出,其中操作被定义为单个字符的插入、删除或替换,或两个字符的转置。”

Wikibooks中的 Python 实现:

def lev(a, b):
    if not a: return len(b)
    if not b: return len(a)
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), \
    lev(a[1:], b)+1, lev(a, b[1:])+1)

更多来自 Wikibooks,这为您提供了最长公共子字符串 (LCS)的长度:

def LCSubstr_len(S, T):
    m = len(S); n = len(T)
    L = [[0] * (n+1) for i in xrange(m+1)]
    lcs = 0
    for i in xrange(m):
        for j in xrange(n):
            if S[i] == T[j]:
                L[i+1][j+1] = L[i][j] + 1
                lcs = max(lcs, L[i+1][j+1])
    return lcs
于 2009-03-25T16:46:32.327 回答
18

还有 Google 自己的google-diff-match-patch(“目前在 Java、JavaScript、C++ 和 Python 中可用”)。

(不能评论,因为我自己只用过python的difflib)

于 2009-03-25T17:47:33.910 回答
8

另一种选择是使用最近发布的包FuzzyWuzzy。该包支持的各种功能也在这篇博文中进行了描述。

于 2011-08-29T18:41:14.373 回答
5

我正在使用双重变音器,它就像一个魅力。

一个例子:

>>> dm(u'aubrey')
('APR', '')
>>> dm(u'richard')
('RXRT', 'RKRT')
>>> dm(u'katherine') == dm(u'catherine')
True

更新:水母也有。属于语音编码。

于 2011-12-16T06:30:54.423 回答
4

我一直在使用 Seat Geek 的 Fuzzy Wuzzy 并取得了巨大的成功。

https://github.com/seatgeek/fuzzywuzzy

具体来说就是token set ratio函数...

他们还写了一篇关于模糊字符串匹配过程的精彩文章:

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

于 2013-08-14T03:07:38.193 回答
3

这是一个 python 脚本,用于计算两个单词中最长的公共子字符串(可能需要调整以适用于多单词短语):

def lcs(word1, word2):

    w1 = set(word1[i:j] for i in range(0, len(word1))
             for j in range(1, len(word1) + 1))

    w2 = set(word2[i:j] for i in range(0, len(word2))
             for j in range(1, len(word2) + 1))

    common_subs = w1.intersection(w2)

    sorted_cmn_subs = sorted([
        (len(str), str) for str in list(common_subs)
        ])

    return sorted_cmn_subs.pop()[1]
于 2009-04-20T16:32:11.190 回答
3

这是使用 Charicar 的 simhash 的方法,这也适用于长文档,当您更改文档中的单词顺序时,它也会检测到 100% 的相似性

http://blog.simpliplant.eu/calculating-similarity-between-text-strings-in-python/

于 2011-11-19T11:21:00.343 回答
2

看看Fuzzy模块。它具有用于 soundex、NYSIIS 和双变音器的快速(用 C 语言编写)算法。

一个很好的介绍可以在:http ://www.informit.com/articles/article.aspx?p=1848528

于 2012-04-03T12:12:54.937 回答