当前位置:首页 > 开发 > 行业应用 > 正文

文本相似度计算-编辑距离

发表于: 2014-07-20   作者:dengqsintyt   来源:转载   浏览次数:
摘要: 一、概念 编辑距离:编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。 如:将sailn一字转成failing: sailn--->failn:   (s->f)插入,删除 sailn--->failin:  (+i)  

一、概念

编辑距离:编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

如:将sailn一字转成failing:

sailn--->failn:   (s->f)插入,删除

sailn--->failin:  (+i)  插入

sailn--->failing: (+g)  插入

        则:sailn与failing的最少编辑距离就是3

问题:找出字符串的编辑距离,即把一个字符串s1最少经过多少步操作变成编程字符串s2,操作有三种,添加一个字符,删除一个字符,修改一个字符

 

二、思想

函数edit(i, j),它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

简单描述动态规划公式:

if i == 0 且 j == 0,edit(i, j) = 0

if i == 0 且 j > 0,edit(i, j) = j

if i > 0 且j == 0,edit(i, j) = i

if i ≥ 1  且 j ≥ 1 ,edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) },当第一个字符串的第i个字符不等于第二个字符串的第j个字符时,f(i, j) = 1;否则,f(i, j) = 0。

        计算出两个文本的最少编辑距离之后,如果这个数字越小,那么说明这两篇文章越相似,但是很明显,通过这种方法计算的时间复杂度为,而且需要两两进行计算,所以只适合处理小数据的文本

三、实现

int min(int a, int b)
{
	return a < b ? a : b;
}

int edit(string str1, string str2)
{
	int max1 = str1.size();
	int max2 = str2.size();

	int **ptr = new int*[max1 + 1];
	for(int i = 0; i < max1 + 1 ;i++)
	{
		ptr[i] = new int[max2 + 1];
	}

	for(int i = 0 ;i < max1 + 1 ;i++)
	{
		ptr[i][0] = i;
	}

	for(int i = 0 ;i < max2 + 1;i++)
	{
		ptr[0][i] = i;
	}

	for(int i = 1 ;i < max1 + 1 ;i++)
	{
		for(int j = 1 ;j< max2 + 1; j++)
		{
			int d;
			int temp = min(ptr[i-1][j] + 1, ptr[i][j-1] + 1);
			if(str1[i-1] == str2[j-1])
			{
				d = 0 ;
			}
			else
			{
				d = 1 ;
			}
			ptr[i][j] = min(temp, ptr[i-1][j-1] + d);
		}
	}

	cout << "**************************" << endl;
	for(int i = 0 ;i < max1 + 1 ;i++)
	{
		for(int j = 0; j< max2 + 1; j++)
		{
			cout << ptr[i][j] << " " ;
		}
		cout << endl;
	}
	cout << "**************************" << endl;
	int dis = ptr[max1][max2];

	for(int i = 0; i < max1 + 1; i++)
	{
		delete[] ptr[i];
		ptr[i] = NULL;
	}

	delete[] ptr;
	ptr = NULL;

	return dis;
}

 

 

 

文本相似度计算-编辑距离

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一、概述 针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Mo
一、概述 针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Mo
总结一下模式识别中的距离和相似度计算方式 一.距离 首先介绍闵科夫斯基距离: r=1,城市街区距离,一
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前
海量数据相似度计算之simhash和海明距离 2013-08-28 13:44 严澜(@观澜而索源) jobbole.com 我要评
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前
海量数据相似度计算之simhash和海明距离 通过 采集系统 我们采集了大量文本数据,但是文本中有很多
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号