文档章节

计算字符串的相似度

无情小白龙
 无情小白龙
发布于 2014/05/26 16:33
字数 614
阅读 32
收藏 1

问题描述

对于给定的两个字符串,可以进行增加、减少或者修改一个字符的方式使一个字符串等于另一个字符串,把需要操作的次数定义为两个字符串的距离,相似度等于“距离+1”的倒数。


分析求解

两个字符串A和B,下标范围为[aBegin,aEnd]和[bBegin,bEnd]

如果第一个字符相等,则不作处理,只需计算A[2,aEnd]和B[2,bEnd]的距离

如果不相等,可以做以下处理

  1. 删除A的第一个字符,然后计算A[2,aEnd]和B[1,bEnd]的距离。

  2. 删除B的第一个字符,然后计算A[1,aEnd]和B[2,bEnd]的距离。

  3. 修改A的第一个字符为B的第一个字符,然后计算A[2,aEnd]和B[2,bEnd]的距离。

  4. 修改B的第一个字符为A的第一个字符,然后计算A[2,aEnd]和B[2,bEnd]的距离。

  5. 添加A的第一个字符到B的第一个字符之前,然后计算A[2,aEnd]和B[1,bEnd]的距离。

  6. 添加B的第一个字符到A的第一个字符之前,然后计算A[1,aEnd]和B[2,bEnd]的距离。

但是我们最终关注的问题是怎样求得两个字符串的距离,也就是说我们只要知道通过一步操作就可以将问题简化成规模更小的问题就可以,没有必要实施这个操作。

那么上面6个操作就可以合并为下面3个操作

  1. 一步操作之后,再处理A[1,aEnd]和B[2,bEnd]。

  2. 一步操作之后,再处理A[2,aEnd]和B[1,bEnd]。

  3. 一步操作之后,再处理A[2,aEnd]和B[2,bEnd]。

代码实现

//*End代表的是要比较的字符串的最后一个字符的下一个位置
int calculate(char *strA, int aBegin, int aEnd, char *strB, int bBegin, int bEnd)
{
	if(aBegin>=aEnd)
	{
		if(bBegin>=bEnd)
			return 0;
		else 
			return bEnd-bBegin;
	}

	if(bBegin>=bEnd)
	{
		if(aBegin>=aEnd)
			return 0;
		else 
			return aEnd-aBegin;
	}

	if(strA[aBegin]==strB[bBegin])
	{
		return calculate(strA,aBegin+1,aEnd,strB,bBegin+1,bEnd);
	}
	else
	{
		int n1 = calculate(strA,aBegin+1,aEnd,strB,bBegin,bEnd);
		int n2 = calculate(strA,aBegin,aEnd,strB,bBegin+1,bEnd);
		int n3 = calculate(strA,aBegin+1,aEnd,strB,bBegin+1,bEnd);
		
		//求最小值+1
		return min(n1,n2,n3) + 1;
	}
}


参考书籍:《编程之美》

© 著作权归作者所有

无情小白龙
粉丝 4
博文 24
码字总数 12338
作品 0
西安
程序员
私信 提问
文本相似度计算基本方法小结

相似度计算方面 Jaccard相似度:集合之间的Jaccard相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。 Shingling:k-shingle是指文档中连续...

小萝卜_
2016/05/24
156
1
【java算法】---余弦相似度计算字符串相似率

余弦相似度计算字符串相似率 功能需求:最近在做通过爬虫技术去爬取各大相关网站的新闻,储存到公司数据中。这里面就有一个技术点,就是如何保证你已爬取的新闻,再有相似的新闻 或者一样的新...

雨点的名字
2018/08/15
0
0
一个根据相似度的去重方法

需求,一个csv文件中有很多行,每行是个id,字符串,每个字符串可能两两相似(是相似,不是相同),怎样去重,保留两两相似度小于0.8的id。 做法,用diff库计算两两相似度,每次计算结果,这...

caucy
2017/07/19
140
0
从文档相似度计算看LSH(Locality Sensitive Hashing)

经常使用的哈希函数,冲突总是不招人喜欢。LSH却依赖于冲突,在解决NNS(Nearest neighbor search )时,我们期望: 离得越近的对象,发生冲突的概率越高 离得越远的对象,发生冲突的概率越低 ...

开源中国驻成都办事处
2012/09/16
5.9K
4
求解类似数据如何搜索!

数据格式如下 "10101010001001101100100011000100100100001011100001000010010101000101010101000101".....共计256位 就是除了1就是0的唯一标示符256位的跟64位的还有1024位的 这种标示符 目......

1514582970
2016/04/07
197
2

没有更多内容

加载失败,请刷新页面

加载更多

面向对象编程

1、类和对象 类是对象的蓝图和模板,而对象是实例;即对象是具体的实例,类是一个抽象的模板 当我们把一大堆拥有共同特征的对象的静态特征(属性)和动态特征(行为)都抽取出来后,就可以定...

huijue
今天
8
0
redis异常解决 :idea启动本地redis出现 jedis.exceptions.JedisDataException: NOAUTH Authentication required

第一次安装在本地redis服务,试试跑项目,结果却出现nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required错误,真是让人头疼 先检查一...

青慕
今天
10
0
Spring 之 IoC 源码分析 (基于注解方式)

一、 IoC 理论 IoC 全称为 Inversion of Control,翻译为 “控制反转”,它还有一个别名为 DI(Dependency Injection),即依赖注入。 二、IoC方式 Spring为IoC提供了2种方式,一种是基于xml...

星爵22
今天
25
0
Docker安装PostgresSql

Docker安装PostgresSql 拉取docker镜像 # docker pull postgres:10.1010.10: Pulling from library/postgres9fc222b64b0a: Pull complete 38296355136d: Pull complete 2809e135bbdb: Pu......

Tree
今天
8
0
内容垂直居中

方法一: 采用上下 padding 形式,将内容放置在垂直居中 .line { padding: 2% 0; text-align: center; height: 5px;} <div class="line"> 内容垂直居中</div> 方法二: 采......

低至一折起
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部