54

我想找到两个字符串之间的字符串相似性。此页面包含其中一些示例。Python 具有Levenshtein 算法的实现。在这些限制下，是否有更好的算法（希望是 python 库）。

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

除了 Levenshtein 距离（或 Levenshtein 比率）之外的其他东西会是我的情况更好的算法吗？

4

6 回答 6

96

我意识到这不是一回事，但这已经足够接近了：

>>> 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
于 2009-09-24T13:10:55.380 回答
25

谢菲尔德大学有一个很好的字符串相似度指标资源。它有一个各种指标的列表（不仅仅是 Levenshtein），并且有它们的开源实现。看起来它们中的许多应该很容易适应 Python。

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

这是列表的一部分：

  • 汉明距离
  • 莱文斯坦距离
  • Needleman-Wunch 距离或卖方算法
  • 还有很多...
于 2009-09-24T12:13:28.340 回答
18

此代码段将计算两个字符串的 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
于 2015-07-06T00:51:12.103 回答
9

我会使用 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 水平的错误成本度量。

注意您的猿/苹果示例的距离为 2，因此 X 为 0.6 ...如果我拼命寻找某些东西并且有很高的假阴性惩罚，我只会使用低至 0.75 的阈值

于 2009-09-24T14:41:31.583 回答
6

你是这个意思吗？

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

于 2009-09-24T11:46:47.830 回答
2

我知道这不一样，但您可以调整比率以过滤掉不够相似的字符串，并返回与您正在查找的字符串最接近的匹配项。

也许您会对语义相似度指标更感兴趣。

https://www.google.com/search?client=ubuntu&channel=fs&q=semantic+similarity+string+match&ie=utf-8&oe=utf-8

我意识到您说速度不是问题，但是如果您要为算法处理大量字符串，则以下内容非常有帮助。

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/

进口文史丹

于 2014-11-12T19:28:21.573 回答