找到两个字符串之间的相似度度量
- 2024-12-11 08:48:00
- admin 原创
- 180
问题描述：
在 Python 中如何获取一个字符串与另一个字符串相似的概率？
我想要获得一个十进制值，如 0.9（表示 90%）等。最好使用标准 Python 和库。
例如
similar("Apple","Appel") #would have a high prob.
similar("Apple","Mango") #would have a lower prob.
解决方案 1：
有一个内置的。
from difflib import SequenceMatcher
def similar(a, b):
return SequenceMatcher(None, a, b).ratio()
使用它：
>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0
解决方案 2：
解决方案 #1：Python 内置
使用difflib中的SequenceMatcher
优点：内置 Python 库，不需要额外的包。
缺点：太有限，还有很多其他好的字符串相似度算法。
例子：
>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75
解决方案 #2：水母库
这是一个非常好的库，覆盖范围广，问题少。它支持：
编辑距离
Damerau-编辑距离
哈罗距离
Jaro-Winkler 距离
比赛评分方法比较
汉明距离
优点：易于使用、支持多种算法、经过测试。
缺点：不是内置库。
例子：
>>> 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
解决方案 3：
我想也许你正在寻找一种描述字符串之间距离的算法。以下是一些你可以参考的内容：
汉明距离
编辑距离
Damerau–编辑距离
Jaro–Winkler 距离
解决方案 4：
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
解决方案 5：
您可以创建如下函数：
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))
解决方案 6：
注意，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
解决方案 7：
包distance包括 Levenshtein distance：
import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3
解决方案 8：
您可以在以下链接下找到大多数文本相似度方法及其计算方法：https://github.com/luozhouyang/python-string-similarity#python-string-similarity
这里有一些例子；
规范化、度量、相似性和距离
（规范化）相似度和距离
公制距离
基于 Shingles (n-gram) 的相似度和距离
莱文斯坦
规范化编辑
加权编辑
达梅劳-莱文斯坦
最佳字符串对齐
贾罗-温克勒
最长公共子序列
度量最长公共子序列
N 元语法
基于 Shingle(n-gram) 的算法
Q-Gram
余弦相似度
杰卡德指数
Sorensen-Dice 系数
重叠系数（即 Szymkiewicz-Simpson）
解决方案 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
解决方案 10：
内置函数在处理大量输入时非常慢，下面介绍如何使用diff-match-patchSequenceMatcher来实现：
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
解决方案 11：
文本距离：
TextDistance – python 库，用于通过多种算法比较两个或多个序列之间的距离。它有Textdistance
30多种算法
纯python实现
简单使用
比较两个以上的序列
一些算法在一个类中有多个实现。
可选的 numpy 使用以实现最大速度。
例1：
import textdistance
textdistance.hamming('test', 'text')
输出：
1
例2：
import textdistance
textdistance.hamming.normalized_similarity('test', 'text')
输出：
0.75
谢谢，干杯！
解决方案 12：
如上所述，有许多指标可以定义字符串之间的相似性和距离。我将通过一个Jaccard similarity带有的示例Q-Grams和一个带有 的示例来给出我的看法edit distance。
图书馆
from nltk.metrics.distance import jaccard_distance
from nltk.util import ngrams
from nltk.metrics.distance import edit_distance
杰卡德相似度
1-jaccard_distance(set(ngrams('Apple', 2)), set(ngrams('Appel', 2)))
我们得到：
0.33333333333333337
对于Apple和Mango
1-jaccard_distance(set(ngrams('Apple', 2)), set(ngrams('Mango', 2)))
我们得到：
0.0
编辑距离
edit_distance('Apple', 'Appel')
我们得到：
2
最后，
edit_distance('Apple', 'Mango')
我们得到：
5
Q-Grams 的余弦相似度（q=2）
另一个解决方案是使用textdistance库。我将提供一个例子Cosine Similarity
import textdistance
1-textdistance.Cosine(qval=2).distance('Apple', 'Appel')
我们得到：
0.5
解决方案 13：
将 Spacy NLP 库添加到组合中；
@profile
def main():
str1= "Mar 31 09:08:41 The world is beautiful"
str2= "Mar 31 19:08:42 Beautiful is the world"
print("NLP Similarity=",nlp(str1).similarity(nlp(str2)))
print("Diff lib similarity",SequenceMatcher(None, str1, str2).ratio())
print("Jellyfish lib similarity",jellyfish.jaro_distance(str1, str2))
if __name__ == '__main__':
#python3 -m spacy download en_core_web_sm
#nlp = spacy.load("en_core_web_sm")
nlp = spacy.load("en_core_web_md")
main()
使用Robert Kern 的 line_profiler运行
kernprof -l -v ./python/loganalysis/testspacy.py
NLP Similarity= 0.9999999821467294
Diff lib similarity 0.5897435897435898
Jellyfish lib similarity 0.8561253561253562
然而时间在揭示
Function: main at line 32
Line # Hits Time Per Hit % Time Line Contents
==============================================================
32 @profile
33 def main():
34 1 1.0 1.0 0.0 str1= "Mar 31 09:08:41 The world is beautiful"
35 1 0.0 0.0 0.0 str2= "Mar 31 19:08:42 Beautiful is the world"
36 1 43248.0 43248.0 99.1 print("NLP Similarity=",nlp(str1).similarity(nlp(str2)))
37 1 375.0 375.0 0.9 print("Diff lib similarity",SequenceMatcher(None, str1, str2).ratio())
38 1 30.0 30.0 0.1 print("Jellyfish lib similarity",jellyfish.jaro_distance(str1, str2))
解决方案 14：
这是我的想法：
import string
def match(a,b):
a,b = a.lower(), b.lower()
error = 0
for i in string.ascii_lowercase:
error += abs(a.count(i) - b.count(i))
total = len(a) + len(b)
return (total-error)/total
if __name__ == "__main__":
print(match("pple inc", "Apple Inc."))
解决方案 15：
Python3.6+=
未导入任何库
在大多数情况下效果很好
在 Stack Overflow 中，当您尝试添加标签或发布问题时，它会显示所有相关内容。这非常方便，正是我正在寻找的算法。因此，我编写了一个查询集相似性过滤器。
def compare(qs, ip):
al = 2
v = 0
for ii, letter in enumerate(ip):
if letter == qs[ii]:
v += al
else:
ac = 0
for jj in range(al):
if ii - jj < 0 or ii + jj > len(qs) - 1:
break
elif letter == qs[ii - jj] or letter == qs[ii + jj]:
ac += jj
break
v += ac
return v
def getSimilarQuerySet(queryset, inp, length):
return [k for tt, (k, v) in enumerate(reversed(sorted({it: compare(it, inp) for it in queryset}.items(), key=lambda item: item[1])))][:length]
if __name__ == "__main__":
print(compare('apple', 'mongo'))
# 0
print(compare('apple', 'apple'))
# 10
print(compare('apple', 'appel'))
# 7
print(compare('dude', 'ud'))
# 1
print(compare('dude', 'du'))
# 4
print(compare('dude', 'dud'))
# 6
print(compare('apple', 'mongo'))
# 2
print(compare('apple', 'appel'))
# 8
print(getSimilarQuerySet(
[
"java",
"jquery",
"javascript",
"jude",
"aja",
],
"ja",
2,
))
# ['javascript', 'java']
解释
compare接受两个字符串并返回一个正整数。您可以编辑
al中的允许变量compare，它表示我们需要搜索的范围有多大。它的工作原理是这样的：迭代两个字符串，如果在相同的索引处找到相同的字符，则累加器将添加到最大值。然后，我们在 的索引范围内搜索allowed，如果匹配，则根据字母的距离将其添加到累加器中。（越远，越小）length指出您想要的结果中与输入字符串最相似的项目数。
解决方案 16：
为了我的目的，我有自己的方法，它比 difflib SequenceMatcher 的 quick_ratio() 快 2 倍，同时提供类似的结果。a 和 b 是字符串：
score = 0
for letters in enumerate(a):
score = score + b.count(letters[1])
