编辑距离_编辑距离算法 - CSDN
精华内容
参与话题
  • 编辑距离编辑距离算法

    千次阅读 2018-05-02 15:46:46
    编辑距离概念描述:编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。例如将kitten一字转...

    编辑距离概念描述:

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

    例如将kitten一字转成sitting:

    1. sitten (k→s)
    2. sittin (e→i)
    3. sitting (→g)

    俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

     

    问题:找出字符串的编辑距离,即把一个字符串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。

    • 计算edit(1, 1),edit(0, 1) + 1 == 2,edit(1, 0) + 1 == 2,edit(0, 0) + f(1, 1) == 0 + 1 == 1,min(edit(0, 1),edit(1, 0),edit(0, 0) + f(1, 1))==1,因此edit(1, 1) == 1。 依次类推:

    • edit(2, 1) + 1 == 3,edit(1, 2) + 1 == 3,edit(1, 1) + f(2, 2) == 1 + 0 == 1,其中s1[2] == 'a' 而 s2[1] == 'f'‘,两者不相同,所以交换相邻字符的操作不计入比较最小数中计算。以此计算,得出最后矩阵为:

    #include <stdio.h>   
    #include <string.h>   
    char s1[1000],s2[1000];   
    int min(int a,int b,int c) {   
        int t = a < b ? a : b;   
        return t < c ? t : c;   
    }   
    void editDistance(int len1,int len2) {   
    	int d[len1+1][len2+1];
        int i,j;   
        for(i = 0;i <= len1;i++)   
            d[i][0] = i;   
        for(j = 0;j <= len2;j++)   
            d[0][j] = j;  
    		 
        for(i = 1;i <= len1;i++)   
            for(j = 1;j <= len2;j++) { 
    			if(s1[i-1] == s2[j-1])  
                	d[i][j] = d[i-1][j-1];
                else{
                	
                	int deletion = d[i-1][j] + 1;   //删除 
                	int insertion = d[i][j-1] + 1;   //插入 
               	int substitution = d[i-1][j-1] + 1;// 替换 
                	d[i][j] = min(deletion,insertion,substitution);
    				  
    			}
                 
            } 
    	for(i=0;i<=len1;i++){
    		for(j=0;j<=len2;j++){
    			printf("%d ",d[i][j]);
    		}
    		printf("\n");
    	}  
        printf("%d\n",d[len1][len2]); 
    }   
    int main(void) { 
    	scanf("%s %s",s1,s2) ;   
        editDistance(strlen(s1),strlen(s2));   
        return 0;
    } 


    展开全文
  • 算法:编辑距离问题(动态规划)

    千次阅读 2017-10-29 20:06:35
    问题描述:   设A和B是2个字符串。...将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离,记为d(A,B)。对于给定的字符串A和字符串B,计算其编辑距离 d(A,B)。 个人对问题的理解:

    问题描述:

                    

    设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离,记为d(A,B)。对于给定的字符串A和字符串B,计算其编辑距离 d(A,B)。


    个人对问题的理解:设两个字符串s[0:i],t[0:j],用最少的操作数(三种:增删换,三种各花销一次操作)将s变成t(或者t变成s,同等),先解决三种特殊情况

    1)s为空,t不为空;

    2)t为空,s不为空;

    3)s与t相等;

    对于第一第二种情况,即在i等于0时,也就是说s为空,增加j个字符,使得s转化为t,在j等于0时,也就是说t为空,就是减少 i个字符,使得s转化为t。

    对于第三种情况,显然为d(A,B)=0。



    算法描述:

                    

    1)现在只剩下普通(一般)情况,运用动态规划求出递归方程,将原问题分解为若干个子问题进行求最优解,后得出原问题的最优解,采用“填表的方法”,设计步骤:对每个子问题只求解一次,将其结果保存在一张表(构造一个行数为n+1 列数为 m+1 的矩阵 , 用来保存完成某个转换需要执行的最少操作的次数)中。然后三步a.描述最优解的结构b.递归定义最优解的值c.按自底向上的方式计算最优解的值d.由计算出的结构构造一个最优解,利用解决子问题的最优值从而得出原问题的最优值。

    2)矩阵设为d[i][j],保存从S[0:i]变到t[0:j]的编辑距离。这里S[0:i]变到t[0:j]有三种情况,要求出这三种情况的最小值作为最小操作数。分别为:

    (1)设可以在k1个操作内将s[0:i-1]转换为t[0:j],用k1+1次操作将s[0:i]转化为t[0:j],只需要先在“s[0:i]转化为t[0:j]”的操作开端做1次移除操作移除s[i]将s[0:i]转化为s[0:i-1],然后再做k1个操作就可以转换为t[0:j]。对应表格,既矩阵所求d[i][j]的左格。

    (2)设可以在k2个操作内将s[0:i]转换为t[0:j-1],用k2+1次操作将s[0:i]转化为t[0:j],先用k2次操作将s[0:i]转化为t[0:j-1],然后再执行1次插入操作在“s[0:i]变成t[0:j-1]的操作”的末尾插入“增加t[j]”的一次操作,即可将s[0:i]转化为t[0:j]。对应表格,既矩阵所求d[i][j]的上格。

    (3)设可以在k3个操作内将s[0:i-1]转化为t[0:j-1] s[i]==t[j],S[0:i]变到t[0:j]就只要k3个操作,若s[i]!=t[j],则需1次换操作加在s[0:i-1]转化为t[0:j-1]的操作数基础上就可以将S[0:i]变到t[0:j],共k3+1次。对应所求d[i][j]的左上格。

    即:(注释)

     

         子问题标识符的含义:从S[0:i]变到t[0:j]的编辑距离。(1<=i<=m,1<=j<=n)

         子问题递归公式:

          n   (m == 0 ) ;(n为字符串t的长度,m为字符串s的长度)

        m    (n== 0 )  ;

         d[j][i] =Math.min(d[j-1][i-1]+1,Math.min(d[j][i-1] + 1,d[j-1][i] + 1 ))   (s.charAt(i-1)!=t.charAt(j-1))  1<=i<=m,1<=j<=n//java编写

         d[j][i] =Math.min(d[j-1][i-1],Math.min(d[j][i-1] + 1,d[j-1][i] + 1 ))   (s.charAt(i-1)==t.charAt(j-1))  1<=i<=m,1<=j<=n

         原问题最优解:  双重循环扫描完从S[0:i]变到t[0:j]后,即S[0:m]变到t[0:n],最优值为d[n][m]的编辑距离。

    3)对于d[i][j]二维数组,可以开辟为d[n+1][m+1],n为字符串t的长度,m为字符串s的长度。首先进行如下初始化:

     

    再根据以上所说的三种方法来填表,完成后如图:

     

    如图,最优值为d[n][m]即为所求两串的编辑距离。

    申请二维数组空间代码:

    初始化代码:

     


    扫描数组的代码(即解决每个子问题最终求得原问题解的过程的代码):



    结合上述所有情况:完整代码如下:







    **注://之前把当两个字符相同时直接定为d[j-1][i-1],这个需不需要比较的问题,仍在讨论中,保险起见,暂时更改为上述做法。





    算法时间及空间复杂度分析(此次为java编写):

       由上述代码得,求子问题时的双重循环加两个初始化单循环的线性时间,再加上比较等操作的常数时间,得时间复杂度为O(M*N),而空间复杂度,花销了一个二维数组的辅助空间,得空间复杂度也为O(M*N)。


    对于动态规划的问题,解决问题前得思考好各种可能出现的情况,并且写好三步:

          子问题标识符的含义:

          子问题递归公式:

          原问题最优解:


    填表方法十分巧妙和便捷,得记牢此方法。



    展开全文
  • 最小编辑距离算法 Edit Distance(经典DP)

    万次阅读 多人点赞 2018-05-23 11:36:32
    编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越...

    编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。

    最小编辑距离模板:

    int dp[1005][1005];     /*dp[i][j]表示表示A串从第0个字符开始到第i个字符和B串从第0个
    字符开始到第j个字符,这两个字串的编辑距离。字符串的下标从1开始。*/
    char a[1005],b[1005];   //a,b字符串从下标1开始
    
    int EditDis()
    {
        int len1 = strlen(a+1);
        int len2 = strlen(b+1);
        //初始化
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++)
                dp[i][j] = INF;
        for(int i=1;i<=len1;i++)
            dp[i][0] = i;
        for(int j=1;j<=len2;j++)
            dp[0][j] = j;
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                int flag;
                if(a[i]==b[j])
                    flag=0;
                else
                    flag=1;
                dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+flag));
                //dp[i-1][j]+1表示删掉字符串a最后一个字符a[i]
                //dp[i][j-1]+1表示给字符串添加b最后一个字符
                //dp[i-1][j-1]+flag表示改变,相同则不需操作次数,不同则需要,用flag记录
            }
        }
        return dp[len1][len2];
    }
    

    概念

    字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括:

    • 删除一个字符     a) Insert a character
    • 插入一个字符     b) Delete a character
    • 修改一个字符     c) Replace a character

    例如对于字符串"if"和"iff",可以通过插入一个'f'或者删除一个'f'来达到目的。

      一般来说,两个字符串的编辑距离越小,则它们越相似。如果两个字符串相等,则它们的编辑距离(为了方便,本文后续出现的“距离”,如果没有特别说明,则默认为“编辑距离”)为0(不需要任何操作)。不难分析出,两个字符串的编辑距离肯定不超过它们的最大长度(可以通过先把短串的每一位都修改成长串对应位置的字符,然后插入长串中的剩下字符)。



    问题描述

    给定两个字符串A和B,求字符串A至少经过多少步字符操作变成字符串B。 



    问题分析

    1)首先考虑A串的第一个字符

      假设存在两个字符串A和B,他们的长度分别是lenA和lenB。首先考虑第一个字符,由于他们是一样的,所以只需要计算A[2...lenA]和B[2...lenB]之间的距离即可。那么如果两个字符串的第一个字符不一样怎么办?可以考虑把第一个字符变成一样的(这里假设从A串变成B串):

    • 修改A串的第一个字符成B串的第一个字符,之后仅需要计算A[2...lenA]和B[2...lenB]的距离即可;
    • 删除A串的第一个字符,之后仅需要计算A[2...lenA]和B[1...lenB]的距离即可;
    • 把B串的第一个字符插入到A串的第一个字符之前,之后仅需要计算A[1...lenA]和B[2...lenB]的距离即可。

    2)接下来考虑A串的第i个字符和B串的第j个字符。

      我们这个时候不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等,即A[i]=B[j],则只需要计算A[i...lenA]和B[j...lenB]之间的距离即可。如果不想等,则:

    • 修改A串的第i个字符成B串的第j个字符,之后仅需要计算A[i+1...lenA]和B[j+1...lenB]的距离即可;
    • 删除A串的第i个字符,之后仅需要计算A[i+1...lenA]和B[j...lenB]的距离即可;
    • 把B串的第j个字符插入到A串的第i个字符之前,之后仅需要计算A[i...lenA]和B[j+1...lenB]的距离即可。

      写到这里,自然会想到用递归求解或者动态规划求解,由于用递归会产生很多重复解,所以用动态规划。


    建动态规划方程

      用edit[i][j]表示A串和B串的编辑距离。edit[i][j]表示A串从第0个字符开始到第i个字符和B串从第0个字符开始到第j个字符,这两个字串的编辑距离。字符串的下标从1开始。

      dis[0][0]表示word1和word2都为空的时候,此时他们的Edit Distance为0。很明显可以得出的,dis[0][j]就是word1为空,word2长度为j的情况,此时他们的Edit Distance为j,也就是从空,添加j个字符转换成word2的最小Edit Distance为j;同理dis[i][0]就是,word1长度为i,word2为空时,word1需要删除i个字符才能转换成空,所以转换成word2的最小Edit Distance为i。

      则从上面的分析,不难推导出动态规划方程:

    ,其中

    上式中的min()函数中的三个部分,对应三种字符操作方式:

    edit[i-1][j]+1相当于给word2的最后插入了word1的最后的字符,插入操作使得edit+1,之后计算edit[i-1][j];

    edit[i][j-1]+1相当于将word2的最后字符删除,删除操作edit+1,之后计算edit[i][j-1];

    edit[i-1][j-1]+flag相当于通过将word2的最后一个字符替换为word1的最后一个字符。flag标记替换的有效次数。



    算法分析: 

      也就是说,就是将一个字符串变成另外一个字符串所用的最少操作数,每次只能增加、删除或者替换一个字符。
      首先我们令word1和word2分别为:michaelab和michaelxy(为了理解简单,我们假设word1和word2字符长度是一样的),dis[i][j]作为word1和word2之间的Edit Distance,我们要做的就是求出michaelx到michaely的最小steps。

      首先解释下dis[i][j]:它是指word1[i]和word2[j]的Edit Distance。dis[0][0]表示word1和word2都为空的时候,此时他们的Edit Distance为0。很明显可以得出的,dis[0][j]就是word1为空,word2长度为j的情况,此时他们的Edit Distance为j,也就是从空,添加j个字符转换成word2的最小Edit Distance为j;同理dis[i][0]就是,word1长度为i,word2为空时,word1需要删除i个字符才能转换成空,所以转换成word2的最小Edit Distance为i。下面及时初始化代码:

           for (int i = 0; i < row; i++) dis[i][0] = i;
           for (int j = 0; j < col; j++) dis[0][j] = j;



        下面来分析下题目规定的三个操作:添加,删除,替换。
        假设word1[i]和word2[j](此处i = j)分别为:michaelab和michaelxy
        如果b==y, 
            那么:dis[i][j] = dis[i-1][j-1]。                                                              
        如果b!=y,
            那么:添加:也就是在michaelab后面添加一个y,那么word1就变成了michaelaby,
                 此时  dis[i][j] = 1 + dis[i][j-1];
        上式中,1代表刚刚的添加操作,添加操作后,word1变成michaelaby,word2为michaelxy。
        dis[i][j-1]代表从word1[i]转换成word2[j-1]的最小Edit Distance,也就是michaelab转换成michaelx的最小
        Edit Distance,由于两个字符串尾部的y==y,所以只需要将michaelab变成michaelx就可以了,而他们之间的最
        小Edit Distance就是dis[i][j-1]。
    
    
        删除:也就是将michaelab后面的b删除,那么word1就变成了michaela,此时dis[i][j] = 1 + dis[i-1][j];
        上式中,1代表刚刚的删除操作,删除操作后,word1变成michaela,word2为michaelxy。dis[i-1][j]代表从
        word[i-1]转换成word[j]的最小Edit Distance,也就是michaela转换成michaelxy的最小Edit Distance,所以
        只需要将michaela变成michaelxy就可以了,而他们之间的最小Edit Distance就是dis[i-1][j]。
    
    
        替换:也就是将michaelab后面的b替换成y,那么word1就变成了michaelay,此时dis[i][j] = 1 + dis[i-1][j-1];
        上式中,1代表刚刚的替换操作,替换操作后,word1变成michaelay,word2为michaelxy。dis[i-1][j-1]代表从
        word[i-1]转换成word[j-1]的最小Edit Distance,也即是michaelay转换成michaelxy的最小Edit Distance,由
        于两个字符串尾部的y==y,所以只需要将michaela变成michaelx就可以了,而他们之间的最小Edit Distance就是
        dis[i-1][j-1]。
    
    
    
    
    举例:
    比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
    先创建一个6×8的表(cafe长度为4,coffee长度为6,各加2)
    (1):
        coffee
                    
    c              
    a              
    f              
    e          1
    接着,在如下位置填入数字(表2):
        coffee
      0123456
    c1            
    a2            
    f3            
    e4        2
    从3,3格开始,开始计算。取以下三个值的最小值:
    • 如果最上方的字符等于最左方的字符,则为左上方的数字。否则为左上方的数字+1。(对于3,3来说为0)
    • 左方数字+1(对于3,3格来说为2)
    • 上方数字+1(对于3,3格来说为2)
    因此为格3,3为0(表3)
        coffee
      0123456
    c1  0           
    a2            
    f3            
    e4        3     
    循环操作,推出下表
        coffee
      0123456
    c10123   4   5   
    a2112345
    f3221234
    e4332223
    取右下角,得编辑距离为3



    展开全文
  • 编辑距离算法(Edit Distance)

    万次阅读 多人点赞 2020-09-29 23:42:07
    写在前面的话今年是2016年的最后一天,外公,超级想你,我都没有想过你会不能继续再走到2017.我过得很好,每天都超级幸福,我现在在学校有一堆好朋友。哈哈,我总是能处在宇宙中心的那种人,没办法,您这么优秀才能...

    写在前面的话

    今年是2016年的最后一天,外公,超级想你,我都没有想过你会不能继续再走到2017.我过得很好,每天都超级幸福,我现在在学校有一堆好朋友。哈哈,我总是能处在宇宙中心的那种人,没办法,您这么优秀才能教出这么好的孙女,好吧。

    我会好好学习的,我是第一女王嘛,永远都会是的。是吧,要做就做最好,要么就不做,我永远都要做你的骄傲。对了,我又有很多新朋友了,我们就像家人一样,就是每天都过得超级幸福,哈哈,就是有种魔力,能让我遇到的人都把像家人一样对待。我又变美了,好吧,简直是全院最美的,好吧。现在有一堆人在照顾我,保护我,给我开心,带我给无穷无尽的快乐,我从来都没有这么开心过。生命真的很奇特,不是么。

    啊,对了,隆达罗西复出了,我们等了好久,你在天国要记得看知道么。还有啊,要照顾好自己。我爱你哟,你知道超级爱~

    好像这个月写的都是传说中的"情感"博客,看不下去了,出来写篇非情感博客。

    好像我的技术博客情感博客变成了主线,技术博客变成了背景衬托,哈哈哈,心疼的抱抱订阅我博客的小伙伴们。

    感觉最近打字真的很顺溜啊。哟西,速度真的是杠杠滴

    终于可以不正紧的写一篇技术博客了,画风突然有点奇特,嘎嘎嘎~



    概念

    编辑距离的作用主要是用来比较两个字符串的相似度的

    基本的定义如下所示:

    编辑距离,又称Levenshtein距离(莱文斯坦距离也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

    这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的,所以也叫 Levenshtein 距离。它可以用来做DNA分析,拼字检测,抄袭识别等等。总是比较相似的,或多或少我们可以考虑编辑距离。

    在概念中,我们可以看出一些重点那就是,编辑操作只有三种。插入,删除,替换这三种操作,我们有两个字符串,将其中一个字符串经过上面的这三种操作之后,得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。

    例如:
    我们有两个字符串: kitten 和 sitting:
    现在我们要将kitten转换成sitting
    我们可以做如下的一些操作;

    k i t t e n --> s i t t e n 将K替换成S

    sitten --> sittin 将 e 替换成i

    sittin --> sitting 添加g

    在这里我们设置每经过一次编辑,也就是变化(插入,删除,替换)我们花费的代价都是1。

    例如:

    • 如果str1=“ivan”,str2=“ivan”,那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)=1
    • 如果str1=“ivan1”,str2=“ivan2”,那么经过计算后等于1。str1的"1"转换"2",转换了一个字符,所以距离是1,相似度=1-1/Math.Max(str1.length,str2.length)=0.8


    #算法过程

    1.str1或str2的长度为0返回另一个字符串的长度。 if(str1.length0) return str2.length; if(str2.length0) return str1.length;

    2.初始化(n+1)(m+1)的矩阵d,并让第一行和列的值从0开始增长。扫描两字符串(nm级的),如果:str1[i] == str2[j],用temp记录它,为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。

    3.扫描完后,返回矩阵的最后一个值d[n][m]即是它们的距离。

    计算相似度公式:1-它们的距离/两个字符串长度的最大值。


    其实这个算法并不难实现
    我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况:

    1、第一行和第一列的值从0开始增长
    这里写图片描述
    图一

    首先我们先创建一个矩阵,或者说是我们的二维数列,假设有两个字符串,我们的字符串的长度分别是m和n,那么,我们矩阵的维度就应该是(m+1)*(n+1).

    注意,我们先给数列的第一行第一列赋值,从0开始递增赋值。我们就得到了图一的这个样子

    之后我们计算第一列,第二列,依次类推,算完整个矩阵。

    我们的计算规则就是:
    d[i,j]=min(d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp) 这三个当中的最小值。

    其中:str1[i] == str2[j],用temp记录它,为0。否则temp记为1

    我们用d[i-1,j]+1表示增加操作
    d[i,j-1]+1 表示我们的删除操作
    d[i-1,j-1]+temp表示我们的替换操作

    2、举证元素的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t 三者当中的最小值
    这里写图片描述

    3.依次类推直到矩阵全部生成
    这里写图片描述

    这里写图片描述

    这个就得到了我们的整个完整的矩阵。

    下面我们来看下代码,我最擅长的就是Python,下面我们来看实现:

    #!/usr/bin/env python
    # coding=utf-8
    # function   : calculate the minEditDistance of two strings
    # author     : Chicho
    # date       : 2016-12-31
    
    
    def minEditDist(sm,sn):
        m,n = len(sm)+1,len(sn)+1
    
        # create a matrix (m*n)
    
        matrix = [[0]*n for i in range(m)]
    
        matrix[0][0]=0
        for i in range(1,m):
            matrix[i][0] = matrix[i-1][0] + 1
    
        for j in range(1,n):
            matrix[0][j] = matrix[0][j-1]+1
    
        
        for i in range(m):
            print matrix[i]
    
    
        print "********************"
        
        cost = 0
    
        for i in range(1,m):
            for j in range(1,n):
                if sm[i-1]==sn[j-1]:
                    cost = 0
                else:
                    cost = 1
                
                matrix[i][j]=min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost)
    
    
        for i in range(m):
            print matrix[i]
    
        return matrix[m-1][n-1]
    
    
    mindist=minEditDist("ivan1","ivan2")
    print mindist
    

    我们来看下最后得到的运行结果:
    这里写图片描述
    上面是一个初始化的矩阵

    这里写图片描述
    最后得到的结果,距离就是最后右下角的那个值1

    下面我们在根据计算出两个字符串的相似度:

    最后得到它们的距离=1

    相似度:1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8





    参考文献:

    http://www.cnblogs.com/ivanyb/archive/2011/11/25/2263356.html

    写在后面的话

    无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看小说一样!觉得太牛了,所以分享给大家。点这里可以跳转到教程 https://www.cbedai.net/chichoxian

    在这里插入图片描述

    外公,爱你,给你一个敲大的么么哒

    这里写图片描述

    希望生命可以产生所有奇妙的化学反应

    展开全文
  • 72.编辑距离

    2019-05-22 17:22:17
    详解编辑距离(Edit Distance)及其代码实现 应用:编辑距离 题目描述: 给定两个单词word1和word2,计算出将word1转换成word2所使用的最少操作数。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一...
  • 编辑距离

    2020-02-21 16:27:32
    编辑距离是指两个子串之间,由一个转成另一个所需要的最少编辑操作次数。允许的编辑操作包括: 将一个字符替换成另一个字符 插入一个字符 删除一个字符 这是常见的求两个字符编辑距离的题目描述,被称为...
  • 编辑距离

    千次阅读 2017-12-27 23:11:43
    编辑距离是计算两个文本相似度的算法之一,以字符串为例,字符串a和字符串b的编辑距离是将a转换成b的最小操作次数,这里的操作包括三种: 插入一个字符 删除一个字符 替换一个字符 举个例子,kitten和sitting的...
  • Levenshtein Distance算法,又叫Edit Distance算法...一般来说,编辑距离越小,两个串的相似度越大。    算法基本原理:假设我们可以使用d[i,j]个步骤(可以用一个二维数组保存这个值),表示将串 s[1...i]转换...
  • 编辑距离详解及应用

    千次阅读 2018-05-19 23:18:19
    今天老师布置一道实验题,虽然说给的时间挺长的,但是还是挺难的,而且...将字符串A变换为字符串B所需要的最少字符操作数称为字符串A到字符串B的编辑距离(Edit Distance)。任务:1.应用动态规划设计策略,设...
  • 本文主要讲一下文本相似度计算的几个距离公式,主要包括:欧氏距离、余弦相似度、Jaccard距离、编辑距离。 距离计算在文本很多场景下都可以用到,比如:聚类、K近邻、机器学习中的特征、文本相似度等等。
  • 编辑距离计算python实现

    千次阅读 2019-08-21 15:05:20
    编辑距离是用来比较两个字符串之间相似度的度量方法,表示的是两个字符串间相互转换所需要的最少步骤。 编辑距离递推公式: 算法计算步骤: 1.对于字符串A 'jarrry'和字符串B'jerr',先初始化矩阵dp为 [len(A) ...
  • 最小编辑距离python实现

    千次阅读 2014-10-12 16:13:41
    # -*- coding: cp936 -*- def edit(str1, str2):    matrix = [[i+j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)] ... for i in xrange(1,len(str1)+1): ... for j in xrange
  • Java实现字符串编辑距离

    万次阅读 多人点赞 2019-07-26 17:33:51
    1 问题描述 给定一个源串和目标串,能够进行如下操作: 在任意位置上插入一个字符; 替换掉任意字符; 删除任意字符。 写一个程序,实现返回最小操作次数,使得对源串进行上述这些操作后等于目标串。...
  • Python如何计算编辑距离

    千次阅读 2019-03-11 19:17:05
    在计算文本的相似性时,经常会用到编辑距离编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。通常来说,编辑距离越小,两个文本的相似性越大。这里的编辑操作主要包括...
  • 相似度算法——Levenshtein(编辑距离)

    千次阅读 2018-01-03 17:47:34
    Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。 编辑距离的算法是首先由俄国...
  • solr之~模糊查询

    万次阅读 2015-07-17 11:02:01
    例如,有的人可能想要搜索某个前缀开始的单词(称为通配符查询),或者想要查询和关键字有一两个字母不相同的单词(称为模糊查询或编辑距离查询),或者你想要查询两个关键字,并且这两个关键字之间的距离不会大于...
  • Python 字符串相似性的几种度量方法

    万次阅读 2018-02-01 19:26:11
    评价字符串相似度最常见的办法就是:把一个字符串通过插入、删除或替换这样的编辑操作,变成另外一个字符串,所需要的最少编辑次数,这种就是编辑距离(edit distance)度量方法,也称为Levenshtein距离。...
  • 文本相似度 -- 最小编辑距离算法

    万次阅读 2017-08-10 22:10:18
    最小编辑距离算法是计算两个字符串之间相互转换最少要经过多少次操作(增加,移除,替换)的算法 算法原理 这个算法计算的是将s[1…i]转换为t[1…j](例如将beauty转换为batyu)所需最少的操作数(也就是所谓的编辑...
  • 在信息论和计算机科学中,
  • 本文介绍了一种语义版本的编辑距离
1 2 3 4 5 ... 20
收藏数 86,738
精华内容 34,695
关键字:

编辑距离