开发者社区> ghost丶桃子> 正文

计算字符串的相似度(编辑距离)

简介:
+关注继续查看

问题

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
1.修改一个字符(如把“a”替换为“b”)。
2.增加一个字符(如把“abdd”变为“aebdd”)。
3.删除一个字符(如把“travelling”变为“traveling”)。
比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离,给定任意两个字符串,你是否能写出一个算法来计算出它们的距离?

分析与解法

不难看出,两个字符串的距离肯定不超过它们的长度之和(我们可以通过删除操作把两个串都转化为空串)。虽然这个结论对结果没有帮助,但至少可以知道,任意两个字符串的距离都是有限的。
我们还是应该集中考虑如何才能把这个问题转化成规模较小的同样的问题。如果有两个串A=xabcdae和B=xfdfa,它们的第一个字符是相同的,只要计算A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同,那么可以进行如下的操作(lenA和lenB分别是A串和B串的长度):
1.删除A串的第一个字符,然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
2.删除B串的第一个字符,然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符,然后计算A[2,…,lenA]和B[2,…,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符,然后计算A[2,…,lenA]和B[2,…,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前,然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前,然后计算A[2,…,lenA]和B[1,…,lenB]的距离。

在这个题目中,我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以,可以将上面6个操作合并为:
1.一步操作之后,再将A[2,…,lenA]和B[1,…,lenB]变成相同字符串。
2.一步操作之后,再将A[1,…,lenA]和B[2,…,lenB]变成相同字符串。
3.一步操作之后,再将A[2,…,lenA]和B[2,…,lenB]变成相同字符串。

这样,很快就可以完成一个递归程序。

代码实现:

复制代码
int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd)  
{    
    if (pABegin > pAEnd)    
    {    
        if (pBBegin > pBEnd)    
            return 0;     
        else    
            return pBEnd - pBBegin + 1;    
    }    
    if (pBBegin > pBEnd)    
    {    
        if(pABegin > pAEnd)    
            return 0;    
        else    
            return pAEnd - pABegin + 1;    
    }    
    if (strA[pABegin] == strB[pBBegin])    
    {    
        return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);    
    }    
    else    
    {    
        int t1 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd);    
        int t2 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd);    
        int t3 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd);    
    
        return minValue(t1,t2,t3)+1;    
    }    
}  
复制代码

以上解法来自《编程之美》,有什么地方需要改进的呢?问题在于:在递归的过程中,有些数据被重复计算了。

很经典的可使用动态规划方法解决的题目,和计算两字符串的最长公共子序列相似。

设Ai为字符串A(a1a2a3 … am)的前i个字符(即为a1,a2,a3 … ai)
设Bj为字符串B(b1b2b3 … bn)的前j个字符(即为b1,b2,b3 … bj)

设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
当ai==bj时 显然 L(i,j) = L(i-1,j-1)
当ai!=bj时 

  若将它们修改为相等,则对两个字符串至少还要操作L(i-1,j-1)次
   若删除ai或在bj后添加ai,则对两个字符串至少还要操作L(i-1,j)次
   若删除bj或在ai后添加bj,则对两个字符串至少还要操作L(i,j-1)次
   此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1 

显然,L(i,0)=i,L(0,j)=j, 再利用上述的递推公式,可以直接计算出L(i,j)值。

代码实现:

复制代码
int minValue(int a, int b, int c)
{
    int t = a <= b ? a:b;
    return t <= c ? t:c;
}

int calculateStringDistance(string strA, string strB)
{
    int lenA = (int)strA.length()+1;
    int lenB = (int)strB.length()+1;

    int **c = new int*[lenA];
    for(int i = 0; i < lenA; i++)
        c[i] = new int[lenB];

    for(int i = 0; i < lenA; i++) c[i][0] = i;
    for(int j = 0; j < lenB; j++) c[0][j] = j;
    c[0][0] = 0;
    for(int i = 1; i < lenA; i++)
    {
        for(int j = 1; j < lenB; j++)
        {
            if(strB[j-1] == strA[i-1])
                c[i][j] = c[i-1][j-1];
            else
                c[i][j] = minValue(c[i][j-1], c[i-1][j], c[i-1][j-1]) + 1;
        }
    }

    int ret =  c[lenA-1][lenB-1];

    for(int i = 0; i < lenA; i++)
        delete [] c[i];
    delete []c;

    return ret;
}
复制代码

 

 

 

 

作者:阿凡卢
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
http://www.cnblogs.com/luxiaoxun/archive/2012/08/05/2623894.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium
题目: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating let...
730 0
Confluence 7 手动上传编辑过的文件
Confluence 7 手动上传编辑过的文件
76 0
写一个函数对字符串数组排序,使所有变位词都相邻
题目 写一个函数对字符串数组排序,使得所有的变位词都相邻。 解答 首先,要弄清楚什么是变位词。变位词就是组成的字母相同,但顺序不一样的单词。 比如说:live和evil就是一对变位词。OK,那么这道题目的意思就很清楚了, 它并不要求我们将字符串数组中的字符串按字典序排序,否则我们直接调用STL中的sort 函数就可以了。
841 0
可以搜索到DedeCms后台文章列表文档id吗?或者快速定位id编辑文章
  我们在建站时有的时候发现之前的文章有错误了,要进行修改,但又不知道文章名,只知道大概的文章id,那么可以搜索到DedeCms后台文章列表文档id吗?或者快速定位文章id方便修改?   第一种方法:复制下面的链接地址,直接修改文章id(aid=1183这个数字),就进入文章编辑页面了 http://www.
795 0
json格式的字符串转为json对象遇到特殊字符问题解决
中午做后台发过来的json的时候转为对象,可是有几条数据一直出不来,检查发现json里包含了换行符,造成这种情况的原因可能是编辑部门在编辑的时候打的回车造成的 假设有这样一段json格式的字符串 1 var json={ 2 "school": [ 3 { 4 ...
658 0
LeetCode 1422. 分割字符串的最大得分
给你一个由若干 0 和 1 组成的字符串 s ,请你计算并返回将该字符串分割成两个 非空 子字符串(即 左 子字符串和 右 子字符串)所能获得的最大得分。
140 0
1955
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载