Python文本相似性计算之编辑距离详解
作者:daisy 发布时间:2022-04-28 12:14:23
编辑距离
编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。
例如将kitten一字转成sitting:('kitten' 和 ‘sitting' 的编辑距离为3)
sitten (k→s)
sittin (e→i)
sitting (→g)
Python中的Levenshtein包可以方便的计算编辑距离
包的安装: pip install python-Levenshtein
我们来使用下:
# -*- coding:utf-8 -*-
import Levenshtein
texta = '艾伦 图灵传'
textb = '艾伦•图灵传'
print Levenshtein.distance(texta,textb)
上面的程序执行结果为3,但是只改了一个字符,为什么会发生这样的情况?
原因是Python将这两个字符串看成string类型,而在 string 类型中,默认的 utf-8 编码下,一个中文字符是用三个字节来表示的。
解决办法是将字符串转换成unicode格式,即可返回正确的结果1。
# -*- coding:utf-8 -*-
import Levenshtein
texta = u'艾伦 图灵传'
textb = u'艾伦•图灵传'
print Levenshtein.distance(texta,textb)
接下来重点介绍下保重几个方法的作用:
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为:
其中的m为s1, s2匹配的字符数,t是换位的数目。
两个分别来自S1和S2的字符如果相距不超过
时,我们就认为这两个字符串是匹配的;而这些相互匹配的字符则决定了换位的数目t,简单来说就是不同顺序的匹配字符的数目的一半即为换位的数目t。举例来说,MARTHA与MARHTA的字符都是匹配的,但是这些匹配的字符中,T和H要换位才能把MARTHA变为MARHTA,那么T和H就是不同的顺序的匹配字符,t=2/2=1
。
两个字符串的Jaro Distance即为:
Levenshtein.jaro_winkler(s1, s2)
计算Jaro–Winkler距离,而Jaro-Winkler则给予了起始部分就相同的字符串更高的分数,他定义了一个前缀p,给予两个字符串,如果前缀部分有长度为ι的部分相同,则Jaro-Winkler Distance为:
dj是两个字符串的Jaro Distance
ι是前缀的相同的长度,但是规定最大为4
p则是调整分数的常数,规定不能超过25,不然可能出现dw大于1的情况,Winkler将这个常数定义为0.1
这样,上面提及的MARTHA和MARHTA的Jaro-Winkler Distance为:
dw = 0.944 + (3 * 0.1(1 − 0.944)) = 0.961
个人觉得算法可以完善的点:
去除停用词(主要是标点符号的影响)
针对中文进行分析,按照词比较是不是要比按照字比较效果更好?
总结
其他参考资料:
https://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
http://www.coli.uni-saarland.de/courses/LT1/2011/slides/Python-Levenshtein.html#Levenshtein-inverse
猜你喜欢
- 本节讲述单选框/下拉菜单/添加文件,综合css,html和JavaScript实现的,具体详情如下所示:单选框:实现的功能是:(类似平时的性
- with/as使用open打开过文件的对with/as都已经非常熟悉,其实with/as是对try/finally的一种替代方案。当某个对象
- 最近和一程序员合作项目。弄的我头都大了~埋怨我的CSS命名看不懂~得按照他的来。结果我打开他的页面,看了看,从头第一个开始就是content
- Numpy创建矩阵并等间隔抽取数据1、利用Numpy创建向量和二维矩阵1.1 创建向量得到需要强调的是,向量的维度,在python中并不是书
- 代码如下:<%@LANGUAGE="VBSCRIPT" CODEPAGE="936"
- 问题:如何在报表中每隔N行显示一条粗线如何为报表增加一个行号列?回答:1、在设计模式里打开该报表,在报表主体里面加一个TextBox,把Na
- 一、前言因为最近刚好被问到这个问题,但是自己当时特别懵逼,导致没有做出来。所以下来后自己Google了很多IoU的博客,但是很多博客要么过于
- 一、背景:近期在利用 pycharm 安装第三方库时会提示 pip 不是最新版本, 因此对 pip 进行更新,但是生成最新版本之后, pi
- 今天学习到python的读取文件部分。还是以一段代码为例:filename='programming.txt'with op
- 本文实例为大家分享了php微信公众号获取位置信息的具体代码,供大家参考,具体内容如下<?php/** * wechat php tes
- 一、装饰器decorator decorator设计模式允许动态地对现有的对象或函数包装以至于修改现有的职责和行为,简单地讲用来动态地扩展现
- 在图像处理以及图像特效中,经常会用到一种成高斯分布的蒙版,蒙版可以用来做图像融合,将不同内容的两张图像结合蒙版,可以营造不同的艺术效果。这里
- Linux下MySQL整个数据库的备份与还原[root]# /usr/bin/mysqldump -h127.0.0.1 -uusernam
- asp代理采集代码如下:<%Function ProxyPage(url) Set Retrieval&
- 如何做一个树状展开视图来显示自己的记录结构?在SQL中,如何做一个可收起和展开树状结构图?就是资源管理器左栏的那种效果。这要用到Data s
- 合并两个没有共同列的dataframe,相当于按行号求笛卡尔积。最终效果如下以下代码是参考别人的代码修改的:def cartesian_df
- python里面的matplotlib.pylot是大家比较常用的,功能也还不错的一个包。基本框架比较简单,但是做一个功能完善且比较好看整洁
- 需求需要生成一个宣传的图片分享到朋友圈,这个宣传图片包含二维码,包含不同的背景图片和不同的文字。对于这种图片生成,我们考虑过使用服务端生成,
- 我们在日常开发中,我们经常会面对复杂的子系统,其中包含许多相互关联的类和接口。直接使用这些类和接口可能会导致代码的复杂性增加,使得系统难以维
- 前言Python 的一大优点就是丰富的类库,所以我们经常会用 pip 来安装各种库,所以对于Python开发用户来讲,PIP安装软件包是家常