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

Question

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

我想获得像0.9(意味着90%)等十进制值.最好使用标准的Python和库.

例如

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

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

Answer 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

Answer 2

我想也许你正在寻找一种描述字符串之间距离的算法.您可以参考以下内容:

1. 汉明距离
2. Levenshtein距离
3. Damerau-Levenshtein距离
4. Jaro-Winkler的距离

Answer 3

解决方案#1:Python内置

使用SequenceMatcher从difflib

专业:本机python库,无需额外包.
缺点:太有限了,还有很多其他优秀的字符串相似算法.

例如:

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

解决方案#2:水母图书馆

它是一个非常好的图书馆,覆盖面很好,问题很少.它支持:
- Levenshtein距离
- Damerau-Levenshtein距离
- Jaro距离
- 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

Answer 4

Fuzzy Wuzzy是一个在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

Answer 5

您可以在此链接下找到大多数文本相似度方法及其计算方法： https: //github.com/luozhouyang/python-string-similarity#python-string-similarity 这里有一些示例；

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

• （标准化）相似度和距离

• 公制距离

• 基于 Shingles (n-gram) 的相似度和距离
• 编辑
• 标准化编辑
• 加权编辑
• 达默劳-莱文施泰因
• 最佳字符串对齐
• 贾罗-温克勒
• 最长公共子序列
• 度量最长公共子序列
• N-Gram
• 基于Shingle(n-gram)的算法
• Q-Gram
• 余弦相似度
• 杰卡德指数
• 索伦森-戴斯系数
• 重叠系数（即Szymkiewicz-Simpson）

Answer 6

您可以创建一个类似的函数:

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

Answer 7

包裹距离包括Levenshtein距离:

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

Answer 8

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

Answer 9

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

Answer 10

文字距离：

\n

TextDistance \xe2\x80\x93 python 库，用于通过多种算法比较两个或多个序列之间的距离。它有文本距离

\n

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

\n

示例1：

\n

import textdistance\ntextdistance.hamming(\'test\', \'text\')\n

\n

输出：

\n

1

\n

示例2：

\n

import textdistance\n\ntextdistance.hamming.normalized_similarity(\'test\', \'text\')\n

\n

输出：

\n

0.75

\n

谢谢并干杯！

\n

Answer 11

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