文档章节

使用 Levenshtein 寻找彼此相似的字符串对

xh4n3
 xh4n3
发布于 2015/08/18 17:18
字数 1507
阅读 597
收藏 15

我们爬来了一些数据,接下来以豆瓣畅销书为例。

爬虫爬来的数据有

['艾伦•图灵传','深入理解计算机系统(原书第2版)','C++ Primer 中文版(第 5 版)','深入理解计算机系统','Web性能权威指南']

而我们系统中原有的数据有

['艾伦·图灵传','深入理解计算机系统(原书第2版)','C++ Primer 中文版(第 4 版)','深入理解计算机系统']

做前端的同志可能一眼就看出来了,两个数组中有三个元素是因为全半角的缘故,是不能全词匹配的,而前两本书事实上是同一本书。而《深入理解计算机系统》是可以全词匹配到的,《Web性能权威指南》一书是可以直接添加到数据库的。


解决方案一:

这个任务大可以交给编辑去做,但是时间复杂度为 N^2,连程序都吃不消跑,更别提让编辑做了。

解决方案二:

去除所有的标点符号,或者将所有全角符号转化为半角。 去掉所有空格。 然后进行全词匹配,这样做有些鲁莽,但是速度一点也不慢。

解决方案三:

我想到了用 jieba 进行中文分词,

import jieba
book = '艾伦·图灵传'
word = jieba.cut(book)
words = list(word)
# words = ['艾伦', '·', '图灵', '传']

对于每本书我们都可以进行这样一个分词操作,并可以考虑将标点符号去除。 然后看每两个数组的元素的重合情况,但要考虑归一化,原因如下:

  1. ‘Python 开发指南’ 和 ‘皇家 Python 开发指南’ 元素的重合数为 3 个单词。
  2. ‘Python 开发指南’ 和 ‘皇家 Python 超级无敌开发指南’ 元素的重合数为 3 个单词。

显然第 1 组看起来会比第 2 组相似一些,但是重合数是一样的。使用重合数显然不科学,我们可以通过除以分词后单词总数来计算它们的重合率。

解决方案四:

在想解决方案三的时候,我回忆起了以前做聚类算法的时候用的各种距离算法,对于实数的欧几里得距离,用在 k-modes 中的对于类型数据的相异度量算法,前者在这里显然不适用,后者又显得有点小题大做。然后我发现了一种叫做编辑距离 Edit Distance 的算法,又称 Levenshtein 距离。[1]

编辑距离是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。 维基上给出了一个例子: 'kitten' 和 'sitting' 的编辑距离为3:

  1. kitten → sitten (s 替换成 k)
  2. sitten → sittin (i 替换成 e)
  3. sittin → sitting (加上一个 g)

碰巧的是有一个开源的 python 包刚好可以计算 Levenshtein 距离,可以通过以下安装:

pip install python-Levenshtein

然后就可以计算编辑距离了:

import Levenshtein
texta = '艾伦·图灵传'
textb = '艾伦•图灵传'
print Levenshtein.distance(texta,textb)
# 3

很自然地会有这个疑问,为什么这里的编辑距离会是3,我们来看看具体进行的编辑操作。

Levenshtein.editops('艾伦·图灵传', '艾伦•图灵传')
[('insert', 6, 6), ('replace', 6, 7), ('replace', 7, 8)]

看起来只有一个字符的区别,但是这里做了三次编辑操作,为什么?我们来打印一下这两个字符串的具体表达:

In [4]: a='艾伦·图灵传'
In [5]: a
Out[5]: '\xe8\x89\xbe\xe4\xbc\xa6\xc2\xb7\xe5\x9b\xbe\xe7\x81\xb5\xe4\xbc\xa0'
In [6]: a='艾'
In [7]: a
Out[7]: '\xe8\x89\xbe'

看到这里就明白了,我们犯了一个错误,把这两个字符串存成了 string 类型,而在 string 类型中,默认的 utf-8 编码下,一个中文字符是用三个字节来表示的。于是这里又牵扯到了 Python 中的 string 和 unicode 的区别。然而在这个字节串中,我们的编辑距离,的的确确是3。

现在重新来计算距离。

print Levenshtein.distance(u'艾伦·图灵传',u'艾伦•图灵传')
# 1

现在就正确了,现在的编辑距离1就代表了两本书的名字的差别度量。这时候就要开始做归一化了,而巧的是,我们发现这个 Levenshtein 包中自带了一个相似度函数 jaro(),它可以接受两个字符串并给出从0到1范围内的相似度。下面所显示的0.888888888889便表示了这两个字符串的相似度。

