Python中的字符串相似度度量

Question

我想找到两个字符串之间的相似度。 en.wikipedia 上有一些例子。code.google上有一个Python实现的Levenshtein距离。
在以下限制条件下，是否有更好的算法（并且希望有一个Python库）：

0. 我想在字符串之间进行模糊匹配。例如，matches('Hello, All you people', 'hello, all You peopl') 应该返回True。
1. 假阴性是可以接受的，但假阳性除非极其罕见，否则不可接受。
2. 这是在非实时设置中完成的，因此速度不是（太）关键。
3. [编辑] 我正在比较多个单词的字符串。

除了Levenshtein距离（或Levenshtein比率）之外，对于我的情况，是否有更好的算法？

- agiliq

---

关于第二点：请阅读以下文章：http://en.wikipedia.org/wiki/Receiver_operating_characteristic。根据您的第二点，最佳的相似性度量是仅将相同字符串称为相似。超出此范围的任何不精确匹配都会产生误报。 - jilles de wit

嗯...那么我正在寻找近乎人类智能的无误差解决方案。例如，人类可以得出结论，Appel可能与Apple相同，但Ape不是。可能我的观点没有表达清楚。 - agiliq

(1) 即使完全匹配，"无误差"仍是不可能的。例如："apple"（水果）！="apple"（电脑等制造商）。
(2) 如果有“接近人类智能”的技术可用，它既不会出现在屏幕代码中，也不会免费提供。
(3) 考虑使用允许置换的方法——将"appel/apple"排名高于"ape/apple"和"ape/appel"。 - John Machin

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

- Nadia Alramli

Answer 2

在谢菲尔德大学有一个很棒的字符串相似度度量资源。它列出了各种度量标准（不仅仅是莱文斯坦距离），并提供了它们的开源实现。看起来其中许多指标应该很容易适应Python。

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

以下是列表的一部分：

• 汉明距离
• 莱文斯坦距离
• Needleman-Wunch距离或Seller算法
• 等等...

- ariddell

Answer 3

以下代码片段将计算两个字符串的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

- duhaime

---

当我运行这个程序时，出现了“IndexError: list index out of range”错误。为什么会出现这种情况？ - Feyzi Bagirov

@FeyziBagirov，你能否发布一个带有你的脚本和输入的Github Gist？ - duhaime

Answer 4

我建议使用Levenshtein距离或所谓的Damerau距离（考虑了交换位置），而不是difflib库，有两个原因：（1）可以使用“足够快”的动态规划算法和“飞快”的C代码（2）其行为被充分理解，例如Levenshtein满足三角不等式，因此可以在Burkhard-Keller树中使用。

阈值：您应该仅将距离<(1-X)*max(len(string1),len(string2))视为“正面”，并调整X（相似性因子）以适合自己。选择X的一种方法是获取匹配样本，为每个计算X，忽略X<0.8或0.9的情况，然后按降序排列剩余项的X，眼球观察并插入正确结果，并针对各种X水平计算某些错误成本度量。

N.B.您的猿/苹果示例距离为2，因此X为0.6……如果我迫切寻找某物并且有很高的假阴性惩罚，我只会使用低至0.75的阈值。

- John Machin

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。

- Tzury Bar Yochay

---

谢谢。这可能会给我一些好的想法，但不是我正在寻找的内容。get_close_matches('appel', ['ape', 'peach', 'puppy']) 会返回猿猴。我可以设置截断值，但从一些快速实验来看，误报太常见了。 - agiliq

Answer 6

我知道这不一样，但你可以调整比率来过滤掉不够相似的字符串，并返回与你所寻找的字符串最接近的匹配项。也许你会更感兴趣的是语义相似度度量方法。

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/

导入Levenshtein

- John

Answer 7

为了避免误判，可以使用库 ngramratio 中的方法 nratio()。

>>> pip install ngramratio

>>> from ngramratio import ngramratio
>>> SequenceMatcherExtended = ngramratio.SequenceMatcherExtended

>>> a = 'Hi there'
>>> b = 'Hit here'

>>> seq=SequenceMatcherExtended(a=a.lower(), b=b.lower())

>>> seq.ratio()
>>> 0.875
>>> seq.nratio(1) #this replicates `seq.ratio`.
>>> 0.875

>>> seq.nratio(2)
>>> 0.75

>>> seq.nratio(3)
>>> 0.5

nratio(n)仅匹配长度 >= n 的n元组。

您可以选择一个值为n，比如n=2，并像Nadia在之前的回复中所做的那样创建一个布尔相似度函数。

def similar(seq1, seq2):
    return SequenceMatcherExtended(a=seq1.lower(), b=seq2.lower()).nratio(2) > 0.8

>>> similar(a, b)
False
>>> similar('Hi there', 'Hi ther')
True

- giacomo