寻找两个字符串之间的相似度指标。

Question

寻找两个字符串之间的相似度指标。

474

如何在Python中获得字符串相似度的概率？

我想要一个十进制值，如0.9（表示90%），最好使用标准Python和库。

例如：

similar("Apple","Appel") #would have a high prob.

similar("Apple","Mango") #would have a lower prob.

- tenstar

12

我认为“概率”可能不是这里恰当的术语。无论如何，请参见https://dev59.com/GnRB5IYBdhLWcg3wQFLu。 - NPE

5

你要找的词是“比率”，而不是“概率”。 - Inbar Rose

3

请查看汉明距离。 - Diana

5

短语是“相似度量”，但有多个相似度量（Jaccard，Cosine，Hamming，Levenshein等），因此您需要指定哪一个。具体而言，您想要字符串之间的相似度量; @hbprotoss列出了几个。 - smci

我喜欢来自https://dev59.com/03RB5IYBdhLWcg3wWF8H的“bigrams”。 - MarkHu

16个回答

113

解决方案 #1：Python内置

使用SequenceMatcher来自difflib

优点：内置的Python库，无需额外安装包。
缺点：太过有限，还有许多其他适用于字符串相似度的好算法。

示例：

>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75

解决方案 #2: jellyfish 库

这是一个非常好的库，覆盖面广且问题很少。它支持以下功能：

Levenshtein 距离
Damerau-Levenshtein 距离
Jaro 距离
Jaro-Winkler 距离
Match Rating Approach 比较
Hamming 距离

优点：易于使用，支持多种算法，经过测试。
缺点：不是内置库。

示例：

>>> import jellyfish
>>> jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')
2
>>> jellyfish.jaro_distance(u'jellyfish', u'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance(u'jellyfish', u'jellyfihs')
1

- Iman Mirzadeh

好的答案，jellyfish 很棒。截至今天，jellyfish 使用本地库（具有纯 Python 回退）。 - Kevin Smyth

82

我认为您可能正在寻找描述字符串之间距离的算法。以下是您可以参考的一些算法：

- hbprotoss

53

TheFuzz是一个用Python实现Levenshtein距离的包, 并提供了一些辅助函数，以帮助在某些情况下您可能希望将两个不同的字符串视为相同。例如：

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    91
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100

- BLT

2

更新的链接：https://github.com/seatgeek/thefuzz - Ahmed Soliman

已更新链接和包名，谢谢。 - BLT

"TheFuzz" 真是太棒了！它使用非常强大的字符嵌入来计算向量距离。它还具有传统的字符串方法，但是对于像嵌入记录之间的余弦相似度这样的操作，它可以节省您大量的时间 :) - rjurney

19

您可以创建如下函数:

def similar(w1, w2):
    w1 = w1 + ' ' * (len(w2) - len(w1))
    w2 = w2 + ' ' * (len(w1) - len(w2))
    return sum(1 if i == j else 0 for i, j in zip(w1, w2)) / float(len(w1))

- Saullo G. P. Castro

但是，similar('appel', 'apple')比similar('appel', 'ape')更高。 - tenstar

1

您的函数将比较给定字符串与其他字符串。我想要一种返回相似性比例最高的字符串的方法。 - answerSeeker

1

@SaulloCastro，现在if self.similar(search_string, item.text()) > 0.80:可以工作了。谢谢。 - answerSeeker

16

请注意，difflib.SequenceMatcher 仅仅找到最长连续匹配的子序列，这通常不是所需的结果，举个例子：

>>> a1 = "Apple"
>>> a2 = "Appel"
>>> a1 *= 50
>>> a2 *= 50
>>> SequenceMatcher(None, a1, a2).ratio()
0.012  # very low
>>> SequenceMatcher(None, a1, a2).get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=250, b=250, size=0)]  # only the first block is recorded

在生物信息学中，找到两个字符串之间的相似性与成对序列比对的概念密切相关。为此，有许多专用库可供使用，包括biopython。以下示例实现了Needleman Wunsch算法：

>>> from Bio.Align import PairwiseAligner
>>> aligner = PairwiseAligner()
>>> aligner.score(a1, a2)
200.0
>>> aligner.algorithm
'Needleman-Wunsch'

