Python中的字符串相似度度量

Question

我想找出两个字符串之间的相似度。维基百科上有一些相关的例子。code.google上有一个关于Levenshtein距离的Python实现。
我想知道在以下条件下，是否有更好的算法（希望还有Python库）：

0. 我想进行模糊匹配，比如说matches('Hello, All you people', 'hello, all You peopl')应该返回True。
1. 可以接受假阴性，但假阳性在极少数情况下是不能接受的。
2. 这个过程不是实时的，所以速度不是太大的问题。
3. [编辑] 我比较的是多词字符串。

除了Levenshtein距离（或Levenshtein比率），还有没有更适合我情况的算法呢？

Answer 1

这个代码片段会计算两个字符串之间的 difflib、Levenshtein、Sørensen 和 Jaccard 相似度值。在下面的代码中，我正在遍历一个 TSV 文件，其中我们关注的字符串位于 TSV 的 [3] 和 [4] 列。你可以通过运行 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 2

我知道这不是完全一样的东西，但这个差不多可以：

>>> 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 3

谢菲尔德大学有一个很棒的资源，专门讲字符串相似度的测量方法。里面列出了各种各样的测量标准（不仅仅是莱文斯坦距离），而且还有这些方法的开源实现。看起来很多方法都可以很容易地用Python来实现。

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

这里有一些列出的测量方法：

• 汉明距离
• 莱文斯坦距离
• 尼德尔曼-温奇距离或塞勒斯算法
• 还有很多其他的...