找出两个字符串之间的相似度度量

如何在Python中获得一个字符串与另一个字符串相似的概率?

我想要得到一个十进制值，比如0.9(意思是90%)等等。最好是标准的Python和库。

如。

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


similar("Apple","Mango") #would have a lower prob.
367005 次浏览
小开

你可以创建这样一个函数:

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))
小开
最佳答案

这是内置的。

from difflib import SequenceMatcher


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

使用它:

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

我想你们可能在寻找一种描述字符串之间距离的算法。这里有一些你可以参考的:

  1. 汉明距离
  2. Levenshtein distance
  3. Damerau-Levenshtein距离
  4. Jaro-Winkler距离
小开

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

包距离包含Levenshtein距离:

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

解决方案#1:内置Python

使用difflib中的SequenceMatcher

< p > 优点: 本机python库，不需要额外的包 缺点:太有限了，有很多其他的字符串相似度的好算法。

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

解决方案#2:水母库

这是一个非常好的图书馆，覆盖面很广，问题很少。 它支持:< br > - Levenshtein Distance
- Damerau-Levenshtein距离
- Jaro Distance
- Jaro-Winkler距离
- Match Rating Approach Comparison
-汉明距离

< p > 优点: 易于使用，支持的算法的色域，测试。
缺点:不是本机库。

例子:

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

内置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
小开

注意，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
小开

你可以在这个链接下找到大多数文本相似度方法及其计算方法:https://github.com/luozhouyang/python-string-similarity#python-string-similarity

  • 归一化，度量，相似度和距离

  • (归一化)相似度和距离

  • 距离度量

  • 基于相似度和距离的带状(n-gram)
  • Levenshtein
  • 规范化Levenshtein
  • 加权Levenshtein
  • Damerau-Levenshtein
  • 最佳字符串对齐
  • Jaro-Winkler
  • 最长公共子序列
  • 度量最长公共子序列
  • 语法
  • 基于瓦(n-gram)的算法
  • Q-Gram
  • 余弦相似度
  • Jaccard指数
  • Sorensen-Dice系数
  • 重叠系数(即Szymkiewicz-Simpson)
小开

如上所述，有许多指标可以定义字符串之间的相似性和距离。我将通过展示一个带有Q-Grams的Jaccard similarity示例和一个带有edit distance的示例来给出我的5美分。

库

from nltk.metrics.distance import jaccard_distance
from nltk.util import ngrams
from nltk.metrics.distance  import edit_distance

Jaccard相似

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

Textdistance:

TextDistance - python库，用于通过多种算法比较两个或多个序列之间的距离。它有Textdistance

  • 30 +算法
  • 纯python实现
  • 简单的使用
  • 两个以上的序列比较
  • 有些算法在一个类中有多个实现。
  • 可选的numpy使用最高速度。

例二:

import textdistance
textdistance.hamming('test', 'text')

输出:

1

Example2:

import textdistance


textdistance.hamming.normalized_similarity('test', 'text')

输出:

０．７５

谢谢，干杯!

小开

这是我想到的:

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."))
小开

BLEUscore

BLEU，或双语评估替补，是一个用于比较的分数

.文本到一个或多个参考译文的候选翻译 完全匹配的结果是1.0，而完全不匹配的结果是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
小开
  • < h3 > Python3.6 + =

  • 没有导入库

  • 在大多数情况下工作良好

在堆栈溢出，当你试图添加一个标签或发布一个问题，它会带来所有相关的东西。这是如此方便，正是我正在寻找的算法。因此，我编写了一个查询集相似度过滤器。

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接受两个字符串并返回一个正整数。
  • 你可以在compare中编辑al allowed变量，它表示我们需要搜索的范围有多大。它的工作原理是这样的:迭代两个字符串，如果在相同的下标处找到相同的字符，那么累加器将添加到最大的值。然后，我们在allowed的索引范围内搜索，如果匹配，则根据字母的距离添加到累加器中。(越远越小)
  • length表示你想要多少项作为结果，这是最类似于输入字符串。
小开

还添加了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))

提交答案