Python中的string相似性度量
我想find两个string之间的string相似性。 这个页面有一些例子。 Python有一个Levenshteinalgorithm的实现 。 有没有更好的algorithm，（希望是一个Python库），在这些限制下。
- 我想做string之间的模糊匹配。 例如匹配（'你好，你所有的人'，'你好，所有你peopl'）应该返回True
- 假阴性是可以接受的，假阳性，除极less数情况外都不是。
- 这是在非实时设置下完成的，因此速度不是很关心。
- [编辑]我正在比较多个string。
除了Levenshtein距离（或Levenshtein比率）之外，对于我的情况会是更好的algorithm吗？
谢菲尔德大学的string相似性度量有一个很好的资源。 它有一个列表（不仅仅是Levenshtein），还有它们的开源实现。 看起来像很多人应该很容易适应Python。
http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html
这里有一些名单：
- 海明距离
- Levenshtein距离
- Needleman-Wunch距离或卖家algorithm
- 还有很多…
我意识到这不是一回事，但这已经足够接近了：
>>> 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
这段代码将计算两个string的difflib，Levenshtein，Sørensen和Jaccard相似度值。 在下面的代码片段中，我重复了一个tsv，其中感兴趣的string占据了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
我会使用Levenshtein距离，或所谓的Damerau距离（考虑到换位），而不是difflib的东西，原因有两个：（1）“足够快”（dynamic编程algorithm）和“whoooosh”（bit-bashing）C代码是可用的和（2）很好理解的行为，例如Levenshtein满足三angular不等式，因此可以在例如Burkhard-Keller树中使用。
阈值：只有距离<（1 – X）* max（len（string1），len（string2））和调整X（相似因子）才适合自己的情况， selectX的一种方法是获得匹配样本，为每个X计算X，忽略X <0.8或0.9的情况，然后按X的降序对余数进行sorting，并将它们眼球对准并插入正确的结果并计算一些X的各种级别的错误代价度量。
NB你的猿/苹果的例子有距离2，所以X是0.6 …我只会使用一个低至0.75的阈值，如果我拼命寻找的东西，并有一个很高的假阴性罚款
你是这个意思吗？
>>> 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
我知道这是不一样的，但你可以调整比率过滤掉不够相似的string，并返回最接近匹配的string，你正在寻找。
也许你会对语义相似性度量更感兴趣。
我意识到你说速度是不是一个问题，但如果你正在处理你的algorithm很多string下面是非常有用的。
def spellcheck(self, sentence): #return ' '.join([difflib.get_close_matches(word, wordlist,1 , 0)[0] for word in sentence.split()]) return ' '.join( [ sorted( { Levenshtein.ratio(x, word):x for x in wordlist }.items(), reverse=True)[0][1] for word in sentence.split() ] )
它比difflib快大约20倍。
https://pypi.python.org/pypi/python-Levenshtein/
importLevenshtein
