精华内容
参与话题
问答
  • 我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时,其中编辑单个字符(比如修改、插入、删除)所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。 简单例子 从字符串...

    基本介绍

      Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时,其中编辑单个字符(比如修改、插入、删除)所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。

     

    简单例子

      从字符串“kitten”修改为字符串“sitting”只需3次单字符编辑操作,如下:

      • sitten ( k -> s )
      • sittin ( e -> i )
      • sitting ( _ -> g )

      因此“kitten”和“sitting”的Levenshtein距离为3。

     

    实现思想

      如何编程实现这一算法呢?许多人试图用矩阵来解释,但实际上矩阵是最终可视化的工具,配合理解“为什么”比较方便,但从矩阵却比较难想到“怎么做”。

      我们试图找到“从字符串AAA修改到字符串BBB”这一问题的子解结构。当然反过来说“从字符串BBB修改到字符串AAA”和它是同一个问题,因为从AAA中删掉一个字符来匹配BBB,就相当于在BBB中插入一个字符来匹配AAA,这两个操作是可以互相转化的。

      假设字符序列A[1i]A[1\ldots i]A[1i]B[1j]B[1\ldots j]B[1j]分别是字符串AAABBB的前iiijjj个字符构成的子串,我们得到一个子问题是“从字符串A[1i]A[1\ldots i]A[1i]修改到字符串B[1j]B[1\ldots j]B[1j]”:A:B:A[1]B[1]A[2]B[2]A[i2]B[j2]A[i1]B[j1]A[i]B[j]\left[\begin{matrix}\begin{aligned}&A:&&A[1]&&A[2]&&\cdots&&A[i-2]&&A[i-1]&&A[i]\\\\&B:&&B[1]&&B[2]&&\cdots&&B[j-2]&&B[j-1]&&B[j]\end{aligned}\end{matrix}\right]A:B:A[1]B[1]A[2]B[2]A[i2]B[j2]A[i1]B[j1]A[i]B[j]

      ① 插入操作

      • 当将A[1i]A[1\ldots i]A[1i]修改成B[1j1]B[1\ldots j-1]B[1j1]需要操作数为op1op_1op1,那么我插入一个字符A[i']=B[i]A[i']=B[i]A[i]=B[i]A[i]A[i]A[i]A[i+1]A[i+1]A[i+1]之间,用以匹配B[i]B[i]B[i],于是A[1i]A[1\ldots i]A[1i]修改到B[1j]B[1\ldots j]B[1j]所需操作数为op1+1op_1+1op1+1A[i2]B[j2]A[i1]B[j1]A[i]B[j]A[i]ϕ\left[\begin{matrix}\begin{aligned}&&\cdots&&\color{Red}{A[i-2]}&&\color{Red}{A[i-1]}&&\mathbf{\color{Red}{A[i]}}&&\mathbf{\color{Blue}{A[i']}}&&\\\\&&\cdots&&\color{Red}{B[j-2]}&&\mathbf{\color{Red}{B[j-1]}}&&\mathbf{\color{Blue}{B[j]}}&&\phi&&\end{aligned}\end{matrix}\right]A[i2]B[j2]A[i1]B[j1]A[i]B[j]A[i]ϕ

      ② 删除操作

      • 当将A[1i1]A[1\ldots i-1]A[1i1]修改成B[1j]B[1\ldots j]B[1j]需要操作数为op2op_2op2,那么我删掉字符A[i]A[i]A[i]也可以op2+1op_2+1op2+1的操作数使两个子字符串匹配:A[i2]B[j2]A[i1]B[j1]ϕB[j]\left[\begin{matrix}\begin{aligned}&&\cdots&&\color{Red}{A[i-2]}&&\mathbf{\color{Red}{A[i-1]}}&&\mathbf{\color{Blue}{\phi}}&&\\\\&&\cdots&&\color{Red}{B[j-2]}&&\color{Red}{B[j-1]}&&\mathbf{\color{Red}{B[j]}}&&\end{aligned}\end{matrix}\right]A[i2]B[j2]A[i1]B[j1]ϕB[j]

      ③ 修改操作

      • 如果A[1i1]A[1\ldots i-1]A[1i1]修改成B[1j1]B[1\ldots j-1]B[1j1]所需操作数为op3op_3op3的话,我将字符A[i]A[i]A[i]替换成A[i']=B[j]A[i']=B[j]A[i]=B[j],就可以op3+1op_3+1op3+1的操作数完成:A[i2]B[j2]A[i1]B[j1]A[i]B[j]\left[\begin{matrix}\begin{aligned}&&\cdots&&\color{Red}{A[i-2]}&&\mathbf{\color{Red}{A[i-1]}}&&\mathbf{\color{Blue}{A[i']}}&&\\\\&&\cdots&&\color{Red}{B[j-2]}&&\mathbf{\color{Red}{B[j-1]}}&&\mathbf{\color{Blue}{B[j]}}&&\end{aligned}\end{matrix}\right]A[i2]B[j2]A[i1]B[j1]A[i]B[j]
      • 但如果此时字符A[i]==B[j]A[i]==B[j]A[i]==B[j]的话,则不需要进行修改操作,操作数仍为op3op_3op3

      综上所述,我们将字符串A[1i]A[1\ldots i]A[1i]修改成字符串B[1j]B[1\ldots j]B[1j]所需操作为min{op1+1, op2+1, op3+1(aibi)}min\{op_1+1,\ op_2+1,\ op_3+1_{(a_i\neq b_i)}\}min{op1+1, op2+1, op3+1(aibi)},其中1(aibi)1_{(a_i\neq b_i)}1(aibi)代表当aibia_i\neq b_iaibi时取值111,否则取值为000

     

    数学定义

      数学上,我们定义两个字符串AAABBB间的Levenshtein距离为levA, B(a, b)lev_{A,\ B}(a,\ b)levA, B(a, b),其中aaabbb分别为字符串AAABBB的长度,而levA, Bi, j=ijminleva, b(i, j1)+1leva, b(i1, j)+1leva, b(i1, j1)+1(aibi), j=0, i=0, otherwiselev_{A,\ B}(i,\ j)=\left\{\begin{matrix}\begin{aligned}&i&&,\ j=0\\&j&&,\ i=0\\&min\left\{\begin{matrix}lev_{a,\ b}(i,\ j-1)+1\\lev_{a,\ b}(i-1,\ j)+1\\lev_{a,\ b}(i-1,\ j-1)+1_{(a_i\neq b_i)}\end{matrix}\right.&&,\ otherwise\end{aligned}\end{matrix}\right.levA, B(i, j)=ijminleva, b(i, j1)+1leva, b(i1, j)+1leva, b(i1, j1)+1(aibi), j=0, i=0, otherwise

      更多请参考 Wikipedia - Levenshtein_distance

     

     

    C++代码

      有了状态转移方程,我们就可以愉快地DP了,时间复杂度O(MN)O(MN)O(MN),空间复杂度O(MN)O(MN)O(MN)

    复制代码
     1 #include <stdio.h>
     2 #include <string.h>
     3 #include <algorithm>
     4 using std::min;
     5 int lena, lenb;
     6 char a[1010], b[1010];
     7 void read() {
     8     scanf("%s%s", a, b);
     9     lena = strlen(a);
    10     lenb = strlen(b);
    11 }
    12 
    13 int dp[1010][1010];
    14 void work() {
    15     for(int i=1; i<=lena; i++) dp[i][0] = i;
    16     for(int j=1; j<=lenb; j++) dp[0][j] = j;
    17     for(int i=1; i<=lena; i++)
    18         for(int j=1; j<=lenb; j++)
    19             if(a[i-1]==b[j-1])
    20                 dp[i][j] = dp[i-1][j-1];
    21             else
    22                 dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1;
    23     printf("%d\n", dp[lena][lenb]);
    24 }
    25 
    26 int main() {
    27     read();
    28     work();
    29     return 0;
    30 }
    复制代码

     

    几个小优化

      1. 如果满足A[i]==B[j]A[i]==B[j]A[i]==B[j](下标从111开始),实际上是可以直接取lev(i, j)=lev(i1, j1)lev(i,\ j)=lev(i-1,\ j-1)lev(i, j)=lev(i1, j1)的。因为此时字符相同是不需要任何编辑操作的。这一优化也可以从上文转移方程中构造不等关系得出。

      2. 如果使用滚动数组,则空间复杂度可以降到O(2max{M, N})O(2*max\{M,\ N\})O(2max{M, N})。但也可以通过保存lev(i1, j1)lev(i-1,\ j-1)lev(i1, j1)来把空间复杂度降到O(max{M, N})O(max\{M,\ N\})O(max{M, N}),如下:

    复制代码
     1 int dp[1010];
     2 void work() {
     3     for(int j=1; j<=lenb; j++) dp[j] = j;
     4     int t1, t2;
     5     for(int i=1; i<=lena; i++) {
     6         t1 = dp[0]++;
     7         for(int j=1; j<=lenb; j++) {
     8             t2 = dp[j];
     9             if(a[i-1]==b[j-1])
    10                 dp[j] = t1;
    11             else
    12                 dp[j] = min(t1, min(dp[j-1], dp[j]))+1;
    13             t1 = t2;
    14         }
    15     }
    16     printf("%d\n", dp[lenb]);
    17 }
    复制代码

     

    以上即为Levenshtein距离算法的基本介绍,如果您喜欢,请点个推荐吧~如果您有宝贵意见,欢迎在下方评论区提出哦~

     

    展开全文
  • 编辑距离及编辑距离算法

    千次阅读 2018-05-02 11:01:27
    编辑距离概念描述:编辑距离,又称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;
    } 


    展开全文
  • 先解释下什么是编辑距离算法。就是两个字符串(假如为S,T),从第一个字符串S,经过插入,删除,替换,添加,等操作数的总和数最小的路径称为字符串S和T的编辑距离。。。以程序中的字符串为例:sting,cbstring11....
    在看一篇博文的时候看到了这么个算法,捉摸了很久才弄懂什么意思。
    先解释下什么是编辑距离算法。
    就是两个字符串(假如为S,T),从第一个字符串S,经过插入,删除,替换,添加,等操作数的总和数最小的路径称为字符串S和T的编辑距离。。。
    以程序中的字符串为例:sting,cbstring1

    1.首先创建一个二维矩阵,6 x 9,设为C[][]
    首先初始化值。其实代表着初始化移动距离。。
    2.进入循环,如果S的第一个字符串==T的第二个字符串,z=C[I][J],否则z=C[I+1][J+1]
    其实就是记录操作数。z=0,或者z=1,最后记录到c[i=1][i=1],也就是说C,对应数组的值的是距离
    但实例中不相等,则z=1,x=2,y=2,最后,C[1][1]=1;也就是说,到现在已经进行了距离为1的编辑。。
    3.重新进入循环
    i=0,j=1,这时
    str1[i] == str2[j]仍然不成立。x=3,y=2,z=2,c[1][2]=2
    4。进入循环
    i=0,j=2,这时str1[i] == str2[j],成立,x=4,y=3,z=2
    c[1][3]=2.
    5.进入循环,i=0,j=3,这时不成立,x=5,y=3,z=4,c[1][4]=3.
    6.i=0,j=4,不成立。x=6,y=4,z=5,c[1][5]=4;
    //上面的步骤,相当于s到cbsting1前j个子字符串的编辑距离。
    (有个算法是 这样的:见文章最后,引用1)
    接着就是S的st二个字符串到cbsting1前J个子字符串的编辑距离。
    二‘i=1.
    1.i=1,j=0,不成立,x=2,y=3,z=2,c[2][1]=2
    2.i=1,j=1,不成立,x=3,y=3,z=2,c[2][2]=2
    3.i=1,j=2,成立,x=c[2][3]+1=2,y=c[2][2]+1=3;z=2;c[2][3]=2;
    。。。。


    0 1 2 3 4 5
    1 1 2 2 3 4
    2 2 2 2 2 3
    3
    4
    5
    6
    7
    8















    其实总结下:
    C[I][J],就是S的[0..i]字串到T[0..J]字串的编辑距离。
    分解成C[I][J]=c[i-1][j]+1,c[i][j-1]+1,c[i-1][j-1]+f[i][j](见小注)
    也就是
    C[I+1][J+1]=c[i][j+1]+1,c[i+1][j]+1,c[i][j]+f[i+1][j+1]
    下面是程序
    package Algorithm;
    
    public class Distance {
        public static void main(String[]args){
            int a=new Distance().getDistance("sting".toCharArray(),"cbsting1".toCharArray());
            System.out.println(a);
        }
        public int getDistance(char[] str1,char[] str2){
           
             int n = str1.length;
             int m = str2.length;
             int[][] C = new int[n+1][m+1];
             int i, j, x, y, z;
             for (i = 0; i <= n; i++)
                 C[i][0] = i;
             for (i = 1; i <= m; i++)
                 C[0] [i] = i;
             for (i = 0; i < n; i++)
                 for (j = 0; j < m; j++)
                 {
                     x = C[i][j + 1] + 1;
                     y = C[i + 1][ j] + 1;
                     if (str1[i] == str2[j])
                         z = C[i][ j];
                     else
                         z = C[i][ j] + 1;
                    
                     C[i + 1][ j + 1] = Math.min(Math.min(x, y), z);
                 }
             return C[n][ m];
         }
       
    }
    

     

    引用1:原文:http://hxraid.iteye.com/blog/615469

    例如:S=“eeba”   T="abac" 我们发现当S只有一个字符e、T只有一个字符a的时候,我们马上就能得到S和T的编辑距离edit(0,0)=1(将e替换成a)。那么如果S中有1个 字符e、T中有两个字符ab的时候,我们是不是可以这样分解:edit(0,1)=edit(0,0)+1(将e替换成a后,在添加一个b)。如果S中有 两个字符ee,T中有两个字符ab的时候,我们是不是可以分解成:edit(1,1)=min(edit(0,1)+1, edit(1,0)+1, edit(0,0)+f(1,1)). 这样我们可以得到这样一些动态规划公式:      
            如果i=0且j=0        edit(0, 0)=1
    
            如果i=0且j>0        edit(0, j )=edit(0, j-1)+1
    
            如果i>0且j=0        edit( i, 0 )=edit(i-1, 0)+1
    
            如果i>0且j>0        edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) )
    
    小注
    edit(i,j)表示S中[0.... i]的子串si到T中[0....j]的子串tj的编辑距离。

    f(i,j)表示S中第i个字符s(i)转换到T中第j个字符s(j)所需要的操作次数,
    如果s(i)==s(j),则不需要任何操作f(i, j)=0; 否则,需要替换操作,f(i, j)=1




    转载于:https://www.cnblogs.com/sking7/archive/2011/10/16/2214044.html

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

    万次阅读 多人点赞 2016-12-31 21:31:35
    写在前面的话今年是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

    在这里插入图片描述

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

    这里写图片描述

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

    展开全文
  •  http://hxraid.iteye.com/blog/615469 【串和序列处理 2】字符串编辑距离算法 文章分类:综合技术 我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说:baidu、google、sousou等...
  • #include #include #include /* 求两个数字的最小者 */ #define min(val1, val2) (((val1) .../* 求三个数字的最小者 */ ...#define min3operators(val1, val2, val3) (min(val1, val2) .../*********************...
  • 编辑距离定义通过插入删除或替换使得一个字符串变为另一个字符串的最小操作次数。DP思路设有字符串a和字符串b a[m]表示第一个字符串,m表示该字符串字符的下标为0~m b[n]表示第二个字符串,n表示该字符串字符的下标...
  • 编辑距离算法前言原理实现 前言 有时候 原理 实现
  • https://www.cnblogs.com/xiuyangleiasp/p/5023717.html... 基本介绍  Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一...
  • 字符串编辑距离: 是一种字符串之间相似度计算的方法。给定两个字符串S、T,将S转换成T所需要的删除,插入,替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。举个例子:S=“eeba...
  • 字符串编辑距离算法

    2013-11-27 14:02:08
    我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说:baidu、google、sousou等知名全文搜索系统。当我们输入一个错误的query="Jave... 字符串编辑距离:是一种字符串之间相似度计算
  • 我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说:baidu、google、sousou等知名全文搜索系统。当我们输入一个错误的query="Jave" 的时候,返回中有大量包含...字符串编辑距离: 
  • 这是Levenshtein Distance算法的java实现,另外oracle 10g r2当中好像自带了这样的函数,utl_match包当中 public class LD { /** * 计算矢量距离 * Levenshtein Distance
  • 两个字符串编辑距离即为两个字符串s1, s2经过插入、删除和替换操作使得第一个字符串s1与第二个字符串s2相同所需的最短操作次数。(s1字符个数为m, s2字符个数为n) 利用动态规划的方法,考虑从字符串的最后一个...
  • 字符串编辑距离指的是字符串A向字符串B转换的最小步数。比如字符串“ABC”转换成“A”最少需要删除“B”,“C”两个字符。字符串操作有三种,一个是新增插入,一个是删除,一个是替换。该算法最早由 levenshtein提出...
  • 字符串编辑距离

    2018-10-29 15:10:50
    字符串编辑距离(Edit Distance),是俄罗斯科学家Vladimir Levenshtein在1965年提出的概念,又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。 算法介绍 判断2个字符串相似情况 ...
  • Levenshtein Distance,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。levenshtein() 函数返回两...
  • 编辑距离
  • 参考:https://www.cnblogs.com/shihuajie/p/5772173.html 参考:http://www.cnblogs.com/Aimeast/archive/2011/09/05/2167844.html 参考:https://www.cnblogs.com/shikyoh/p/4995078.html ...
  • 最近研究一个两个字符串相识度的问题,结果发现了Levenshtein distance 算法,最早由俄国人发现,算法介绍可自行百度。...Levenshtein Distance,wordlink_affiliate">编辑距离算法,是指从字符串A变成字符串B,所需

空空如也

1 2 3 4 5 ... 20
收藏数 13,662
精华内容 5,464
关键字:

字符串编辑距离算法