python计算字符串相似度总结
1、距离计算
包的安装：
pip install python-Levenshtein
levenshtein
编辑距离(Edit Distance)，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
接下来重点介绍下保重几个方法的作用：
Levenshtein.distance(str1, str2)
计算编辑距离(也称Levenshtein距离)。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入、删除、替换。算法实现：动态规划。
Levenshtein.hamming(str1, str2)
计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应位置上不同字符的个数。
Levenshtein.ratio(str1, str2)
计算莱文斯坦比。计算公式 r = (sum – ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是类编辑距离。注意这里是类编辑距离，在类编辑距离中删除、插入依然+1，但是替换+2。
Levenshtein.jaro(s1, s2)
计算jaro距离，Jaro Distance据说是用来判定健康记录上两个名字是否相同，也有说是是用于人口普查，我们先来看一下Jaro Distance的定义。
两个给定字符串S1和S2的Jaro Distance为：
Levenshtein.jaro_winkler(s1, s2)
1.1实际应用
def gen_title(word,relates:set):
rsw = ''
presimi = 0.1
for rs in relates:
simi = Levenshtein.jaro_winkler(word,rs)
print(f'{word}--{rs}-->与其相识度：{simi}')
if simi < 0.6 or simi >0.95:
continue
if simi > presimi:
rsw = rs
presimi = simi
if not rsw:
return word
return f'{word}_{rsw}'2、余弦相似度
余弦相似度可用来计算两个向量的相似程度
对于如何计算两个向量的相似程度问题，可以把这它们想象成空间中的两条线段，都是从原点([0, 0, ...])出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合;如果夹角为90度，意味着形成直角，方向完全不相似;如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。
2.1 实际应用
# -*- coding: utf-8 -*-
"""
余弦相似性算法beta2.0(本次修改主要是通过只计算主干词语来提高相关性，去掉无用的停止词)
用于计算两个文本字符串的相似度
需要用到结巴分词, 算法耗时取决于字典(或者缓存字典)的加载时间
因此字典不宜过大，使用默认的字典就可以了
因为不需要进行精确的分词只是做相似度计算而已
如果需要使用自定义词典，那么可以在分词之前使用
jieba.load_userdict(ditname) 加入自定义词典
如果要屏蔽掉烦人的, 结巴的初始化输出显示:
Building prefix dict from the default dictionary ...
Loading model from cache /var/folders/h9/5172d1757k90s7p3ngzzgllm0000gn/T/jieba.cache
Loading model cost 0.410 seconds.
Prefix dict has been built succesfully.
这些东西, 那么可以打开jieba的__init__.py 文件删除掉对应的信息或者将输出写入文件等(自行处理)
算法参考文档: http://baike.baidu.com/item/%E4%BD%99%E5%BC%A6%E7%9B%B8%E4%BC%BC%E5%BA%A6
作者: brooks
MQQ: 76231607
"""
import jieba
from jieba import posseg
import math
import time
jieba.initialize()
def simicos(str1, str2):
# 对两个要计算的字符串进行分词, 使用隐马尔科夫模型(也可不用)
# 由于不同的分词算法, 所以分出来的结果可能不一样
# 也会导致相似度会有所误差, 但是一般影响不大
cut_str1 = [w for w, t in posseg.lcut(str1) if 'n' in t or 'v' in t]
cut_str2 = [w for w, t in posseg.lcut(str2) if 'n' in t or 'v' in t]
# 列出所有词
all_words = set(cut_str1 + cut_str2)
# 计算词频
freq_str1 = [cut_str1.count(x) for x in all_words]
freq_str2 = [cut_str2.count(x) for x in all_words]
# 计算相似度
sum_all = sum(map(lambda z, y: z * y, freq_str1, freq_str2))
sqrt_str1 = math.sqrt(sum(x ** 2 for x in freq_str1))
sqrt_str2 = math.sqrt(sum(x ** 2 for x in freq_str2))
try:
return sum_all / (sqrt_str1 * sqrt_str2)
except ZeroDivisionError:
return 0.0
if __name__ == '__main__':
case1 = "水仙不开花的歇后语是什么"
case2 = "水仙不开花用歇后语怎么说"
start = time.time()
similarity = simicos(case1, case2)
end = time.time()
print("耗时: %.3fs" % (end - start))
print("相似度: %.1f%%" % (similarity * 100))3.基于集合交集算法计算
集合交集算法是一个简单的逻辑：
1. 先分别对两个字符串进行分词
2. 进行求交集
3. 计算交集的部分与原来关键词的占比，这个占比就是相似度
3.1 实际应用
# -*- coding: utf-8 -*-
"""
基于集合的方式来计算相似度
作者：brooks
"""
import time
from jieba.analyse import tfidf
import jieba
jieba.initialize()
def setsimilarity(str1, str2):
# 1. 先分别对两个字符串进行分词
str1_cut = jieba.lcut(str1)
str2_cut = jieba.lcut(str2)
# 2. 进行求交集
set_str1 = set(str1_cut)
set_str2 = set(str2_cut)
union_words = set_str1 & set_str2
# 3. 计算交集的部分与原来关键词的占比，这个占比就是相似度
return len(union_words) / len(set_str1)
if __name__ == '__main__':
case1 = "无货源电商怎么做,靠谱吗"
case2 = "购买淘宝店铺靠不靠谱"
start = time.time()
similarity = setsimilarity(case1, case2)
end = time.time()
print(tfidf(case1))
print(tfidf(case2))
print("耗时: %.3fs" % (end - start))
print("相似度: %.1f%%" % (similarity * 100))总结：
三个算法各有优劣，推荐使用：余弦算法、集合相似度算法，编辑距离效果略差，主要是关键词长短不一，顺序改变的话，编辑距离的结果差别就会很大。
