Jan 9

字符串的 编辑距离 问题。 不指定

felix021 @ 2009-1-9 15:19 [IT » 程序设计] 评论(6) , 引用(0) , 阅读(9820) | Via 本站原创 | |
这是今天算法考试的最后一题,设计一个动态规划的算法来求两个字符串的编辑距离。
以为自己做对了,很happy —— 其实错了,好笨,sigh.

--

Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离),它用来表示2个字符串的相似度,LD定义为需要最少多少步基本操作才能让2个字符串相等,基本操作包含3个:插入, 删除, 替换;比如,kiteen和sitting之间的距离可以这么计算:  
          1,kitten   --   >   sitten,   替换k为s;  
          2,sitten   --   >   sittin,   替换e为i;  
          3,sittin   --   >   sitting,   增加g;  
所以,其LD为3。

设计状态d[m][n] = d(A[1..m], B[1..n]),易知:
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
                   d[i-1][j] + 1, //插入一个字符
                   d[i][j-1] + 1  //删除一个字符

于是可以递推地填满一个 m * n 的矩阵,即得答案。
计算LD的算法表示为(C++代码):  
int d[1010][1010];
int dist(string a, string b){
    int m = a.size(), n = b.size(), i, j;
    for(i = 0; i <= m; ++i) d[i][0] = i;
    for(j = 0; j <= n; ++j) d[0][j] = j;
    for (i = 1; i <= m; ++i){
        for(j = 1; j <= n; ++j){
            //    --------------     a, b是从0开始计数的
            d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
            d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
            d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
        }
    }
    for (i = 0; i <= m; ++i){ //打印矩阵
        for(j = 0; j <= n; ++j)
            printf("%5d ", d[i][j]);
        printf("\n");
    }
    return d[m][n];
}

这个算法其实就是一个矩阵的计算:  
引用
调用dist("abcdef", "acddaf")可以得到输出为:
    0     1     2     3     4     5     6
    1     0     1     2     3     4     5
    2     1     1     2     3     4     5
    3     2     1     2     3     4     5
    4     3     2     1     2     3     4
    5     4     3     2     2     3     4
    6     5     4     3     3     3     3

最后的d[m][n]就是求得的答案。

@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组):
int diff(char *a, char *b){
    int *d[2], i, j;
    int m = strlen(a), n = strlen(b);
    d[0] = new int[n + 1];
    d[1] = new int[n + 1];
    int turn = 0, pre, t;
    for (i = 0; i <= n; ++i) d[turn][i] = i;
    for (i = 1; i <= m; ++i){
        pre = turn;
        turn = (turn + 1) % 2;
        d[turn][0] = i;
        for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
        for(j = 1; j <= n; ++j){
            t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
            t = min(t, d[pre][j] + 1);
            d[turn][j] = min(t, d[turn][j-1] + 1);
        }
    }
    for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
    t = d[turn][n];
    delete[] d[0];
    delete[] d[1];
    return t;
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
BTzjz
2009-12-31 13:20
调用dist("abcdef", "acddaf")可以得到输出为:
    0     1     2     3     4     5     6
    1     0     1     2     3     4     5
    2     1     1     2     3     4     5
    3     2     1     2     3     4     5
    4     3     2     1     2     3     4
    5     4     3     2     2     3     4
    6     5     4     3     3     3     3
如何通过以上知道LD

这个编辑距离就是矩阵的最后一个元素啊,就是3咯
BTzjz
2009-12-31 13:19
请问如果怎么在中途知道编辑距离已经到达多少了呢?是看对角线么?
felix021 回复于 2009-12-31 14:03
“中途的编辑距离”,这个概念很有意思,建议先搞清楚1. 这个概念到底是指什么东西的编辑距离2. 是否有考虑这个东西的必要
ryj
2009-10-29 13:07
调用dist("abcdef", "acddaf")可以得到输出为:
    0     1     2     3     4     5     6
    1     0     1     2     3     4     5
    2     1     1     2     3     4     5
    3     2     1     2     3     4     5
    4     3     2     1     2     3     4
    5     4     3     2     2     3     4
    6     5     4     3     3     3     3
如何通过以上知道LD
ryj
2009-10-29 13:05
ok
Xplus
2009-1-9 22:13
都说了,你帮我考线代,我帮你考算法,这都好……哎
felix021 回复于 2009-1-9 22:59
。。我保证我会帮你挂线代
riz
2009-1-9 15:29
如果有机会…我以后就要和这些打交道了…恐怖…
felix021 回复于 2009-1-9 17:06
不恐怖,很好玩儿的。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]