使用 Biopython 或其他生物信息学软件包比 Python 标准库中的任何部分都更加灵活，因为可以使用许多不同的评分方案和算法。此外，您实际上可以获取匹配序列以可视化发生的情况：

>>> alignment = next(aligner.align(a1, a2))
>>> alignment.score
200.0
>>> print(alignment)
Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-
|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-
App-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-el

- Chris_Rands

13

包 distance 包括 Levenshtein 距离：

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3

- Enrique Pérez Herrero

10

你可以在这个链接中找到大部分文本相似度方法及其计算方式：https://github.com/luozhouyang/python-string-similarity#python-string-similarity。以下是一些例子：

标准化、度量、相似度和距离
(标准化) 相似度和距离
度量距离
基于 Shingles (n-gram) 的相似度和距离
Levenshtein
标准化 Levenshtein
加权 Levenshtein
Damerau-Levenshtein
最优字符串对齐
Jaro-Winkler
最长公共子序列
度量最长公共子序列
N-Gram
基于 Shingle(n-gram) 的算法
Q-Gram
余弦相似度
Jaccard 系数
Sørensen-Dice 系数
重叠系数（即 Szymkiewicz-Simpson）

- Mike

9

BLEU评分

BLEU，即双语评估替补，是用于比较文本候选翻译和一个或多个参考翻译的评分。

完全匹配得分为1.0，而完全不匹配得分为0.0。

虽然最初是用于翻译领域，但它可以用来评估自然语言处理任务套件生成的文本。

代码：

import nltk
from nltk.translate import bleu
from nltk.translate.bleu_score import SmoothingFunction
smoothie = SmoothingFunction().method4

C1='Text'
C2='Best'

print('BLEUscore:',bleu([C1], C2, smoothing_function=smoothie))

例子：通过更新C1和C2。

C1='Test' C2='Test'

BLEUscore: 1.0

C1='Test' C2='Best'

BLEUscore: 0.2326589746035907

C1='Test' C2='Text'

BLEUscore: 0.2866227639866161

您还可以比较句子相似度：

C1='It is tough.' C2='It is rough.'

BLEUscore: 0.7348889200874658

C1='It is tough.' C2='It is tough.'

BLEUscore: 1.0

- Reema Q Khan

8

如果输入的内容很大，内置的SequenceMatcher速度非常慢，下面是如何使用diff-match-patch实现：

from diff_match_patch import diff_match_patch

def compute_similarity_and_diff(text1, text2):
    dmp = diff_match_patch()
    dmp.Diff_Timeout = 0.0
    diff = dmp.diff_main(text1, text2, False)

    # similarity
    common_text = sum([len(txt) for op, txt in diff if op == 0])
    text_length = max(len(text1), len(text2))
    sim = common_text / text_length

    return sim, diff

- damio

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Inbar Rose · Accepted Answer

848

有一个内置的。

from difflib import SequenceMatcher

def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

使用它：

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0

- Inbar Rose

73

请看这个很好的答案，比较了SequenceMatcher和python-Levenshtein模块。https://dev59.com/C2w15IYBdhLWcg3wT6H2 - ssoler

2

有趣的文章和工具：http://chairnerd.seatgeek.com/fuzzywuzzy-fuzzy-string-matching-in-python/ - DevLounge

11

我强烈推荐查看整个difflib文档 https://docs.python.org/2/library/difflib.html。其中有一个内置的`get_close_matches`方法，但我发现使用`sorted(... key=lambda x: difflib.SequenceMatcher(None, x, search).ratio(), ...)更可靠，它还可以自定义sorted(... .get_matching_blocks())[-1] > min_match`检查。 - ThorSummoner

3

@ThorSummoner 引起了对一个非常有用的函数(get_closest_matches)的关注。它是一个便利函数，可能正是你正在寻找的，也就是说请阅读文档！在我的特定应用程序中，我正在进行一些基本的错误检查/向用户提供错误输入的报告，并且这个答案允许我向他们报告潜在的匹配项以及“相似度”是多少。不过，如果你不需要显示相似度，请务必查看get_closest_matches。 - svenevs

这个完美地运行了。简单而有效。谢谢 :) - Karthic Srinivasan

显示剩余2条评论