一、概念
编辑距离:编辑距离,又称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; }
相关推荐
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
由一系列算法组成的Java版相似度计算工具包,目标是传播自然语言处理中相似度计算方法。similarity具备工具实用、性能高效、架构清晰、语料时新、可自定义的特点。 提供下列功能: 词语相似度计算 词林编码法相似度...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
(1)提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; (2)完成文本预处理功能,其中包括去除停用词、分词和词性标注等; (3)提供文本相似度计算结果的可视化功能,可以直观地展示两个...
该项目是一个使用Python语言开发的文本相似度计算系统。 1. **系统设计**:项目的主要目的是通过比较文本之间的相似性,帮助用户快速找到相关或重复的文本内容。 2. **技术实现**: - 利用了Python编程语言进行...
针对传统的相似度计算方法只考虑文本结构特征或者语义信息导致文本相似度计算质量较低等问题,结合短文本特征稀疏的特性,提出一种多重检验加权融合短文本相似度计算方法。该方法使用编辑距离、考虑词频的语义信息及...
Levenshtein:快速计算编辑距离以及字符串的相似度
printf("\t编辑距离 edits 为: %d \n",aa.edn()); LCS lcs1(a,b); printf("\t最长公共子序列为: %s\n",lcs1.lcsstr()); NG ng1(a,b,N); printf("\t字符串%d阶N-gram相似度为: %f\n",ng1.N,ng1.ngram());...
摘要:句子或文本片段相似度计算在与Web 相关的任务中起着越来越重要的作用。在基于概念之间的语义相似度基础之上, 提出一种句子语义相似度的计算方法SSBS 并进行了相关的实验。与其他方法相比,SSBS 方法在特征的...
文本相似度计算(文本匹配) 余弦相似(Cosine Similarity):两向量求余弦 点积(Dot Product):两向量归一化后求内积 汉明距离(Hamming Distance),编辑距离(Levenshtein Distance),欧氏距离(Euclidean ...
词相似度计算词林编码法相似度汉语语义法相似度知网词相似度字面编辑距离法初步相似度计算简单而言相似度句子相似度计算词性和词序结合法编辑距离算法Gregor编辑距离法优化编辑距离法文本相似度计算余弦相似度编辑...
而后介绍了最小编辑距离算法、余弦相似度算法和杰卡德相似系数,在论证了主题对文本相似度的重要性后,又针对难提取主题的文本加以改进,最终提出了基于主题和特征的文本相似度算法;然后对各个算法在测试集上的相似度...
编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中应用比较广泛,如一些评测方法中就用到了(wer,mWer等),同时也常用来计算你对原文本所作的改动数。编辑距离的算法...
计算字符串相似度(支持中英文,编辑距离算法,余弦,繁体转简体)的简单demo,可以直接运行查看结果。。。。
编辑距离就是用来计算从原串(s)转换到目标串 t 所需要的最少的插入 删除和替换的数目 在NLP中应用比较广泛 如一些评测方法中就用到了(wer mWer等) 同时也常用来计算你对原文本所作的改动数 编辑距离的算法是首先...
编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。...Python中的Levenshtein包可以方便的计算编辑距离 包的安装: pip install python-Leven
传统的相似度算法主要从字符的角度度量文本的相似性,忽略了文本内多个共同文本串对于文本相似度的影响。针对此问题提出一种基于熵的相似度求解方法,在对文本间字符信息的提取基础上,建立共同子文本串度量维度,...
编辑距离,又称为Levenshtein距离,是用于计算一个字符串转换为另一个字符串时,插入、删除和替换的次数。例如,将’dad’转换为’bad’需要一次替换操作,编辑距离为1。 nltk.metrics.distance.edit_distance函数...