print Levenshtein.jaro(u'艾伦·图灵传',u'艾伦•图灵传')
# 0.888888888889

然后我们可以写个嵌套的 for 循环,设置一个阈值 threshold,计算每一对书本的相似度,当他们超过某一阈值时,进行处理。这里要注意的就是,不要重复检验书本对,即检测(书本 A,书本 B)和(书本 B,书本 A),这样可以避免 N^2 的时间复杂度。


当然最后其实还是需要人工介入的,比如遇到第三本书这种情况,版次不一样并不算同一本书。再当然,我们是可以对所有版次有关的字符进行特殊处理,比如出现版次字符,而且两本书不相同的时候,把距离函数的输出值加上一个修正参数。不过,这种情况太多太多,还是用人工处理好了,此时的两本书为同一本书的机率是很高的。再不然,只能上机器学习了,但是也是要你有训练样本的。

参考文献: [1] wikipedia Levenshtein_distance [2] Levenshtein Document

© 著作权归作者所有

共有 人打赏支持
xh4n3
粉丝 14
博文 28
码字总数 16847
作品 0
杭州
程序员
私信 提问
php中比较两个字符串的相似度代码

在php计算字符串相似度similar_text与相似度levenshtein函数的详细介绍 similar_text函数的使用及实现过程。similar_text() 函数主要是用来计算两个字符串的匹配字符的数目,也可以计算两个字...

夜之寐h7
2016/07/06
6
0
Scala的字符串相似性度量算法库--stringmetric

stringmetric是Scala的字符串相似性度量算法的库。(如:Dice/Sorensen, Hamming, Jaccard, Jaro, Jaro-Winkler, Levenshtein, Metaphone, N-Gram, NYSIIS, Overlap, Ratcliff/Obershelp, R......

匿名
2016/03/21
269
0
ElasticSearch fuzziness 模糊查询

[[模糊]] === 模糊 模糊匹配 视两个单词 模糊'' 相似,正好像它们是同一个词. ((("typoes and misspellings", "fuzziness, defining"))) 首先, 我们需要通过fuzziness 来定义什么是((("fuzzi......

键走偏锋
2017/08/01
0
0
计算两个字符串相(或句子)似度的方法

主要方法有:编辑距离、余弦相似度、模糊相似度百分比 1 编辑距离 编辑距离(Levenshtein距离)详解(附python实现) 使用Python计算文本相似性之编辑距离 2 余弦相似度 余弦计算相似度度量 ...

致Great
2018/05/11
0
0
人们讨厌你开源文档的13个原因

【IT168 评论】大多数程序员都非常在乎他们开发的软件的质量,但是他们却很少关注相应的文档。虽然很少有人提及这一点,但是一份好的文档确实能为你的软件的成功插上翅膀。没有好文档,大家不...

开源中国社区
2013/01/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud搭建微服务架构----流量回放

前言 系统微服务化后,传统的自测/测试方式都变得比较困难: 依赖的服务可能不稳定。 服务无法提供期望的响应数据。 缺少场景构造标准。 随着整体业务越来越复杂,微服务依赖的越来越多,测试...

春哥大魔王的博客
26分钟前
3
0
记一次springboot模块配置问题导致读取Apollo配置中心配置文件始终错误的问题

现在正在做的一个项目采用的是微服务,主框架是spring cloud,配置中心用的是携程的Apollo。 项目下有多个服务,在测试服务器上启动用户服务的时候发现在eureka中心另一个服务被启动了,尝试...

zcqshine
27分钟前
6
0
流处理和批处理框架的异同

分布式流处理需求日益增加,包括支付交易、社交网络、物联网(IOT)、系统监控等。业界对流处理已经有几种适用的框架来解决,下面我们来比较各流处理框架的相同点以及区别。 分布式流处理是对...

hblt-j
30分钟前
4
0
spring cloud 面试题

什么是springboot 用来简化spring应用的初始搭建以及开发过程 使用特定的方式来进行配置(properties或yml文件) 创建独立的spring引用程序 main方法运行 嵌入的Tomcat 无需部署war文件 简化...

狼王黄师傅
32分钟前
4
0
前嗅ForeSpider教程:采集黄页88

以黄页88为例,采集当前列表页新闻的正文数据: 第一步:新建任务 ①点击左上角“加号”新建任务,如图1: 【图1】 ②在弹窗里填写采集地址,任务名称,如图2: 【图2】 ③点击下一步,选择进...

forespider
36分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部