Python中的字符串相似性度量

Question

我想找到两个字符串之间的字符串相似性.此页面包含其中一些示例.Python有Levenshtein算法的实现.在这些约束下,是否有更好的算法(并且希望是python库).

1. 我想在字符串之间进行模糊匹配.例如匹配('Hello,All you people','hello,all you peopl')应该返回True
2. 假阴性是可以接受的,假阳性,除非极少数情况下不是.
3. 这是在非实时设置中完成的,因此速度不是(非常)关注的.
4. [编辑]我正在比较多字串.

除了Levenshtein距离(或Levenshtein比率)以外的其他东西对我的情况更好吗？

Answer 1

我意识到这不是一回事,但这已足够接近了:

>>> import difflib
>>> a = 'Hello, All you people'
>>> b = 'hello, all You peopl'
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower())
>>> seq.ratio()
0.97560975609756095

你可以将它作为一个功能

def similar(seq1, seq2):
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9

>>> similar(a, b)
True
>>> similar('Hello, world', 'Hi, world')
False

Answer 2

谢菲尔德大学有很好的字符串相似性指标资源.它有各种指标列表(不仅仅是Levenshtein),并且有开源实现.看起来很多应该很容易适应Python.

http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

这里有一些清单:

• 汉明距离
• Levenshtein距离
• Needleman-Wunch距离或卖家算法
• 还有很多...

Answer 3

此片段将计算两个字符串的difflib,Levenshtein,Sørensen和Jaccard相似度值.在下面的代码片段中,我正在迭代一个tsv,其中感兴趣的字符串占据了列[3]和[4]tsv.(pip install python-Levenshtein和pip install distance):

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

Answer 4

我会使用Levenshtein距离,或所谓的Damerau距离(考虑转换)而不是difflib的东西有两个原因(1)"足够快"(动态编程算法)和"whoooosh"(bit-bashing)C代码是可用的和(2)易于理解的行为,例如Levenshtein满足三角不等式,因此可以用于例如Burkhard-Keller树.

阈值:你应该只将距离<(1 - X)*max(len(string1),len(string2))和调整X(相似因子)的情况视为"正面".选择X的一种方法是获取匹配样本,计算每个匹配的X,忽略X <0.8或0.9的情况,然后按X的降序对剩余部分进行排序并对其进行眼球并插入正确的结果并计算一些各种级别的X的错误成本衡量标准.

NB你的猿/苹果例子的距离是2,所以X是0.6 ......如果我拼命寻找某些东西并且假阴性惩罚很高,我只会使用低至0.75的阈值

Answer 5

你是这个意思吗？

>>> 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']

看看http://docs.python.org/library/difflib.html#difflib.get_close_matches