首页 > 专题系列 > 算法分析 > 动态规划(5)-最小编辑距离(Edit Distance)
2014
03-07

动态规划(5)-最小编辑距离(Edit Distance)

继续动态规划系列案例讲解–编辑距离,一个很有趣的算法。

问题:给定一个长度为m和n的两个字符串,设有以下几种操作:替换(R),插入(I)和删除(D)且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小(操作)数量。

PS:最短编辑距离算法右许多实际应用,参考Lucene的 API。另一个例子,对一个字典应用,显示最接近给定单词\正确拼写单词的所有单词。

找递归函数:

这个案例的子问题是什么呢?考虑寻找的他们的前缀子串的编辑距离,让我们表示他们为

[1 ... i]和[1 ....j] , 1<i<m 和1 <j <n

显然,这是解决最终问题的子问题,记为E(i,j)。我们的目标是找到E(m,n)和最小的编辑距离。

我们可以用三种方式: (i, -), (-, j) 和(i, j)右对齐两个前缀字符串。连字符符号( – )表示没有字符。看一个例子或许会更清楚:

假设给定的字符串是 SUNDAY 和 SATURDAY。如果 i= 2 ,  j = 4,即前缀字符串分别是SU和SATU(假定字符串索引从1开始)。这两个字串最右边的字符可以用三种不同的方式对齐:

1  (i, j): 对齐字符U和U。他们是相等的,没有修改的必要。我们仍然留下其中i = 1和j = 3,即问题E(1,3)

2 (i, -) : 对第一个字符串右对齐,第二字符串最右为空字符。我们需要一个删除(D)操作。我们还留下其中i = 1和j = 4的 子问题 E(i-1,j)。

3 (-, j)  :  对第二个字符串右对齐,第一个字符串最右为空字符。在这里,我们需要一个插入(I)操作。我们还留下了子问题 i= 2 和 j = 3,E(i,j-1)。

对于这三种操作,我可以得到最少的操作为:

E(i, j) = min( [E(i-1, j) + D], [E(i, j-1) + I],  [E(i-1, j-1) + R (如果 i,j 字符不一样)] )

到这里还没有做完。什么将是基本情况?

当两个字符串的大小为0,其操作距离为0。当其中一个字符串的长度是零,需要的操作距离就是另一个字符串的长度. 即:

E(0,0)= 0,E(i,0)= i,E(0,j)= j

为基本情况。这样就可以完成递归程序了。

动态规划解法:

我们先计算出上面递归表达式的时间复杂度:T(m, n) = T(m-1, n-1) + T(m, n-1) + T(m-1, n) + C

T(M,N)的复杂性,可以通过连续替代方法或结二元齐次方程计算。结果是指数级的复杂度。

这是显而易见的,从递归树可以看出这将是一次又一次地解决子问题。

我们对重复子问题的结果打表存储,并在有需要时(自下而上)查找。

动态规划的解法时间复杂度为 O(mn) 正是我们打表的时间.

通常情况下,D,I和R操作的成本是不一样的。在这种情况下,该问题可以表示为一个有向无环图(DAG)与各边的权重,并且找到最短路径给出编辑距离。

实现代码如下:

给出了动态规划实现 和 递归实现。大家可以比较他们的效率差异。

// 动态规划实现 最小编辑距离
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// 测试字符串
#define STRING_X "SUNDAY"
#define STRING_Y "SATURDAY"

#define SENTINEL (-1)
#define EDIT_COST (1)

inline
int min(int a, int b) {
   return a < b ? a : b;
}

// Returns Minimum among a, b, c
int Minimum(int a, int b, int c)
{
    return min(min(a, b), c);
}

// Strings of size m and n are passed.
// Construct the Table for X[0...m, m+1], Y[0...n, n+1]
int EditDistanceDP(char X[], char Y[])
{
    // Cost of alignment
    int cost = 0;
    int leftCell, topCell, cornerCell;

    int m = strlen(X)+1;
    int n = strlen(Y)+1;

    // T[m][n]
    int *T = (int *)malloc(m * n * sizeof(int));

    // Initialize table
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            *(T + i * n + j) = SENTINEL;

    // Set up base cases
    // T[i][0] = i
    for(int i = 0; i < m; i++)
        *(T + i * n) = i;

    // T[0][j] = j
    for(int j = 0; j < n; j++)
        *(T + j) = j;

    // Build the T in top-down fashion
    for(int i = 1; i < m; i++)
    {
        for(int j = 1; j < n; j++)
        {
            // T[i][j-1]
            leftCell = *(T + i*n + j-1);
            leftCell += EDIT_COST; // deletion

            // T[i-1][j]
            topCell = *(T + (i-1)*n + j);
            topCell += EDIT_COST; // insertion

            // Top-left (corner) cell
            // T[i-1][j-1]
            cornerCell = *(T + (i-1)*n + (j-1) );

            // edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise
            cornerCell += (X[i-1] != Y[j-1]); // may be replace

            // Minimum cost of current cell
            // Fill in the next cell T[i][j]
            *(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
        }
    }

    // 结果存储在 T[m][n]
    cost = *(T + m*n - 1);
    free(T);
    return cost;
}

// 递归方法实现
int EditDistanceRecursion( char *X, char *Y, int m, int n )
{
    // 基本情况
    if( m == 0 && n == 0 )
        return 0;

    if( m == 0 )
        return n;

    if( n == 0 )
        return m;

    // Recurse
    int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
    int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
    int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]);

    return Minimum(left, right, corner);
}

int main()
{
    char X[] = STRING_X; // vertical
    char Y[] = STRING_Y; // horizontal

    printf("Minimum edits required to convert %s into %s is %d\n",
           X, Y, EditDistanceDP(X, Y) );
    printf("Minimum edits required to convert %s into %s is %d by recursion\n",
           X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));

    return 0;
}

参考:http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.