精华内容
参与话题
问答
  • 最小编辑距离

    2018-12-25 14:58:32
    ----总结归纳最小编辑距离的思路(动态规划法) 某位置两字符是否相同 1,相同 该位置等于左上角 2,不同,该位置等于 min(左边+1,左上角+1,上面+1) 这三种分别对应 插入字符串,修改字符串,删除字符串,...

    ----总结归纳最小编辑距离的思路(动态规划法)

    某位置两字符是否相同

    1,相同 该位置等于左上角

    2,不同,该位置等于  min(左边+1,左上角+1,上面+1)

    这三种分别对应  插入字符串,修改字符串,删除字符串,三种方式

     

     

    得到右下角的值为最小编辑距离(如图中的3)

    展开全文
  • 计算最小编辑距离,显示最小距离的计算搜索方式。
  • 主要介绍了Python实现计算最小编辑距离的相关代码,有需要的小伙伴可以参考下
  • 最小编辑代价(最小编辑距离

    千次阅读 2018-07-26 16:11:07
    给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。 举例: str1=”abc” str2=”adc” ic=5 dc=3 rc=2,从”abc”编辑到”adc”把...

    题目描述:

    给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。
    举例:
    str1=”abc” str2=”adc” ic=5 dc=3 rc=2,从”abc”编辑到”adc”把b替换成d代价最小,为2;
    str1=”abc” str2=”adc” ic=5 dc=3 rc=10,从”abc”编辑到”adc”,先删除b再插入d代价最小,为8;

    分析:

    经典动态规划方法,利用二维数组dp[][]保存动态规划表;
    假设str1长度为M[0…..M-1],str2长度为N[0…….N-1],dp大小为(M+1)*(N+1);

    dp[i][j]表示str1[0……i-1]编辑成str2[0……j-1]的最小编辑代价,dp大小为(M+1)*(N+1)是为了从空串开始计算,即dp[0][0]表示空串编辑到空串的最小编辑代价。

    如何生成dp[][]:

    1.dp[0][0]表示空串编辑成空串,故dp[0][0]=0;

    2.求第一行dp[0][j],空串编辑成str2[0….j-1],则dp[0][j]=ic*j;

    3.求第一列dp[i][0],str1[0……i-1]编辑成空串,则dp[i][0]=dc*i;

    4.求dp[i][j],即str1[0….i-1]编辑成str2[0…..j-1],四种可能的途径:

    <1>str1[0….i-1]先编辑成str2[0…..j-2],再由str2[0…..j-2]到str2[0…..j-1],即dp[i][j-1]+ic;

    <2>str1[0….i-1]先编辑成str1[0…..i-2],再由str1[0…..i-2]到str2[0…..j-1],即dc+dp[i-1][j];

    <3>如果str1[i-1]==str2[j-1],则dp[i][j]=dp[i-1][j-1];

       如果str1[i-1]!=str2[j-1],则dp[i][j]=dp[i-1][j-1]+rc;
    

    选择上面四个中最小的值作为dp[i][j],时间复杂度O(MN),空间复杂度O(MN)。最小编辑距离为dp[M][N]。

    public class MinCost {
        public int findMinCost(String A, int n, String B, int m, int ic, int dc, int rc) {
            if(A==null||B==null)
                return 0;
            if(n==0) return m*ic;
            if(m==0) return n*ic;
            int[][] dp=new int[n+1][m+1];
            dp[0][0]=0;
            for(int i=1;i<m+1;++i){
                dp[0][i]=ic*i;
            }
            for(int i=1;i<n+1;++i){
                dp[i][0]=dc*i;
            }
            for(int i=1;i<n+1;++i){
                for(int j=1;j<m+1;++j){
                    if(A.charAt(i-1)==B.charAt(j-1)){
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else{
                        dp[i][j]=dp[i-1][j-1]+rc;
                    }
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+dc);
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+ic);
                }
            }
            return dp[n][m];
        }
    class MinCost {
    public:
        int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {
            int dp[n+1][m+1];
            dp[0][0] = 0;
            for(int i=1;i<=n;i++)
                dp[i][0] = dp[i-1][0] + c1;
            for(int j=1;j<=m;j++)
                dp[0][j] = dp[0][j-1] + c0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    if(A[i-1] == B[j-1])
                        dp[i][j] = dp[i-1][j-1];
                    else
                        dp[i][j] = min(dp[i-1][j-1]+c2, min(dp[i-1][j]+c1, dp[i][j-1]+c0));            
                }         
            return dp[n][m];
        }
    };
    展开全文
  • 如果是A串的第i个字符和B串的第j个字符 1.在A的第i个字符后插入一个字符B[j],问题转化为计算A[i...lenA]和B[j+1...lenB]的距离 ...d [i-1][j] 、d [i][j-1]、d [i-1][j-1]进行比较,其中最小的就是当前A和B的编辑距离
  • 最小编辑距离算法

    万次阅读 2017-05-19 19:55:37
    字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括: 删除一个字符 a) Insert...

    概念

    字符串的编辑距离,又称为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
    代码:
    1. <pre name="code" class="cpp">#include<stdio.h>  
    2. #include<string.h>  
    3. char s1[1000],s2[1000];  
    4. int min(int a,int b,int c)  
    5. {  
    6.     int tmp=a<b?a:b;  
    7.     return tmp<c?tmp:c;  
    8. }  
    9. void editDistance(int len1,int len2)  
    10. {  
    11.     int **d=new int*[len1+1];  
    12.     for(int i=0;i<=len1;i++)  
    13.         d[i]=new int[len2+1];  
    14.     int i,j;  
    15.     for(i=0;i<=len1;i++)  
    16.         d[i][0]=i;  
    17.     for(j=0;j<=len2;j++)  
    18.         d[0][j]=j;  
    19.     for(i=1;i<=len1;i++)  
    20.     {  
    21.         for(j=1;j<=len2;j++)  
    22.         {  
    23.             int cost=s1[i]==s2[j]?0:1;  
    24.             int deletion=d[i-1][j]+1;  
    25.             int insertion=d[i][j-1]+1;  
    26.             int substitution=d[i-1][j-1]+cost;  
    27.             d[i][j]=min(deletion,insertion,substitution);  
    28.         }  
    29.     }  
    30.     printf("距离为:%d\n",d[len1][len2]);  
    31.     for(int i=0;i<=len1;i++)  
    32.     {  
    33.         delete[] d[i];  
    34.     }  
    35.     delete[] d;  
    36. }  
    37.    
    38. int main()  
    39. {  
    40.     while(scanf("%s%s",s1,s2)!=EOF)  
    41.     {  
    42.         editDistance(strlen(s1),strlen(s2));  
    43.     }  
    展开全文
  • 动态编程| (编辑距离) 给定两个字符串str1和str2以及可以对str1执行的操作。找出将“str1”转换为“str2”所需的最小编辑次数(操作)。插入 删除 代替所有上述操作具有相等的成本。例子: 输入:str1 =“geek”...

    动态编程| (编辑距离)

    给定两个字符串str1和str2以及可以对str1执行的操作。找出将“str1”转换为“str2”所需的最小编辑次数(操作)。

    1. 插入
    2. 删除
    3. 代替

    所有上述操作具有相等的成本。

    例子:

    
    

    这种情况下的子问题是什么?
    这个想法是从两个字符串的左侧或右侧逐个处理所有字符。
    让我们从右边角度穿越,对于每一对字符都有两种可能性。

    1. 如果两个字符串的最后字符相同,没有什么可做的。忽略最后一个字符并获取剩余字符串的计数。因此,我们重复长度m-1和n-1。
    2. Else(如果最后字符不相同),我们考虑对“str1”的所有操作,考虑对第一个字符串的最后一个字符的所有三个操作,递归计算所有三个操作的最小成本,并取最少三个值。
      1. 插入:对m和n-1重复
      2. 删除:重复m-1和n
      3. 替换:对m-1和n-1重复

    下面是上面Naive递归解的Java实现。

    Java

    // A Naive recursive Java program to find minimum number
    // operations to convert str1 to str2
    class EDIST
    {
        static int min(int x,int y,int z)
        {
            if (x<y && x<z) return x;
            if (y<x && y<z) return y;
            else return z;
        }
     
        static int editDist(String str1 , String str2 , int m ,int n)
        {
            // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0) return n;
          
        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0) return m;
          
        // If last characters of two strings are same, nothing
        // much to do. Ignore last characters and get count for
        // remaining strings.
        if (str1.charAt(m-1) == str2.charAt(n-1))
            return editDist(str1, str2, m-1, n-1);
          
        // If last characters are not same, consider all three
        // operations on last character of first string, recursively
        // compute minimum cost for all three operations and take
        // minimum of three values.
        return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert
                         editDist(str1,  str2, m-1, n),   // Remove
                         editDist(str1,  str2, m-1, n-1) // Replace                    
                       );
        }
     
        public static void main(String args[])
        {
            String str1 = "sunday";
            String str2 = "saturday";
      
            System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );
        }
    }
    /*This code is contributed by Rajat Mishra*/
    在IDE上运行
    输出:

    
    

    上述解的时间复杂度是指数的。在最坏的情况下,我们可能最终做O(3 m)操作。最坏的情况发生在两个字符串的字符都不匹配时。下面是最坏情况下的递归调用图。
    EditDistance

    我们可以看到,许多子问题被一次又一次解决,例如eD(2,2)被称为三次。由于相同的suproblems被再次调用,这个问题具有重叠子属性。因此,编辑距离问题具有动态规划问题的属性(见这个这个)。像其他典型的动态编程(DP)问题一样,通过构造存储子参数结果的临时数组,可以避免重新计算相同的子问题。

    • Java

    Java

    // A Dynamic Programming based Java program to find minimum
    // number operations to convert str1 to str2
    class EDIST
    {
        static int min(int x,int y,int z)
        {
            if (x < y && x <z) return x;
            if (y < x && y < z) return y;
            else return z;
        }
     
        static int editDistDP(String str1, String str2, int m, int n)
        {
            // Create a table to store results of subproblems
            int dp[][] = new int[m+1][n+1];
          
            // Fill d[][] in bottom up manner
            for (int i=0; i<=m; i++)
            {
                for (int j=0; j<=n; j++)
                {
                    // If first string is empty, only option is to
                    // isnert all characters of second string
                    if (i==0)
                        dp[i][j] = j;  // Min. operations = j
          
                    // If second string is empty, only option is to
                    // remove all characters of second string
                    else if (j==0)
                        dp[i][j] = i; // Min. operations = i
          
                    // If last characters are same, ignore last char
                    // and recur for remaining string
                    else if (str1.charAt(i-1) == str2.charAt(j-1))
                        dp[i][j] = dp[i-1][j-1];
          
                    // If last character are different, consider all
                    // possibilities and find minimum
                    else
                        dp[i][j] = 1 + min(dp[i][j-1],  // Insert
                                           dp[i-1][j],  // Remove
                                           dp[i-1][j-1]); // Replace
                }
            }
      
            return dp[m][n];
        }
     
         
     
        public static void main(String args[])
        {
            String str1 = "sunday";
            String str2 = "saturday";
            System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) );
        }
    }/*This code is contributed by Rajat Mishra*/
    在IDE上运行
    spaces”>                                   dp[i-1][j-1])    # Replace
     
        return dp[m][n]
     
    # Driver program
    str1 = "sunday"
    str2 = "saturday"
     
    print(editDistDP(str1, str2, len(str1), len(str2)))
    # This code is contributed by Bhavya Jain
    Run on IDE

    输出:

    
    

    时间复杂度:O(m×n)
    辅助空间:O(m×n)

    应用:有很多实际应用的编辑距离算法,参考Lucene API的样例。另一个例子,显示字典中靠近给定单词\拼写错误的单词的所有单词。

    关于Venki

    软件工程师

    帖子导航
    <<上一页 下一页>> arrPost.push('13178'); arrPost.push('Dynamic Programming | Set 5 (Edit Distance)'); arrPost.push('http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/'); arrPost.push('Dynamic Programming');
    3.2 平均难度:3.2 / 5.0
    基于162票,






    展开全文
  • 在一个文本词库里查找相似单词,就是输入一个单词,在词库里找与这个单词相似的单词,由相似度大到小,用最小编辑距离实现C++ #include #include <iostream> #include <string> #include <string.h> #include ...

空空如也

1 2 3 4 5 ... 20
收藏数 682
精华内容 272
关键字:

最小编辑距离