大家在做爬虫的时候,很容易保持一些相似的数据,这些相似的数据由于不完全一致,如果要通过人工一一的审核,将耗费大量的时间,大家对编辑距离应该有所了解,这篇文章我们先来了解下什么是编辑距离,然后在学习 Python 如何计算编辑距离,下面来一起学习学习吧。
Python 是一种面向对象、解释型计算机程序设计语言,由 Guido van Rossum 于 1989 年底发明,第一个公开发行版发行于 1991 年。Python 语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是 C/C++)很轻松地联结在一起。
编辑距离
编辑距离(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)
计算莱文斯坦比。计算公式
, 其中 sum 是指 str1 和 str2 字串的长度总和,ldist 是类编辑距离。注意这里是类编辑距离,在类编辑距离中删除、插入依然 + 1,但是替换 + 2。
- r = (sum – ldist) / sum
- 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
个人觉得算法可以完善的点:
去除停用词(主要是标点符号的影响)
针对中文进行分析,按照词比较是不是要比按照字比较效果更好?
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家学习或者使用 python 能有所帮助,如果有疑问大家可以留言交流。
其他参考资料:
https://en.wikipedia.org/wiki/Jaro–Winkler_distance
http://www.coli.uni-saarland.de/courses/LT1/2011/slides/Python-Levenshtein.html#Levenshtein-inverse
来源: http://www.phperz.com/article/17/0317/310742.html